下面針對不同排序進行一一講解。
一、直接插入排序（Insertion Sort)
算法思想：
直接插入排序的核心思想就是：將數組中的所有元素依次跟前面已經排好的元素相比較，如果選擇的元素比已排序的元素小，則交換，直到全部元素都比較過 因此，從上面的描述中我們可以發現，直接插入排序可以用兩個循環完成：
第一層循環：遍歷待比較的所有數組元素
第二層循環：將本輪選擇的元素(selected)與已經排好序的元素(ordered)相比較。如果：selected > ordered，那麼將二者交換。
算法代碼：
void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl;} void InsertSort(int a[], int n){ for(int i= 1; i<n; i++){ if(a[i] < a[i-1]){ int j= i-1; int x = a[i]; a[i] = a[i-1]; while(x < a[j]){ a[j+1] = a[j]; j--; } a[j+1] = x; } print(a,n,i); }
}
int main(){ int a[8] = {3,1,5,7,2,4,9,6}; InsertSort(a,8); print(a,8,8);}二、希爾排序（Shell' s Sort）
算法思想:
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄「基本有序」時，再對全體記錄進行依次直接插入排序。
算法步驟：
1.選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2.按增量序列個數k，對序列進行k 趟排序；
3.每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
算法代碼:
void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl;}
void ShellInsertSort(int a[], int n, int dk){ for(int i= dk; i<n; ++i){ if(a[i] < a[i-dk]){ int j = i-dk; int x = a[i]; a[i] = a[i-dk]; while(x < a[j]){ a[j+dk] = a[j]; j -= dk; } a[j+dk] = x; } print(a, n,i ); }
}
void shellSort(int a[], int n){
int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; }}int main(){ int a[8] = {3,1,5,7,2,4,9,6}; shellSort(a,8); print(a,8,8);}三、簡單選擇排序（Selection Sort）
算法思想：
簡單選擇排序的實現思想：比較+交換
從待排序序列中，找到關鍵字最小的元素；
如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換；
從餘下的 N - 1 個元素中，找出關鍵字最小的元素，重複(1)、(2)步，直到排序結束。因此我們可以發現，簡單選擇排序也是通過兩層循環實現。第一層循環：依次遍歷序列當中的每一個元素 第二層循環：將遍歷得到的當前元素依次與餘下的元素進行比較，符合最小元素的條件，則交換。
算法代碼：
void print(int a[], int n ,int i){ cout<<"第"<<i+1 <<"趟 : "; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl;}/** * 數組的最小值 * * @return int 數組的鍵值 */int SelectMinKey(int a[], int n, int i){ int k = i; for(int j=i+1 ;j< n; ++j) { if(a[k] > a[j]) k = j; } return k;}
/** * 選擇排序 * */void selectSort(int a[], int n){ int key, tmp; for(int i = 0; i< n; ++i) { key = SelectMinKey(a, n,i); if(key != i){ tmp = a[i]; a[i] = a[key]; a[key] = tmp; } print(a, n , i); }}int main(){ int a[8] = {3,1,5,7,2,4,9,6}; cout<<"初始值："; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl<<endl; selectSort(a, 8); print(a,8,8);}四、堆排序（Heap Sort）
算法思想：
堆的概念
堆：本質是一種數組對象。特別重要的一點性質：任意的葉子節點小於（或大於）它所有的父節點。對此，又分為大頂堆和小頂堆：
大頂堆要求節點的元素都要大於其孩子。
小頂堆要求節點元素都小於其左右孩子。
兩者對左右孩子的大小關係不做任何要求。
利用堆排序，就是基於大頂堆或者小頂堆的一種排序方法。下面，我們通過大頂堆來實現。
基本思想：堆排序可以按照以下步驟來完成：
1.首先將序列構建稱為大頂堆；（這樣滿足了大頂堆那條性質：位於根節點的元素一定是當前序列的最大值）
2. 取出當前大頂堆的根節點，將其與序列末尾元素進行交換；（此時：序列末尾的元素為已排序的最大值；由於交換了元素，當前位於根節點的堆並不一定滿足大頂堆的性質）
3. 對交換後的n-1個序列元素進行調整，使其滿足大頂堆的性質；
4. 重複2.3步驟，直至堆中只有1個元素為止
下面是基於大頂堆的堆排序算法代碼：
void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl;}/** * 已知H[s…m]除了H[s] 外均滿足堆的定義 * 調整H[s],使其成為大頂堆.即將對第s個結點為根的子樹篩選, * * @param H是待調整的堆數組 * @param s是待調整的數組元素的位置 * @param length是數組的長度 */void HeapAdjust(int H[],int s, int length){ int tmp = H[s]; int child = 2*s+1; while (child < length) { if(child+1 <length && H[child]<H[child+1]) { ++child ; } if(H[s]<H[child]) { H[s] = H[child]; s = child; child = 2*s+1; } else { break; } H[s] = tmp; } print(H,length);}
/** * 初始堆進行調整 * 將H[0..length-1]建成堆 * 調整完之後第一個元素是序列的最小的元素 */void BuildingHeap(int H[], int length){ for (int i = (length -1) / 2 ; i >= 0; --i) HeapAdjust(H,i,length);}/** * 堆排序算法 */void HeapSort(int H[],int length){ BuildingHeap(H, length); for (int i = length - 1; i > 0; --i) { int temp = H[i]; H[i] = H[0]; H[0] = temp; HeapAdjust(H,0,i); }}
int main(){ int H[10] = {3,1,5,7,2,4,9,6,10,8}; cout<<"初始值："; print(H,10); HeapSort(H,10); cout<<"結果："; print(H,10);
} 五、冒泡排序（Bubble Sort）
算法思想：
冒泡遍歷所有的數據，每次對相鄰元素進行兩兩比較，如果順序和預先規定的順序不一致，則進行位置交換；這樣一次遍歷會將最大或最小的數據上浮到頂端，之後再重複同樣的操作，直到所有的數據有序。這個算法的名字由來是因為越大的元素會經由交換慢慢「浮」到數列的頂端。
算法代碼：
void bubbleSort(int a[], int n){ for(int i =0 ; i< n-1; ++i) { for(int j = 0; j < n-i-1; ++j) { if(a[j] > a[j+1]) { int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp; } } }}六、快速排序（Quick Sort）
算法思想：
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n logn)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
算法步驟：
從數列中挑出一個元素，稱為 「基準」（pivot）。
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。
算法代碼：
void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl;}
void swap(int *a, int *b){ int tmp = *a; *a = *b; *b = tmp;}
int partition(int a[], int low, int high){ int privotKey = a[low]; while(low < high){ while(low < high && a[high] >= privotKey) --high; swap(&a[low], &a[high]); while(low < high && a[low] <= privotKey ) ++low; swap(&a[low], &a[high]); } print(a,10); return low;}
void quickSort(int a[], int low, int high){ if(low < high){ int privotLoc = partition(a, low, high); quickSort(a, low, privotLoc -1); quickSort(a, privotLoc + 1, high); }}
int main(){ int a[10] = {3,1,5,7,2,4,9,6,10,8}; cout<<"初始值："; print(a,10); quickSort(a,0,9); cout<<"結果："; print(a,10);
}七、歸併排序（Merge Sort）
算法思想：
歸併排序（Merge sort）是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
算法步驟：
申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列；
設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置；
重複步驟3直到某一指針達到序列尾；
將另一序列剩下的所有元素直接複製到合併序列尾。
算法代碼：
void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl;}
void Merge(ElemType *r,ElemType *rf, int i, int m, int n){ int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; print(rf,n+1);}
void MergeSort(ElemType *r, ElemType *rf, int lenght){ int len = 1; ElemType *q = r ; ElemType *tmp ; while(len < lenght) { int s = len; len = 2 * s ; int i = 0; while(i+ len <lenght){ Merge(q, rf, i, i+ s-1, i+ len-1 ); i = i+ len; } if(i + s < lenght){ Merge(q, rf, i, i+ s -1, lenght -1); } tmp = q; q = rf; rf = tmp; }}
int main(){ int a[10] = {3,1,5,7,2,4,9,6,10,8}; int b[10]; MergeSort(a, b, 10); print(b,10); cout<<"結果："; print(a,10);}八、基數排序(Radix Sort)
算法思想：
基數排序：通過序列中各個元素的值，對排序的N個元素進行若干趟的「分配」與「收集」來實現排序。
分配：我們將L[i]中的元素取出，首先確定其個位上的數字，根據該數字分配到與之序號相同的桶中 。
收集：當序列中所有的元素都分配到對應的桶中，再按照順序依次將桶中的元素收集形成新的一個待排序列L[ ] 。
對新形成的序列L[]重複執行分配和收集元素中的十位、百位...直到分配完該序列中的最高位，則排序結束。
算法代碼：
Void RadixSort(Node L[],length,maxradix){ int m,n,k,lsp; k=1;m=1; int temp[10][length-1]; Empty(temp); while(k<maxradix) { for(int i=0;i<length;i++) { if(L[i]<m) Temp[0][n]=L[i]; else Lsp=(L[i]/m)%10; Temp[lsp][n]=L[i]; n++; } CollectElement(L,Temp); n=0; m=m*10; k++; }}四、使用Python實現● 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。● 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。● 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
def bubble_sort(numberlist): length = len(numberlist) for i in range(length): for j in range(1, length - i): if numberlist[j - 1] > numberlist[j]: numberlist[j], numberlist[j - 1] = numberlist[j - 1], numberlist[j] return numberlist選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。def findSmallest(arr): # 用於查找出數組中最小的元素，返回最小元素的索引。 smallest = arr[0] smallest_index = 0 for i in range(1, len(arr)): if smallest > arr[i]: smallest = arr[i] smallest_index = i return smallest_index
def selectSort(arr): newArr = [] while arr: smallest = findSmallest(arr) newArr.append(arr.pop(smallest)) return newArr
● 從第一個元素開始，該元素可以認為已經被排序
● 取出下一個元素，在已經排序的元素序列中從後向前掃描
● 如果該元素（已排序）大於新元素，將該元素移到下一位置
● 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
● 將新元素插入到該位置後def insert_sort(data): for k in range(1, len(data)): cur = data[k] j = k while j > 0 and data[j - 1] > cur: data[j] = data[j - 1] j -= 1 data[j] = cur return data希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後算法再取越來越小的步長進行排序，算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。def shell_sort(numberlist): length = len(numberlist) gap = length // 2 while gap > 0: for i in range(gap, length): temp = numberlist[i] j = i while j >= gap and numberlist[j - gap] > temp: numberlist[j] = numberlist[j - gap] j -= gap numberlist[j] = temp gap = gap // 2 return numberlist原理如下（假設序列共有{displaystyle n}個元素）：● 將序列每相鄰兩個數字進行歸併操作，形成{displaystyle ceil(n/2)}個序列，排序後每個序列包含兩/一個元素● 若此時序列數不是1個則將上述序列再次歸併，形成{displaystyle ceil(n/4)}個序列，每個序列包含四/三個元素● 重複步驟2，直到所有元素排序完畢，即序列數為1def merge(left, right): result = [] while left and right: if left[0] < right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)) if left: result += left if right: result += right return result
def merge_sort(numberlist): if len(numberlist) <= 1: return numberlist mid = len(numberlist) // 2 left = numberlist[:mid] right = numberlist[mid:]
left = merge_sort(left) right = merge_sort(right) return merge(left, right)從數列中挑出一個元素，稱為「基準」（pivot），
● 重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（相同的數可以到任何一邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）操作。
● 遞歸地（recursively）把小於基準值元素的子數列和大於基準值元素的子數列排序。
● 遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。def quick_sort(array): if len(array) < 2: return array else: pivot = array[0] less = [i for i in array[1:] if i <= pivot] greater = [i for i in array[1:] if i > pivot] return quick_sort(less) + [pivot] + quick_sort(greater)若以升序排序說明，把數組轉換成最大堆積(Max-Heap Heap)，這是一種滿足最大堆積性質(Max-Heap Property)的二叉樹：對於除了根之外的每個節點i, A[parent(i)] ≥ A[i]。重複從最大堆積取出數值最大的結點(把根結點和最後一個結點交換，把交換後的最後一個結點移出堆)，並讓殘餘的堆積維持最大堆積性質。def heap_sort(numberlist): length = len(numberlist) def sift_down(start, end): root = start while True: child = 2 * root + 1 if child > end: break if child + 1 <= end and numberlist[child] < numberlist[child + 1]: child += 1 if numberlist[root] < numberlist[child]: numberlist[root], numberlist[child] = numberlist[child], numberlist[root] root = child else: break
# 創建最大堆 for start in range((length - 2) // 2, -1, -1): sift_down(start, length - 1)
# 堆排序 for end in range(length - 1, 0, -1): numberlist[0], numberlist[end] = numberlist[end], numberlist[0] sift_down(0, end - 1)
return numberlistdef counting_sort(numberlist, maxnumber): # maxnumber為數組中的最大值 length = len(numberlist) # 待排序數組長度 b = [0 for i in range(length)] # 設置輸出序列，初始化為0 c = [0 for i in range(maxnumber+ 1)] # 設置技術序列，初始化為0 for j in numberlist: c[j] = c[j] + 1 for i in range(1, len(c)): c[i] = c[i] + c[i - 1] for j in numberlist: b[c[j] - 1] = j c[j] = c[j] - 1 return b五、總結
所以對n較大的排序記錄。一般的選擇都是時間複雜度為O(nlog2n)的排序方法。(3)O(n1+§))排序,§是介於0和1之間的常數。(4)線性階(O(n))排序
基數排序，此外還有桶、箱排序。當原表有序或基本有序時，直接插入排序和冒泡排序將大大減少比較次數和移動記錄的次數，時間複雜度可降至O（n）；而快速排序則相反，當原表基本有序時，將蛻化為冒泡排序，時間複雜度提高為O（n2）；原表是否有序，對簡單選擇排序、堆排序、歸併排序和基數排序的時間複雜度影響不大。排序算法的穩定性:若待排序的序列中，存在多個具有相同關鍵字的記錄，經過排序， 這些記錄的相對次序保持不變，則稱該算法是穩定的；若經排序後，記錄的相對 次序發生了改變，則稱該算法是不穩定的。
穩定性的好處：排序算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩定，可以避免多餘的比較；
穩定的排序算法：冒泡排序、插入排序、歸併排序和基數排序不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序每種排序算法都各有優缺點。因此，在實用時需根據不同情況適當選用，甚至可以將多種方法結合起來使用。影響排序的因素有很多，平均時間複雜度低的算法並不一定就是最優的。相反，有時平均時間複雜度高的算法可能更適合某些特殊情況。同時，選擇算法時還得考慮它的可讀性，以利於軟體的維護。一般而言，需要考慮的因素有以下四點：2．記錄本身數據量的大小，也就是記錄中除關鍵字外的其他信息量的大小；1）當n較大，則應採用時間複雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸併排序序。快速排序：是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
歸併排序：它有一定數量的數據移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然後再合併，在效率上將有所提高。2） 當n較大，內存空間允許，且要求穩定性 =》歸併排序直接插入排序：當元素分布有序，直接插入排序將大大減少比較次數和移動記錄的次數。直接選擇排序 ：元素分布有序，如果不要求穩定性，選擇直接選擇排序 3、如果是數字時，最好是無符號的，否則將增加相應的映射複雜度，可先將其正負分開排序。以上所述是小編給大家介紹的必須知道的C語言 八大排序算法(收藏)，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對腳本之家網站的支持！‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ END ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧