(1)執行時間
(2)存儲空間
(3)編程工作
對於少量數據,(1)(2)差別不大,主要考慮(3);對於大數據量,(1)是第壹。
主要的排序方法有:
壹、冒泡排序——相鄰交換
第二,選擇排序——最小/最大的壹行壹次在相應的位置。
三、插入排序——將下壹個插入到排列好的序列中。
第四,外殼分類——減少增量
動詞 (verb的縮寫)合並和排序
第六,快速排序
七、堆排序
八、拓撲排序
首先,冒泡排序
-
void BubbleSortArray()
{
for(int I = 1;我& ltn;i++)
{
for(int j = 0;我& ltn-I;j++)
{
if(a[j]& gt;A[j+1])//比較並交換相鄰元素。
{
內部溫度;
temp = a[j];a[j]= a[j+1];a[j+1]= temp;
}
}
}
}
-代碼-
效率O(n?),適合排序小列表。
第二,選擇排序
-
void SelectSortArray()
{
int min _ index
for(int I = 0;我& ltn-1;i++)
{
min _ index = I;
for(int j = I+1;j & ltn;J++)//為每次掃描選擇最小的項目。
if(arr[j]& lt;arr[min _ index])min _ index = j;
if(min_index!=i)//找到最小的項交換,也就是把這個項移動到列表中正確的位置。
{
內部溫度;
temp = arr[I];arr[I]= arr[min _ index];arr[最小索引]= temp;
}
}
}
-代碼-
效率O(n?),適合小排序的列表。
第三,插入排序
-
void InsertSortArray()
{
for(int I = 1;我& ltn;I++)//循環從第二個數組元素開始,因為arr[0]是原來排序的部分。
{
int temp = arr[I];//temp將第壹個元素標記為無序。
int j = I-1;
while(j & gt;= 0 & amp& amparr[j]& gt;Temp)/*將Temp與從小到大排序的元素進行比較,找出應該在哪裏插入temp */
{
arr[j+1]= arr[j];
j-;
}
arr[j+1]= temp;
}
}
-代碼-
最優效率o(n);最差效率O(n?)與冒泡和選擇相同,適用於小列表排序。
如果列表基本有序,插入排序比冒泡選擇效率高。
第四,外殼排序——減少增量排序
-
void ShellSortArray()
{
for(int incr = 3;incr & lt0;incr-)///增量減少,以增量3,2,1為例。
{
for(int L = 0;L & lt(n-1)/incr;L++)//重復每個子列表。
{
for(int I = L+incr;我& ltn;I+=incr)//對每個子列表應用插入排序。
{
int temp = arr[I];
int j = I-incr;
while(j & gt;= 0 & amp& amparr[j]& gt;溫度)
{
arr[j+incr]= arr[j];
j-= incr;
}
arr[j+incr]= temp;
}
}
}
}
-代碼-
適合對小列表進行排序。
效率估計o (nlog 2 n) ~ o (n 1.5)取決於增量值的初始大小。建議使用質數作為增量值,因為如果增量值是2的冪,則在下壹個通道中將再次比較相同的元素。
外殼排序改進了插入排序,減少了比較的次數。是壹種不穩定的排序,因為元素可能會在排序過程中來回跳轉。
動詞 (verb的縮寫)合並和排序
-
void MergeSort(int low,int high)
{
if(低& gt=高)回報;//當每個子列表中還剩壹個元素時停止。
else int mid=(低+高)/2;/*將列表分成兩個相等的子列表。如果有奇數個元素,左邊的子列表比右邊的子列表大*/
MergeSort(低,中);//子列表進壹步劃分。
MergeSort(mid+1,高);
int[]B = new int[高-低+1];//創建壹個新數組來存儲合並的元素。
for(int I =低,j=mid+1,k =低;我& lt= mid & amp& ampj & lt=高;K++)/*兩個子列表被排序並合並,直到兩個子列表中的壹個結束*/
{
if(arr[I]& lt;= arr[j];)
{
b[k]= arr[I];
i++;
}
其他
{ B[k]= arr[j];j++;}
}
for(;j & lt=高;J++,k++)//如果第二個子列表中還有元素,追加到新列表中。
b[k]= arr[j];
for(;我& lt= midI++,k++)//如果第壹個子列表中還有元素,就把它們追加到新列表中。
b[k]= arr[I];
for(int z = 0;z & lt高低開+1;Z++)//將排序後的數組B的所有元素復制到原數組arr中。
arr[z]= B[z];
}
-代碼-
效率O(nlogn),合並的最佳、平均和最差用例效率之間沒有區別。
適合對大型列表進行排序,基於分治法。
第六,快速排序
-代碼-
/*快速排序的算法思路:選擇壹個hub元素,對待排序的序列進行分割,分割後的序列壹部分小於hub元素,另壹部分大於hub元素,然後對兩個分割後的子序列進行上述過程。*/ void swap(int a,int b){ int t;t = a;a = b;b = t;}
int Partition(int [] arr,int low,int high)
{
int pivot = arr[low];//使用子序列的第壹個元素作為pivot元素。
while(low & lt;高)
{
//從後半部分和前半部分查找第壹個小於pivot元素的元素。
while(low & lt;高& amp& amparr[high]>=樞軸)
{
-高;
}
//將這個比pivot元素小的元素交換到前半部分。
swap(arr[低],arr[高]);
//在轉到後,查找前半部分中第壹個大於pivot元素的元素。
while(low & lt;高& amp& amparr[low]& lt;=樞軸)
{
++低電平;
}
swap(arr[低],arr[高]);//將此pivot元素的大元素切換到後半部分。
}
返低;//返回透視元素的位置。
}
void快速排序(int [] a,int low,int high)
{
if(低& lt高)
{
int n=Partition (a,low,high);
快速排序(a,低,n);
快速排序(a,n +1,高);
}
}
-代碼-
平均效率O(nlogn),適合對大型列表進行排序。
該算法的總時間取決於主元值的位置;選擇第壹個元素作為軸心可能導致O(n?)最差情況效率。如果數量基本有序,效率最差。以期權的中間值作為中樞,效率為O(nlogn)。
基於分而治之。
七、堆排序
最大堆:後者任意非終結節點的關鍵字大於等於其左右子節點的關鍵字,堆頂節點的關鍵字在整個序列中最大。
心想:
(1)設i=l,temp = kl
(2)計算I j=2i+1的左子;
(3)如果J
(4)比較kj和kj+1,如果kj+1 & gt;Kj,則讓j = j+1,否則j不變;
(5)比較溫度和kj,如果kj >;Temp,然後使ki等於kj,i=j,j=2i+1,轉到(3),否則轉到(6)。
(6)使ki等於temp,並結束。
-代碼-
void堆排序
{//對於R [1的堆排序...n],我們不妨用R[0]作為臨時存儲單元int I;build heap(R);//將R[1-n]構建到for(I = n;我& gt1;I-)//堆排序當前無序區域R[1..i],* * *做n-1次。{ R[0]= R[1];R[1]= R[I];R[I]= R[0];//在堆頂和堆中最後壹條記錄之間交換Heapify(R,1,I-1);//重新調整R [1...I-1]作為堆,只有R[1]可能違反堆的性質}} -。
堆排序的時間主要由建立初始堆的時間開銷和反復重建堆的時間開銷組成,兩者都是通過調用Heapify實現的。
堆排序的最壞時間復雜度是O(nlgn)。堆排序的平均性能接近最差性能。因為初始堆需要更多的比較,所以堆排序不適合記錄較少的文件。堆排序是局部排序,輔助空間是O(1),是壹種不穩定的排序方式。
堆排序和直接插入排序的區別;
在直接選擇排序中,為了從R [1中選擇具有最小關鍵字的記錄...n],需要進行n-1次比較,然後從R[2]中選擇關鍵字最小的記錄...n],而且要進行n-2次比較。事實上,在後面的n-2次比較中,可能在前面的n-1次比較中已經進行了很多次比較,但是由於在前面的排序中沒有保留這些比較結果,所以在接下來的排序中重復了這些比較操作。
堆排序可以通過樹形結構保存壹些比較結果,可以減少比較的次數。
八、拓撲排序
例子:學生選修課的安排順序
拓撲排序:根據優先關系將有向圖中的頂點排列成線性序列的過程。
方法:
在有向圖中選擇壹個沒有前身的頂點並輸出。
從圖中刪除頂點和所有以它結尾的弧。
重復以上兩步,直到所有頂點都已輸出(拓撲排序成功),或者當圖中沒有無前任的頂點時(圖中有環)。
-代碼-
Void TopologicalSort()/*輸出拓撲排序函數。如果G沒有回路,則輸出G的頂點的拓撲序列並返回OK,否則返回ERROR*/
{
int in degree[M];
int i,k,j;
char n;
int count = 0;
堆疊堆棧;
FindInDegree(G,in degree);//找到每個頂點的度數[0...數字]
init stack(the stack);//初始化堆棧
for(I = 0;我& ltG.numi++)
控制臺。WriteLine ("node" +G.vertices[i].data+”有“+degree [i]”的度;
for(I = 0;我& ltG.numi++)
{
if(indegree[i]==0)
push(the stack . vertices[I]);
}
控制臺。Write("拓撲排序輸出順序為:");
while(thestack。Peek()!=空)
{
彈出(堆棧。peek());
j=locatevex(G,n);
如果(j==-2)
{
控制臺。WriteLine("出現錯誤,程序結束。");
exit();
}
控制臺。寫(G.vertices[j].數據);
count++;
for(p=G.vertices[j].firstarcp!= NULLp=p.nextarc)
{
k = p . adj vex;
如果(!(- indegree[k]))
push(g . vertices[k]);
}
}
if(count & lt;數量)
科索萊。WriteLine("圖有環,有錯,不能排序。");
其他
控制臺。WriteLine("排序成功。");
}
-代碼-
算法的時間復雜度為O(n+e)。