希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數gap，把待排序文件中所有數據分成幾個組，所有距離為gap的數據分在同一組內，并對每一組內的數據進行排序。然后gap減減，重復上述分組和排序的工作。當到達gap=1時，所有數據在同一組內排好序（gap==1時就是上次講的插入排序）。
希爾排序舉例：
#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{assert(arr);for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}
// 希爾排序
// 時間復雜度 O（N^1.3-N^2)
// gap越大，前面大的數據可以越快排到后面，后面小的數可以越快拍到前面，gap越大，越不接近有序
// gap越小越接近有序，如果gap==1其實就是直接插入排序，就有序了
void ShellSort(int* arr, int n)
{assert(arr);int gap = n;// gap>1相當于預排序，讓數組接近有序// gap==1就相當于直接插入排序，保證有序while (gap > 1){gap = gap / 3 + 1; // +1是保證了最后一次gap一定是1// 注意結束條件，防止造成越界訪問（畫圖）for (int i = 0;i < n - gap;i++) // 多趟并排{// 單趟排序int end = i; // 當end==0時就是單趟排序，排間距為gap的那一趟int temp = arr[end + gap]; // 將新的排序數值存起來，方便每次比較大小while (end >= 0) {if (temp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp; // 跳出循環后temp放到end+gap位置}// 打印每一個gap時的排序狀態Printarry(arr, n);}}void TestShellSort()
{int arr[] = { 3,1,4,2,8,4,9,6,0,7 };Printarry(arr, sizeof(arr) / sizeof(arr[0]));ShellSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{TestShellSort();return 0;
}
選擇排序
每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置（末尾位置），直到全部待排序的 數據元素排完 。
直接選擇排序:
在元素集合arr[i]--arr[n-1]中選擇最大(小)的數據?若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素。
舉例：利用雙指方法，begin指向首元素，end指向末尾元素，找到最大值時maxi和end位置數據互換，最小值mini位置和begin位置數據互換。
當begin和maxi重疊時，mini位置的數據和begin位置的數據互換后要將mini的值給到maxi，在將maxi位置的數據和end位置的數據互換。
#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{assert(arr);for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}
// 選擇排序
// 空間復雜度為O（1）
// 時間復雜度為 O（N^2）,最好的情況是接近有序比較n次即可，最壞的是不完全有序接近無順序
void SelectSort(int* arr, int n)
{assert(arr);int begin = 0;int end = n - 1;//int mini = 0;//int maxi = 0;while (begin < end){int mini = 0;int maxi = 0;maxi = mini = begin;// 在[begin，end]之間選出最大值和最小值for (int i = begin + 1;i <= end;++i){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}Swap(&arr[begin], &arr[mini]);// 如果maxi與begin位置重疊的話要修正maxi的位置if (begin == maxi)maxi = mini;Swap(&arr[end], &arr[maxi]);--end;++begin;}
}void TestSelectSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };SelectSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{TestShellSort();return 0;
}計數排序
首先找到待排序數組的最大值和最小值，然后開辟一個空間temp數組，大小為最大值減去最小值加1；然后遍歷數組，將數據出現的次數放到temp數組相對位置中；然后再遍歷temp數組取出對應數據出現的次數，將該數據依次覆蓋回原數組中。
注意：這個排序缺點就是浪費空間比如，待排序數組最小值為100，最大值為1000；那么要開辟0-1000個空間的數組，才能存放比如100出現10次，那么temp數組中下標100位置就存放10，這樣就很浪費空間。我們在這里開辟900個空間的數組，將100出現的次數放到相對位置中，相對位置為：100-min。覆蓋回原數組的時候再加上min即可。相對減少空間浪費。
舉例子：
#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{assert(arr);for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}
// 計數排序
// 時間復雜度O(N+range)
// 空間復雜度O(range)
void CountSort(int* arr, int n)
{// 找出最大最小值int min = arr[0];int max = arr[0];for (int i = 1;i < n;i++){if (arr[i] > max)max = arr[i];if (arr[i] < min)min = arr[i];}// 創建計數的空間int range = max - min + 1;int* countArr = (int*)malloc(sizeof(int) * range);memset(countArr, 0, sizeof(int) * range); // 將數組元素置為0// 遍歷數組將相同的數值出現的次數放到相對位置處：arr[i] - minfor (int i = 0;i < n;i++){countArr[arr[i] - min]++;}// 遍歷countArr數組將某個數出現的次數，依次將這個數放回到原數組int index = 0;for (int i = 0;i < range;i++){while (countArr[i]--) // 控制數據出現的次數{arr[index++] = i + min;}}
}void TestCountSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };CountSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{TestCountSort();return 0;
}
)
