目錄
1、插入排序
2、希爾排序
3、堆排序
4、直接選擇排序
5、快排
6、歸并排序
補：計數排序
1、插入排序
void InsertSort(int* arr, int n)
{int i = 0;for (int i = 0; i + 1 < n; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}}?另一種寫法
INSERTION-SORT
源碼
for j=2 to A.legthkey=A[j]i=j-1whlie i>0 and A[i]>keyA[i+1]=A[i]i=i-1A[i+1]=key
插入排序
比方說手上有6張撲克牌-5 2 4 6 1 3通過插入排序
即從j=2開始（key=2）比較key與A[i] (i=j-1也就是2這張牌的前一張牌5比較)并完成交換數值
把第一張key排好后j++=3再來循環
c語言實現
#include<stdio.h>int main()
{int j ;int arr[6] = { 5，2，4，6，1，3 };int sz = sizeof(arr) / sizeof(arr[0]);for (j=1; j < sz; j++){int key = arr[j];int i = j - 1; //arr[i]>arr[j]不行嗎while (i >=0 && arr[i] > key)//升序排列{arr[i + 1] = arr[i];//為什么不能寫成arr[j]=arr[i]i = i - 1;}arr[i + 1] = key;}return 0;
}
- arr[i]比較的是key的值，而不是arr[j]的值，因為arr[j]在while循環中會改變
- 同理
2、希爾排序
希爾排序法?稱縮?增量法。希爾排序法的基本思想是：先選定?個整數（通常是gap=n/3+1），把 待排序?件所有記錄分成各組，所有的距離相等的記錄分在同?組內，并對每?組內的記錄進?排 序，然后gap=gap/3+1得到下?個整數，再將數組分成各組，進?插?排序，當gap=1時，就相當于 直接插?排序。它是在直接插?排序算法的基礎上進?改進?來的，綜合來說它的效率肯定是要?于直接插?排序算法的。
每一組的排序都是插入排序
int gap = n / 3 + 1;
for (int i = 0; i + gap < n; i+gap)
{int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end-=gap;}else{break;}}arr[end + gap] = tmp;
}完整代碼
void ShellSort(int* arr, int n)
{int i = 0;int gap = n;while (gap > 1){gap = gap/3 +1;for ( i = 0; i + gap < n; i ++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}}3、堆排序
void AdjustDown(DataType* arr, int parent, int n)
{int child = 2 * parent + 1;while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * child + 1;}else{break;}}
}void HeapSort(int* arr, int n)
{int i = 0;//用向下調整算法建堆//循環從下至上for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}}4、直接選擇排序
未優化
void SelectSort1(int* arr, int n)
{int mini;for (int i = 0; i < n - 1; i++){mini = i;for (int j = i + 1; j < n; j++){if (arr[j] < arr[mini]){mini = j;}}Swap(&arr[i], &arr[mini]);}
}優化
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int maxi = begin, mini = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}if (begin == maxi){maxi = mini;}Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);++begin;--end;}}5、快排
快速排序是Hoare于1962年提出的?種?叉樹結構的交換排序?法，其基本思想為：任取待排序元素 序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩?序列，左?序列中所有元素均? 于基準值，右?序列中所有元素均?于基準值，然后最左右?序列重復該過程，直到所有元素都排列 在相應位置上為?。
int _QuickSort(int* arr, int left, int right)
{//left從左往右找比基準值大的數據//right從右往左找比基準值小的數據int keyi = left;left++;while (left <= right){while (left <= right &&arr[left] < arr[keyi]){left++;}//left找到了最大位置while (left <= right &&arr[right] > arr[keyi]){right--;}if (left <= right){Swap(&arr[left++], &arr[right--]);}}Swap(&arr[keyi], &arr[right]);return right;
}//雙指針法
int _QuickSort3(int* arr, int left, int right)
{int key = left, slow = left, fast = left + 1;while (fast <= right){if (arr[fast] < arr[key] && ++slow != fast){Swap(&arr[slow], &arr[fast]);}fast++;}Swap(&arr[key], &arr[slow]);return slow;
}void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}int keyi= _QuickSort(arr, left, right);QuickSort(arr, left,keyi-1);QuickSort(arr, keyi+1, right);}
6、歸并排序
void _MergeSort(int* arr,int left,int right,int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;//[left,mid] [mid+1,right]_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//合并//[left,mid] [mid+1,right]int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else {tmp[index++] = arr[begin2++];}}//要么begin1越界 要么begin2越界while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//[left,mid] [mid+1,right]//把tmp中的數據拷貝回arr中for (int i = left; i < right; i++){arr[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}補：計數排序
計數排序?稱為鴿巢原理，是對哈希直接定址法的變形應?。操作步驟：
1）統計相同元素出現次數
2）根據統計的結果將序列回收到原來的序列中
void CountSort(int* arr, int n)
{int max = arr[0], min = arr[0];for (int i = 0; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail:");exit(1);}memset(count, 0, sizeof(int) * range);for (int i = 0; i < n; i++){count[arr[i] - min]++;}int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}
}
