溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
定義：排序是計算機內經常進行的一種操作，其目的是將一組“無序”的數據調整為“有序”的數據元素。
數學定義：假設含有n個數據元素的序列為{R1,R2...Rn},其相應的關鍵字序列為：{K1,K2...Kn};這些關鍵字相互之間進行比較，即：在他們之間存在著這樣的一個關系：Kp1 <= Kp2 <= ... <= Kpn按此固有關系將上式重新排列為：{Rp1, Rp2, ... Rpn}的操作稱為排序。
問題：什么按照總評排序后張無忌的排名比郭靖靠前呢？
排序的穩定性：
如果序列中有兩個數據元素Ri和Rj,他們關鍵字的Ki == Kj，且排序之前，對象Ri排在Rj之前，但排序之后兩者的順序交互，則稱這個排序方案是不穩定的。
排序時需要比較的關鍵字有多個，排序結果首先按照關鍵字1進行，當關鍵字1相同，按照關鍵字2進行排序...
多關鍵字的排序并不比單關鍵字復雜，只需要在定義比較操作時，同時考慮多個關鍵字即可!
多關鍵字排序實例：
class MulitKeySort : public Object
{
protected:
int key1;
int key2;
public:
MulitKeySort(int k1, int k2)
{
key1 = k1;
key2 = k2;
}
bool operator ==(const MulitKeySort& m)
{
return ( (key1==m.key1) && (key2==m.key2));
}
bool operator !=(const MulitKeySort& m)
{
return !(*this == m);
}
bool operator <(const MulitKeySort& m)
{
return ( (key1<m.key1) || ((key1==m.key1) && (key2<m.key2)));
}
bool operator >=(const MulitKeySort& m)
{
return !(*this < m);
}
bool operator >(const MulitKeySort& m)
{
return ( (key1>m.key1) || ((key1==m.key1) && (key2>m.key2)));
}
bool operator <=(const MulitKeySort& m)
{
return !(*this > m);
}
};
//測試代碼：
void test_1()
{
MulitKeySort m1(3, 4);
MulitKeySort m2(3, 3);
cout << (m1 > m2) << endl;
}排序中的關鍵操作
算法的實現復雜度：過于復雜的排序算法可能影響可讀性和可維護性。
繼承自頂層父類Object，并且私有化所有構造途徑，將各種排序算法設計為靜態成員函數。
class DTSort : public Object
{
private:
DTSort();
DTSort(const DTSort&);
DTSort& operator =(const DTSort&);
template < typename T >
static void Swap(T& a, T& b)
{
T c(a);
a = b;
b = c;
}
}；基本思想：每次（例如第i次，i=0，1，2...,n-2）從后面n-1個待排列的的數據元素中選出關鍵字最新的元素，左右有序元素序列的i個元素。
template < typename T >
static void SelectSort(T array[], int len, bool min2max = true)
{
for(int i=0; i<len; i++)
{
int min = i;
for(int j=i+1; j<len; j++)
{
if(min2max ? array[j]<array[min] : array[j]>array[min])
{
min = j;
}
}
if(i != min)
{
Swap(array[i], array[min]);
}
}
}選擇排序每次選擇未排序的最小元素，插入排序每次將第i個元素插入前面i-1個已經排序的序列；
當插入第i(i>=1)個數據元素時，前面的V[0],V[1],...,V[i-1]已經排好序，這時用V[i]的關鍵字與前i-1個關鍵字進行比較，找到位置后將V[i]插入，原來位置上的對象向后順移。
template < typename T >
static void InsertSort(T array[], int len, bool min2max = true)
{
for(int i=1; i<len; i++)
{
int k = i;
T e = array[i];
for(int j=i-1; (j>=0) && (min2max ? array[j]>e : array[j]<e); j--)
{
array[j+1] = array[j];
k = j;
}
if(k != i)
{
array[k] = e;
}
}
}選擇排序是不穩定的排序法，插入排序時穩定的排序法。兩者的時間復雜度都為O(n^2)
基本思想：每次從后向前進行（假設為第i次），j=n-1, n-2, ...i, 兩兩比較V[j-1]和V[j]的關鍵字；如果發生逆序，則交換V[j-1]和V[j]。
template < typename T >
static void BubbleSort(T array[], int len, bool min2max = true) // 穩定， O(n^2)
{
bool exchange = true;
for(int i=0; (i<len) && exchange; i++)
{
exchange = false;
for(int j=len-1; j>i; j--)
{
if(min2max ? array[j] < array[j-1] : array[j] > array[j-1])
{
Swap(array[j], array[j-1]);
exchange = true;
}
}
}
}冒泡排序每次從后向前將較小的元素交換到位，是一種穩定的排序方法，其負責度為O(n^2);
基本思想：將待排序劃分為若干組，在每一組進行插入排序，以使整個序列基本有序，然后再對整個序列進行插入排序。
例如:將n個數據元素分成d個子序列：
其中，d稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為1。
template < typename T >
static void ShellSort(T array[], int len, bool min2max = true) // 不穩定， O(n^2/3)
{
int d = len;
do
{
d = d / 3 +1;
cout << "d = " << d << endl;
for(int i=d; i<len; i+=d)
{
int k = i;
T e = array[i];
for(int j=i-d; (j>=0) && (min2max ? (array[j]>e) : (array[j]<e)); j-=d) // ...
{
array[j+d] = array[j];
k = j;
}
if(k != i)
{
array[k] = e;
}
}
}while(d>1);
}希爾排序通過分組的方式進行多次插入排序，是一種不穩定的排序法，復雜度為O(n^2/3)。
基本思想：將兩個或者兩個以上的有序序列合并成一個新的有序序列。
這種方法稱為二路歸并。同理，將N個有序序列歸并未一個新有序序列稱為N路歸并。
template <typename T>
static void Merge(T src[], T helper[], int begin, int mid, int end, bool min2max)
{
int i = begin;
int j = mid + 1;
int k = begin; //輔助空間的起始位置
while( (i<=mid) && (j<=end) )
{
if(min2max ? src[i]<src[j] : src[i]>src[j])
{
helper[k++] = src[i++];
}
else
{
helper[k++] = src[j++];
}
}
while(i <= mid) // 左路數據有剩余，直接合并入最終序列
{
helper[k++] = src[i++];
}
while(j <= end) // ...
{
helper[k++] = src[j++];
}
for(int i=begin; i<=end; i++)
{
src[i] = helper[i]; // 將數據拷貝回原來空間
}
}
template <typename T>
static void Merge(T src[], T helper[], int begin, int end, bool min2max)
{
if(begin < end) //遞歸出口
{
int mid = (begin + end) / 2;
// 左路數據合并
Merge(src, helper, begin, mid, min2max);
// 右路數據合并
Merge(src, helper, mid+1, end, min2max);
// 二路歸并
Merge(src, helper, begin, mid, end, min2max);
}
}
template < typename T >
static void MergeSort(T array[], int len, bool min2max = true)
{
// 申請輔助堆空間
T* helper = new T[len];
cout << "help: " << helper <<endl;
if(helper != NULL)
{
Merge(array, helper, 0, len-1, min2max);
}
delete[] helper;
}基本思想：
任取序列中的某個數據元素作為基準將整個序列劃分為左右兩個子序列。
基準元素排列在這兩個子序列中間；
分別對這兩個子序列重復進行劃分，直到所有的數據元素都排在相應的位置上為止。
template <typename T>
static int Partion(T array[], int begin, int end, bool min2max)
{
T pv = array[begin];
while(begin < end)
{
while( (begin<end) && (min2max ? (array[end]>pv) : (array[end]<pv)) )
{
end--;
}
Swap(array[begin], array[end]);
while( (begin<end) && (min2max ? (array[begin]<=pv) : (array[begin]>=pv)) )
{
begin++;
}
Swap(array[begin], array[end]);
}
return begin;
}
template <typename T>
static void Quick(T src[], int begin, int end, bool min2max)
{
if(begin < end) //遞歸出口
{
//對序列進行區域劃分,返回基準元素的位置
int pivot = Partion(src, begin, end, min2max);
//對基準左側的數據元素進行排序
Quick(src, begin, pivot-1, min2max);
//對基準右側的數據元素進行排序
Quick(src, pivot+1, end, min2max);
}
}
template < typename T >
static void QuickSort(T array[], int len, bool min2max = true)
{
Quick(array, 0, len-1, min2max);
}在前面的章節中，我們實現了自己的數組類，排序類DTSrot和數組類Array之間存在什么關系？
排序類的實現，不單要考慮對元素數據的排序，也應該支持自定義數據的排序。
新增成員函數：
排序類中增加可以實現數組類的成員函數(應該作為之前原生數組排序類的重載版本)；
//使排序算法支持自定義數組類的排序
template < typename T >
static void SelectSort(Array<T>& array, bool min2max = true)
{
SelectSort(array.array(), array.length(), min2max);
}
template < typename T >
static void InsertSort(Array<T>& array, bool min2max = true)
{
InsertSort(array.array(), array.length(), min2max);
}
template < typename T >
static void BubbleSort(Array<T>& array, bool min2max = true)
{
BubbleSort(array.array(), array.length(), min2max);
}
template < typename T >
static void ShellSort(Array<T>& array, bool min2max = true)
{
ShellSort(array.array(), array.length(), min2max);
}
template < typename T >
static void MergeSort(Array<T>& array, bool min2max = true)
{
MergeSort(array.array(), array.length(), min2max);
}
template < typename T >
static void QuickSort(Array<T>& array, bool min2max = true)
{
QuickSort(array.array(), array.length(), min2max);
}問題：當待排序數據元素為體積龐大的對象時，如何提高排序效率？
譬如對下面的對象使用冒泡排序算法進行排序，必然涉及大量的數據交換，嚴重影響效率。
問題分析：
1.排序過程中不可避免的要進行交換操作，交換操作的本質為數據元素的復制，當數據元素體積較大時，交換操作耗時巨大。
代理模式：
1.為待排序數據元素設置代理對象；
2.對代理對象所組成的序列進行排序
3.需要訪問有序數據元素時，通過訪問代理序列完成。
艱苦奮斗酸辣粉
struct Test :public Object
{
int id;
int data1[1000];
double data2[500];
bool operator < (const Test& obj)
{
return id < obj.id;
}
bool operator <= (const Test& obj)
{
return id <= obj.id;
}
bool operator >= (const Test& obj)
{
return id >= obj.id;
}
bool operator > (const Test& obj)
{
return id > obj.id;
}
};
class TestProxy : public Object
{
protected:
Test* pTest;
public:
int id()const
{
return pTest->id;
}
int* data1()const
{
return pTest->data1;
}
double* data2()const
{
return pTest->data2;
}
Test& test()const
{
return *pTest;
}
bool operator >(const TestProxy& obj)
{
return test() > obj.test();
}
bool operator >=(const TestProxy& obj)
{
return test() >= obj.test();
}
bool operator <(const TestProxy& obj)
{
return test() < obj.test();
}
bool operator <=(const TestProxy& obj)
{
return test() <= obj.test();
}
Test& operator =(Test& test)
{
pTest = &test;
return test;
}
};
Test t[1000];
TestProxy pt[1000];
void test_3()
{
clock_t begin = 0;
clock_t end = 0;
for(int i=0;i<1000;i++)
{
t[i].id = i;
pt[i] = t[i];
}
begin = clock();
//DTSort::BubbleSort(t,1000,false);
DTSort::BubbleSort(pt,1000,false);
end = clock();
cout << "Time:" << (end - begin) << endl;
for(int i=0;i<1000;i++)
{
//cout << t[i].id << " " << pt[i].id() << endl;
}
}使用代理模式：
不使用代理模式：
兩者時間相差超過50倍，可見代碼模式的優勢。
總結：
1.排序類應當同時支持原生數組和數組類的的排序；
2.當排序元素為體積龐大的對象時，可以考慮使用代理模式簡介完成（有效避開大對象交換時的耗時操作），是空間換時間思想的體現。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
