C語言實現經典排序算法的示例代碼
一、冒泡排序
1.原理
從數組的頭開始不斷比較相鄰兩個數的大小，不斷將較大的數右移，一個循環後，最大數移至最後一位，無序數組規模減一。不斷重復前面動作，知道數組完全有序。
2.實現
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void bubble_sort(int* arr, int len)
{
bool issort = false;
while (!issort)
{
issort = true;//如果有序則直接退出
for (int i = 1; i < len; i++)
{
if (arr[i-1] > arr[i])//不斷比較相鄰兩個數
{
swap(&arr[i - 1], &arr[i]);//將較大的數不斷往右移
issort = false;//如果進行瞭交換則無序
}
}
len--;//無序規模減一
}
}
3.算法分析
時間復雜度： 最好情況，當數組完全有序，則隻需要進行一輪比較，時間復雜度為o(n)；最壞情況為完全無序，每次比較後都要將該數移至數組末尾，時間復雜度為o(n ^2)；平均時間復雜度為o(n ^2)。
空間復雜度： 冒泡排序為就地排序,空間復雜度為o(1)。
穩定排序： 當數字相同時不會改變相對次序。
二、選擇排序
1.原理
數組前面為無序，後面為有序。剛開始全是無序，從中選擇一個最大值與最後一個無序數字進行交換，無序數組規模減一，有序數組規模加一。不斷循環前面操作，直到數組變為有序數組。或者前面為有序數組，後面為無序數組，不斷選擇最小值與無序數組的第一個數交換，前面的有序數組加一，後面的無序數組減一。
2.實現
void selection_sort(int* arr, int len)
{
int max_index;
while (len)
{
max_index = 0;
for (int i = 1; i < len; i++)
{
if (arr[max_index] < arr[i])
{
max_index = i;//獲取最大值的索引
}
}
swap(&arr[max_index], &arr[len - 1]);//將最大值與最後一個值交換
len--;//無序規模減一
}
}
3.算法分析
時間復雜度： 所有的復雜度為每次選擇最大值，不管數字的有序性，時間復雜度都為o(n)+o(n-1)+…+o(1)=o(n^2)。所以該算法平均復雜度、最好情況、最差情況都為o(n ^2)。
空間復雜度： 就地排序，空間復雜度為o(1)。
不穩定性算法： 排序後相同元素的順序可能被打亂。例子：選擇最大進行排序。3,1,2,2* 第一輪排序後 2*,1,2,3 2的相對順序發生瞭改變。選擇最小進行排序，2*,2,3,1 第一輪排序後1,2,3,2*. 2的相對順序也被打亂。如果增加空間復雜度也能將選擇排序變成穩定性排序。
三、插入排序
1.原理
數組前面為有序，後面為無序，將無序數組中的第一個數不斷插入有序數組中（具體實現為不斷比較相鄰兩數大小，前面一個數大於後一個數，則交換順序，較小的數不斷前移），有序規模增加一，無序規模減小一。或者，數組前面為無序，後面為有序，通過將無序數組的最後一位數字插入有序數組中（具體實現為將無序數組的最後一位與相鄰的有序數組不斷比較，將無序數組不斷右移）。
2.實現
void insert_sort(int arr[], int len)
{
for (int i = 1; i < len; i++)//i前面為有序
{
for (int j = i - 1; j >= 0; j--)//j為有序數的末尾
{
bool issort = true;//當數組有序時能夠提前退出
if (arr[j] > arr[j + 1])//將無序數組的第一個數不斷與有序數組比較
{
swap(&arr[j], &arr[j + 1]);//將無序數字插入有序數組合適的位置
issort = false;
}
if (issort) break;
}
}
}
3.算法分析
時間復雜度： 插入排序和冒泡排序類似，最好情況完全有序則時間復雜度為o(n)，最壞情況為完全無序時間復雜度為o(n^2)，平均復雜度為o(n ^2)。
空間復雜度： 就地排序不需要額外空間，空間復雜度為o(1)。
穩定性排序： 和冒泡排序類似。
四、希爾排序
1.原理
每次選擇一個增量進行分組，增量不斷減小到一（為插入排序），數組不斷變得有序，增量為一時變成完全有序。屬於插入排序的改進，通過增量進行分組，對每一組進行插入排序，相比於插入排序的優勢在於，shell排序能夠大尺度的移動每一組的最小值，而插入排序得挨著進行比較，所以shell排序效率更高。
增量為6：
每一組隻有兩個數，分別比較兩個數的大小，如64,57交換順序變成57,64，所有的分組比較完後繼續縮減增量。
增量為3：
每一組有四個數，總共三組，分別為23,12,53,79；57,9,64,87；24,16,71,97；以增量開始（12開始）遍歷數組，遍歷到12則在第一組中對12進行插入排序，交換23和12的順序；遍歷到9則在第二組對9進行插入排序。。。。遍歷到64對一組中的9,57,64進行插入排序。最後每一組都變得有序。整體有序性變大。
增量為1：
對之前排序過的數組進行插入排序，通過前面的步驟數組有序性變大，最後進行插入排序的效率就更高。
2.實現
void shell_sort(int* arr, int len)
{
int gap = 0; //分組的跨度
int i = 0;
int j = 0;
for (gap = len / 2; gap >= 1; gap /= 2) //分組增量
{
for (i = gap; i < len; i++) { //遍歷每組
for (j = i - gap; j >= 0; j -= gap) //對組內進行插入排序
{
if (arr[j] > arr[j + gap])
{
swap(&arr[j], &arr[j + gap]);
}
}
}
}
}
3.算法分析
時間復雜度：最好情況為完全有序o(n),最差情況為完全無序o(n^2)，平均復雜度為o(n ^1.3)。
空間復雜度：該算法為就地排序空間復雜度為o(1)。
穩定性：shell排序在分組中可能將相同數字劃分成不同的分組，會改變相對順序，屬於不穩定性排序算法。
總結
冒泡排序、選擇排序、插入排序、希爾排序的實現都是基於線性表進行實現的（數組或者鏈表），實現邏輯都是通過比較數字的大小。算法的時間復雜度都比較大，但是屬於就地排序，不需要額外空間。幾種算法相比之下希爾排序更具有優勢。
到此這篇關於C語言實現經典排序算法的示例代碼的文章就介紹到這瞭,更多相關C語言排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！