大家好，我是纪宁，这篇文章是关于八大排序的源代码，具体实现过程会在后续文章中介绍。
1、直接插入排序
时间复杂度O(N^2)，原数据越有序，效率越高。
当原数据有序时，则时间复杂度为O(N)。原数据倒序时，时间复杂度为O(N^2)
void InsertSort(int* a, int n)//直接插入排序 { for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[end+1]; while (end >= 0) { if (a[end] >tmp) { a[end + 1] = a[end]; } else { break; } end--; } a[end + 1] = tmp; } }
2、希尔排序
时间复杂度：O(N^1.3) 空间复杂度：O(1)
希尔排序是插入排序的优化，整体思路是先预排序，使原数据更接近有序，等到gap==1时，就变成了直接插入排序。
void ShellSort(int* arr, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1;//gap也可以 /=2；奇特数字必须保证gap最后的值为1 for (int i = 0; i < n - gap; i++) { int end = i; int tmp = arr[end + gap]; while (end >= 0) { if (tmp < arr[end]) { arr[end + gap] = arr[end]; } else { break; } end -= gap; } arr[end + gap] = tmp; } } }
3、选择排序
时间复杂度：O(N^2) 空间复杂度：O(1)
每次选择一个最大或者最小的数，使其出现在正确的位置。
void SelectSort(int* a, int n) { for (int j = 0; j < n; j++) { int mini = j; int maxi= n - j-1; for (int i = j; i < n-j; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } Swap(&a[mini], &a[j]); if (maxi == j) { maxi = mini;//最大值如果在 j 这个位置的话，结果这个位置被换成了min 的值 } Swap(&a[maxi], &a[n-1-j]); } }
4、冒泡排序
时间复杂度：O(N^2) 空间复杂度：O(1)
思路最简单的排序，所有程序员的白月光！
void BubbleSort(int* a, int n)//冒泡排序 { for (int i = 0; i < n; i++) { int ret = 0;//如果一趟后ret还等于0，说明数据已经有序 for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); ret = 1; } } if (ret == 0) break; } }
5、堆排序
时间复杂度：O(N*logN) 空间复杂度：O(1)
建堆的时候可以采用向上调整和向下调整建堆，而排序的时候只能使用向下调整算法。
排升序建大堆，降序建小堆。
void Adjustup(int* a, int child)//向上调整 { int parent = (child - 1) / 2; while (parent >= 0) { if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void Adjustdown(int* a, int parent, int n)//向下调整 { int child = 2 * parent + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) { child++; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } void HeapSort(int* arr, int sz) { //第一步，建堆 向上调整建堆 //for (int i = 1; i < sz; i++) //{ // Adjustup(arr, i); //} //向下调整建堆 for (int i = (sz - 1) / 2; i >= 0; i--) { Adjustdown(arr, i, sz - 1); } int end = sz - 1; while (end > 0) { Swap(&arr[0], &arr[end]); Adjustdown(arr, 0, end); end--; } }
6、快速排序
时间复杂度：O(N*logN) 空间复杂度：O(1)
快速排序递归实现
霍尔法
int QuickSortPart1(int*a,int left,int right)//霍尔版本 { int* Maxi = (&a[left], &a[right], &(a[(left + right) / 2]));//三数取中 Swap(&a[left], Maxi);//换到最左边 int key = a[left]; int keyi = left; while (left<right) { while (left<right && a[right]>=key) { right--; } while (left < right && a[left] <= key) { left++; } Swap(&a[left], &a[right]); } Swap(&a[keyi], &a[left]); return left; } void QuickSort(int*arr, int begin, int end) { if (begin >= end)//等于是只有一个数需要排，大于是没有数需要排 { return; } int keyi = QuickSortPart1(arr, begin, end); /*int keyi = QuickSortPart2(arr, begin, end); int keyi = QuickSortPart3(arr, begin, end);*/ QuickSort(arr, begin, keyi - 1); QuickSort(arr, keyi + 1, end); }
挖坑法
int QuickSortPart2(int* arr, int left, int right)//挖坑法 { int* Maxi = (&arr[left], &arr[right], &(arr[(left + right) / 2])); Swap(&arr[left], Maxi); int holei = left; int hole = arr[left]; while (left < right) { while (left < right && arr[right] >= hole) { right--; } arr[holei] = arr[right]; holei = right; while (left < right && arr[left] <= hole) { left++; } arr[holei] = arr[left]; holei = left; } arr[holei] = hole; return left; } void QuickSort(int*arr, int begin, int end) { if (begin >= end)//等于是只有一个数需要排，大于是没有数需要排 { return; } /*int keyi = QuickSortPart1(arr, begin, end);*/ int keyi = QuickSortPart2(arr, begin, end); /*int keyi = QuickSortPart3(arr, begin, end);*/ QuickSort(arr, begin, keyi - 1); QuickSort(arr, keyi + 1, end); }
前后指针法
int QuickSortPart3(int* a, int left, int right)//快排快慢指针 { int* Maxi = (&a[left], &a[right], &(a[(left + right) / 2])); Swap(&a[left], Maxi); int keyi = left; int prev = left; int cur = left+1; while (cur <= right) { if (a[cur] < a[keyi]&& ++prev!= cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev],&a[keyi]); return prev; } void QuickSort(int*arr, int begin, int end) { if (begin >= end)//等于是只有一个数需要排，大于是没有数需要排 { return; } //*int keyi = QuickSortPart1(arr, begin, end);*/ //int keyi = QuickSortPart2(arr, begin, end); int keyi = QuickSortPart3(arr, begin, end); QuickSort(arr, begin, keyi - 1); QuickSort(arr, keyi + 1, end); }
快速排序小区间优化
void QuickSort1(int* a, int begin, int end) { if (begin >= end) return; // 小区间优化，小区间不再递归分割排序，降低递归次数 if ((end - begin + 1) > 10) { int keyi = PartSort3(a, begin, end); // [begin, keyi-1] keyi [keyi+1, end] QuickSort1(a, begin, keyi - 1); QuickSort1(a, keyi + 1, end); } else { InsertSort(a + begin, end - begin + 1);//直接插入排序 } }
快速排序非递归实现
快排非递归要用栈来实现
void QuickSortNorn(int* a, int begin, int end) { ST st;//创建数组栈 STInit(&st);//初始化栈 STPush(&st, end);//入栈 STPush(&st, begin);//入栈 while (!STEmpty(&st))//判空 { int left = STTop(&st);//取栈顶数据 STPop(&st);//出栈 int right = STTop(&st); STPop(&st); int keyi = QuickSortPart1(a, left,right); if (keyi + 1 < right) { STPush(&st, right); STPush(&st, keyi + 1); } if (keyi - 1 > left) { STPush(&st, keyi - 1); STPush(&st, left); } } STDestroy(&st);//销毁栈 }
7、归并排序
时间复杂度：O(N*logN) 空间复杂度：O(N)
归并排序递归实现
void _MergeSortPart(int* a, int* tmp, int begin, int end) { if (begin >= end) return; int midi = (begin + end) / 2; _MergeSortPart(a, tmp, begin, midi); _MergeSortPart(a, tmp, midi + 1, end); int begin1 = begin, end1 = midi; int begin2 = midi + 1, end2 = end; int index = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); _MergeSortPart(a, tmp, 0, n - 1); free(tmp); tmp = NULL; }
归并排序非递归
void _MergeSortNonr(int* a, int* tmp, int begin, int end) { int gap = 1; while (gap <= end) { for (int i = 0; i <= end; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; int index = i; if (begin2 > end) { break; } if (end2 > end) { end2 = end;//对范围进行修正 } while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));//拷贝回原数组 } gap *= 2; } } void MergeSortNonr(int* a, int n)//归并排序非递归 { int* tmp = (int*)malloc(sizeof(int) * n); _MergeSortNonr(a, tmp, 0, n - 1); free(tmp); tmp = NULL; }
8、计数排序
时间复杂度：O(MAX(N,range)) 空间复杂度：O(range)
void CountSort(int* a, int n)//计数排序 { //先找最大值和最小值 int maxi = 0, mini = 0; for (int i = 1; i < n; i++) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } int max = a[maxi], min = a[mini]; int range = a[maxi] - a[mini]+1; int* count = (int*)malloc(sizeof(int) * range); memset(count, 0, sizeof(int) * range); for (int j = 0; j < n; j++) { count[a[j] - min]++; } int i = 0; for (int j = 0; j < n; j++) { while (count[j]--) { a[i++] = j + min; } } }
