文章目錄

• 一、排序算法概覽
• 二、算法實現
• • 1、選擇排序
  • 2、冒泡排序
  • 3、插入排序
  • 4、快速排序
  • 5、希爾排序
  • 6、桶排序（基數排序）
  • 7、歸并排序
  • 8、堆排序
• 三、總結

---

一、排序算法概覽

可以在VisuAlgo或者站長輔助工具中查看這些排序算法的動態演示過程

二、算法實現

1、選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

void selectSort(ElemType arr[], int len) //選擇排序 {int temp;for (int i = 0; i < len - 1; ++i){for (int j = i + 1; j < len; ++j){if (arr[i]>arr[j]){temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}} }

2、冒泡排序

冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端。

冒泡排序改進1：在某次遍歷中如果沒有數據交換，說明整個數組已經有序。因此通過設置標志位來記錄此次遍歷有無數據交換就可以判斷是否要繼續循環。

冒泡排序改進2：記錄某次遍歷時最后發生數據交換的位置，這個位置之后的數據顯然已經有序了。因此通過記錄最后發生數據交換的位置就可以確定下次循環的范圍了。

void bulletSort(ElemType arr[], int len) //冒泡排序 {int temp;for (int i = 0; i < len - 1; ++i){for (int j = 0; j < len - 1 - i; ++j){if (arr[j]>arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}

3、插入排序

插入排序基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用于少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。

void insertSort(ElemType arr[], int len) //插入排序 {int temp,j,i;//形式1for (i = 1; i < len; ++i){temp = arr[i];j = i - 1;while (j >= 0 && temp < arr[j])//j指向的是有序序列{arr[j + 1] = arr[j];--j;} arr[j + 1] = temp;}//形式2//for (i = 1; i < len; ++i)//{// temp = arr[i];// for (j = i - 1; j >= 0 && temp < arr[j]; --j)//j指向的是有序序列// {// arr[j + 1] = arr[j];// }// arr[j + 1] = temp;//}//形式3/*for (i = 1; i < len; ++i){temp = arr[i];for (j = i - 1; j >= 0; --j){if (temp < arr[j]){arr[j + 1] = arr[j];}elsebreak;}arr[j + 1] = temp;}*///形式4/*for (int i = 1; i < len; ++i){for (int j = i - 1; j >= 0; --j){if (arr[j + 1] < arr[j]){temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}elsebreak;}}*/ }

4、快速排序

快速排序（Quicksort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

void quickSort(ElemType arr[], int left, int right)//快速排序 {int i = left, j = right;int temp;if (left >= right) return;while (i <= j){while (i <= j&&arr[left] >= arr[i]) ++i;//找出左邊比arr[left]大的元素while (i <= j&&arr[left] <= arr[j]) --j;//找出右邊比arr[left]小的元素if (i < j)//交換找到的元素{temp = arr[i];arr[i] = arr[j];arr[j] = temp;i++;//交換完之后移向下一個位置--j;}}//經過循環后在j位置就是標桿的位置，這個位置左邊都不大于該值，該位置右邊都不小于該值temp = arr[left];arr[left] = arr[j];arr[j] = temp; //交換quickSort(arr, left, j - 1); //遞歸操作左邊元素quickSort(arr, j+1, right); //遞歸操作右邊元素}

5、希爾排序

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

void shellSort(ElemType arr[], int len) //希爾排序 {int d = len / 2; //分組(增量置初值)int i, j;int temp;while (d > 0) //由希爾排序要進行的次數來決定（每一次都有相應的分組情況，即有不同的增值）{for (i = d; i < len; ++i) // 對該次希爾排序（分組情況）進行插入排序（由要進行插入排序的元素個數來決定）//本來一個插入排序從1開始，這里有d組插入排序，所以從d開始 //這個是d組一起進行插入排序，即等到每一組都插入第i個元素后，才會進行插入第i+1個元素{temp = arr[i];for (j = i - d; j >= 0 && temp < arr[j]; j = j - d) //將每次的元素插入(由有序元素的個數來決定)arr[j + d] = arr[j];arr[j + d] = temp;}d = d / 2; //從新分組} }

6、桶排序（基數排序）

基數排序，第一步根據數字的個位分配到每個桶里，在桶內部排序，然后將數字再輸出（串起來）；然后根據十位分桶，繼續排序，再串起來。直至所有位被比較完，所有數字已經有序。

void radixSort(ElemType arr[], int len)//桶排序（基數排序） {int temp[10][20];int index;for (int n = 1; n <= 100; n *= 10)//數據中最大數是幾位，就要進行幾次循環{for (int x = 0; x < 10; ++x) //初始化 為了方便查找到存放的數據{for (int y = 0; y < 20; ++y){temp[x][y] = -1;}}for (int i = 0; i < len; ++i) //存放數據{index = (arr[i] / n) % 10;temp[index][i] = arr[i];}int count = 0;for (int i = 0; i < 10; ++i) //將該次排序后的結果放回原數組{for (int j = 0; j < 20; ++j){if (temp[i][j] != -1)arr[count++] = temp[i][j];}}} }

7、歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

void mergeInArr(ElemType arr[], int left, int mid, int right) {//注意此時左右空間都是各自有序int length = right - left + 1; //輔助數組長度int *p = new int[length]; //構建輔助數組memset(p, 0, sizeof(int)*length); //給輔助數組賦值int low = left; //記錄左區間的起始位置int hig = mid + 1; //記錄右區間的起始位置 int index = 0; //輔助空間下標while (low <= mid&&hig <= right) //左右區間都沒有比較完，都有數據{while (low <= mid&&arr[low] <= arr[hig])//如果左邊區間沒有越界，并且左區間的數值<=右區間的數值p[index++] = arr[low++]; //將小的數據存入輔助空間while (hig <= right&&arr[low] > arr[hig]) //如果右邊區間沒有越界，并且左區間的數值>右區間的數值p[index++] = arr[hig++]; //將小的數據存入輔助空間}//到這一步，證明起碼有一個區間是合并進了輔助數組if (hig <= right)//證明右區間并沒有完成合并，左區間是完成合并，把右區間剩下的數據直接拷貝到輔助數組即可(此時右區間剩下的數據比輔助空間的數據大)memcpy(&p[index], &arr[hig], sizeof(int)*(right - hig + 1));if (low <= mid)memcpy(&p[index], &arr[low], sizeof(int)*(mid - low + 1));//將排完序的值傳回給原數組memcpy(&arr[left], p, sizeof(int)*length); //這里&arr[left]要特別注意，不能寫成arrdelete[]p;}void merge(ElemType arr[], int left, int right) {int mid;if (left >= right) return; //遞歸出口 這里就不需要遞歸了mid = ((right - left) >> 1) + left; //查找到中間值 將數組分成兩部分 左區間和右區間//************ 歸操作 **********//merge(arr, left, mid); //左區間 merge(arr, mid + 1, right); //右區1間//************** 并操作 **************//mergeInArr(arr, left, mid, right); //將歸操作后單個有序區間合并}void mergeSort(ElemType arr[], int len) {merge(arr, 0, len - 1);//歸并排序 }

函數說明
（1）使用以下函數需要加頭文件#include<memory.h>
（2）memset 函數：內存逐字節賦值，有三個參數，第一個參數是哪個內存，第二個參數賦什么值，第三個參數這個內存需要賦多大的內存。
（3）memcpy內存拷貝函數，有3個參數，表示把第二個參數的首地址里面的內容拷貝到第一個參數表示的首地址里面，拷貝大小為第三個參數表示的大小

8、堆排序

堆的插入就是——每次插入都是將新數據放在數組最后，而從這個新數據的父結點到根結點必定是一個有序的數列，因此只要將這個新數據插入到這個有序數列中即可。

堆的刪除就是——堆的刪除就是將最后一個數據的值賦給根結點，然后再從根結點開始進行一次從上向下的調整。調整時先在左右兒子結點中找最小的，如果父結點比這個最小的子結點還小說明不需要調整了，反之將父結點和它交換后再考慮后面的結點。相當于從根結點開始將一個數據在有序數列中進行“下沉”。

因此，堆的插入和刪除非常類似直接插入排序，只不是在二叉樹上進行插入過程。所以可以將堆排序形容為“樹上插”

更加詳細的過程可以查看博文：堆排序算法（圖解詳細流程）

//堆排序public static void heapSort(int[] arr) {//構造大根堆heapInsert(arr);int size = arr.length;while (size > 1) {//固定最大值swap(arr, 0, size - 1);size--;//構造大根堆heapify(arr, 0, size);}}//構造大根堆（通過新插入的數上升）public static void heapInsert(int[] arr) {for (int i = 0; i < arr.length; i++) {//當前插入的索引int currentIndex = i;//父結點索引int fatherIndex = (currentIndex - 1) / 2;//如果當前插入的值大于其父結點的值,則交換值，并且將索引指向父結點//然后繼續和上面的父結點值比較，直到不大于父結點，則退出循環while (arr[currentIndex] > arr[fatherIndex]) {//交換當前結點與父結點的值swap(arr, currentIndex, fatherIndex);//將當前索引指向父索引currentIndex = fatherIndex;//重新計算當前索引的父索引fatherIndex = (currentIndex - 1) / 2;}}}//將剩余的數構造成大根堆（通過頂端的數下降）public static void heapify(int[] arr, int index, int size) {int left = 2 * index + 1;int right = 2 * index + 2;while (left < size) {int largestIndex;//判斷孩子中較大的值的索引（要確保右孩子在size范圍之內）if (arr[left] < arr[right] && right < size) {largestIndex = right;} else {largestIndex = left;}//比較父結點的值與孩子中較大的值，并確定最大值的索引if (arr[index] > arr[largestIndex]) {largestIndex = index;}//如果父結點索引是最大值的索引，那已經是大根堆了，則退出循環if (index == largestIndex) {break;}//父結點不是最大值，與孩子中較大的值交換swap(arr, largestIndex, index);//將索引指向孩子中較大的值的索引index = largestIndex;//重新計算交換之后的孩子的索引left = 2 * index + 1;right = 2 * index + 2;}}//交換數組中兩個元素的值public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

三、總結

此處使用More Windows圖解來對上述的算法進行總結，如果對圖解中算法的含義不是很理解可以參考博文：各個排序算法的時間復雜度和穩定性，快排的原理

排序圖表

More Windows圖解七種經典的排序算法

總結

以上是生活随笔為你收集整理的常用排序算法总结（C语言版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。