七、快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
时间复杂度: O(NlogN) 空间复杂度: O(logN) 稳定性: 不稳定
7.1 Hoare版本
单趟排序图解，如下:
每次单趟排序即可确定一个数的位置，于上图而言即是6。
注意: 若选用最左边的值为key，一定要right先进行移动；若选用最右边的值为key,一定要left先动
以排升序且选用最左边的值为key为例。要确保left与right相遇位置的值小于基准值，就必须让right先进行移动。
情况一: right先移动，停止后left进行移动与right相遇，相遇位置即为right的位置(必然比基准值小)
情况二: right先移动，right在找到比基准值小的值之前与left相遇，相遇位置是left所在的位置，该位置的值是上一轮交换过来的(必然比基准值小)
#include<stdio.h> void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void QuickSort(int* arr, int left, int right) { if (left >= right)return; int begin = left, end = right; int key = begin; while (begin < end) { while (begin < end && arr[end] >= arr[key])//找小 { --end; } while (begin < end && arr[begin] <= arr[key])//找大 { ++begin; } Swap(&arr[begin], &arr[end]); } Swap(&arr[begin], &arr[key]); QuickSort(arr, left, begin - 1); QuickSort(arr, begin + 1, right); } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; QuickSort(arr, 0, (int)(sizeof(arr) / sizeof(int)) - 1); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
7.2 挖坑法
挖坑法本质上与Hoare版本并无不同，只是从思想上而言更容易理解。
单趟排序图解，如下:
#include<stdio.h> void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void QuickSort(int* arr, int left, int right) { if (left >= right)return; int begin = left, end = right; int pivot = begin; int key = arr[begin]; while (begin < end) { //右边找小，放在左边 while (begin < end && arr[end] >= key) { --end; } arr[pivot] = arr[end]; pivot = end; //左边找大，放在右边 while (begin < end && arr[begin] <= key) { ++begin; } arr[pivot] = arr[begin]; pivot = begin; } pivot = begin; arr[pivot] = key; QuickSort(arr, left, pivot - 1); QuickSort(arr, pivot + 1, right); } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; QuickSort(arr, 0, (int)(sizeof(arr) / sizeof(int)) - 1); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
7.3 前后指针法
单趟排序图解，如下:
#include<stdio.h> void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void QuickSort(int* arr, int left, int right) { if (left >= right)return; int key = left; int prev = left, cur = left + 1; while (cur <= right) { if (arr[cur] < arr[key] && ++prev != cur)//避免无意义交换 { Swap(&arr[prev], &arr[cur]); } ++cur; } Swap(&arr[key], &arr[prev]); QuickSort(arr, left, prev - 1); QuickSort(arr, prev + 1, right); } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; QuickSort(arr, 0, (int)(sizeof(arr) / sizeof(int)) - 1); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
7.4 非递归
使用递归方式可能因栈帧深度过大而导致栈溢出。
基本思想:
◆ 先将待排序列的第一个元素的下标和最后一个元素的下标入栈。(区间入栈)
◆ 当栈不为空时，读取栈中的信息（一次读取两个: left、right），然后进行单趟排序，排完后获得了key的下标，然后判断key的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的区间入栈；若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。
◆ 反复执行步骤2，直到栈为空为止。
#include<stdio.h> #include<stdbool.h> #include<stdlib.h> #include<assert.h> //利用栈实现非递归 /************************************************************************************/ typedef int SKDataType; typedef struct stack { SKDataType* data; int top; int capacity; }Stack; void StackInit(Stack* ps) { assert(ps); ps->data = (SKDataType*)malloc(sizeof(SKDataType)*4); if(ps->data == NULL) { printf("malloc fail\n"); exit(-1); } ps->capacity = 4; ps->top = 0;//top指向栈顶元素的上一个位置 } void StackDestory(Stack* ps) { assert(ps); free(ps->data); ps->data = NULL; ps->capacity = ps->top = 0; } void StackPush(Stack* ps,SKDataType d) { assert(ps); if(ps->top == ps->capacity) { SKDataType* newSpace = (SKDataType*)realloc(ps->data,ps->capacity * 2 * sizeof(SKDataType)); if(newSpace == NULL) { printf("realloc fail\n"); exit(-1); } ps->data = newSpace; ps->capacity *= 2; } ps->data[ps->top] = d; ++ps->top; } void StackPop(Stack* ps) { assert(ps); assert(ps->top > 0);//栈不可为空 --ps->top; } SKDataType StackTop(Stack* ps) { assert(ps); assert(ps->top > 0); return ps->data[ps->top - 1]; } int StackSize(Stack* ps) { assert(ps); return ps->top; } bool StackIsEmpty(Stack* ps) { assert(ps); return ps->top == 0; } /***********************************************************************************/ void QuickSort(int* arr, int size) { Stack sk; StackInit(&sk); StackPush(&sk, size); StackPush(&sk, 0); while (!StackIsEmpty(&sk)) { int left = StackTop(&sk); StackPop(&sk); int right = StackTop(&sk); StackPop(&sk); //挖坑单趟排序 int begin = left, end = right; int pivot = begin; int key = arr[begin]; while (begin < end) { //右边找小，放在左边 while (begin < end && arr[end] >= key) { --end; } arr[pivot] = arr[end]; pivot = end; //左边找大，放在右边 while (begin < end && arr[begin] <= key) { ++begin; } arr[pivot] = arr[begin]; pivot = begin; } pivot = begin; arr[pivot] = key; if (right > pivot + 1) { StackPush(&sk, right); StackPush(&sk, pivot + 1); } if (left < pivot - 1) { StackPush(&sk, pivot - 1); StackPush(&sk, left); } } StackDestory(&sk); } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; QuickSort(arr, (int)(sizeof(arr) / sizeof(int)) - 1); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
7.5 优化方法
7.5.1 三数取中
快速排序的时间复杂度是O(NlogN)，是我们在理想情况下计算的结果。在理想情况下，我们每次进行完单趟排序后，key的左序列与右序列的长度都几乎相同。
若每单趟所选的key排完序后都正好是该序列的中间值，那么快速排序的时间复杂度为O(NlogN)。
可是并不能保证每次选取的key都是中间值。当待排序列本身就是有序序列时，若是依然每次都选取最左边或是最右边的数作为key，那么快速排序的效率将达到最低: O(N^2)
三数取中就是为了避免这种极端情况的发生（即取最左边的数、最右边的数以及中间位置的数这三个数中的中位数作为key）,确保了选取的数不会是序列中的最大或是最小值了（依然有可能为次大值或次小值，但概率较小，可忽略）
int GetMid(int* arr,int left,int right)//三数取中 { int mid = (left + right) >> 1; if (arr[left] < arr[mid]) { if (arr[mid] < arr[right]) return mid; else if (arr[left] > arr[right]) return left; else return right; } else//arr[left] > arr[mid] { if (arr[mid] > arr[right]) return mid; else if (arr[left] > arr[right]) return right; else return left; } }
7.5.2 小区间优化
为了减少递归的次数与深度(主要是为了减少次数)，减少因为栈帧开辟而带来的损耗，避免发生栈溢出，就需要使用小区间优化。
//小区间优化(二叉树结构，越靠近叶子，结点数分化越多(函数调用开销较大);尾部直接使用插入排序) //不适合使用堆排序(同为二叉树结构)、希尔排序(适合大体量数据) if (pivot - 1 - left > 10) { QuickSort(arr, left, pivot - 1); } else { InsertSort(arr + left, pivot - 1 - left + 1); } if (right - pivot - 1 > 10) {//该值根据数据量自行调控 QuickSort(arr, pivot + 1, right); } else { InsertSort(arr + pivot + 1, right - pivot - 1 + 1); }
八、归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个典型应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> void _MergeSort(int* arr, int left, int right,int* temp) { if (left >= right) return; int mid = (left + right) >> 1; _MergeSort(arr, left, mid, temp); _MergeSort(arr, mid + 1, right, temp); int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] < arr[begin2]) { temp[index++] = arr[begin1++]; } else { temp[index++] = arr[begin2++]; } } while (begin1 <= end1) { temp[index++] = arr[begin1++]; } while (begin2 <= end2) { temp[index++] = arr[begin2++]; } //将归并数据拷贝回原数组 /*for (int i = left; i <= right; ++i) { arr[i] = temp[i]; }*/ memcpy(arr + left, temp + left, (right - left + 1) * sizeof(int)); } void MergeSort(int* arr, int size) { int* temp = (int*)malloc(sizeof(int) * size); assert(temp); _MergeSort(arr, 0, size - 1, temp); free(temp); } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; MergeSort(arr,(int)(sizeof(arr) / sizeof(int))); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
非递归
#include<stdio.h> #include<stdlib.h> void MergeSort(int* arr, int size) { if (arr == NULL) return; int* temp = (int*)malloc(sizeof(int) * size); if (temp == NULL) return; int gap = 1;//每组数据个数 while (gap < size) { for (int i = 0; i < size ; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; int index = i; if (end1 >= size) { end1 = size - 1; //[begin2.end2]即为一个不存在的区间 begin2 = size; end2 = size - 1; } else if (begin2 >= size) { begin2 = size; end2 = size - 1; } else if (end2 >= size) end2 = size - 1;//归并过程中右区间计算过大 while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] < arr[begin2]) { temp[index++] = arr[begin1++]; } else { temp[index++] = arr[begin2++]; } } while (begin1 <= end1) { temp[index++] = arr[begin1++]; } while (begin2 <= end2) { temp[index++] = arr[begin2++]; } } for (int j = 0; j < size; ++j) { arr[j] = temp[j]; } gap *= 2; } free(temp); } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; MergeSort(arr, (int)(sizeof(arr) / sizeof(int))); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
时间复杂度: O(NlogN) 空间复杂度: O(N) 稳定性: 稳定
九、计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整型数据。
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<assert.h> void CountSort(int* arr, int size) { int max = arr[0], min = arr[0]; for (int i = 1; i < size; ++i) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } int range = max - min + 1; int* count = (int*)calloc(range ,sizeof(int)); assert(count); for (int i = 0; i < size; ++i) { count[arr[i] - min]++;//相对位置映射 } int j = 0; for (int i = 0; i < range; ++i) { while (count[i]--) { arr[j++] = i + min; } } free(count); count = NULL; } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; CountSort(arr, (int)(sizeof(arr) / sizeof(int))); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
时间复杂度：O(N + range)
空间复杂度：O(range)
稳定性: 对于只能排序整型的排序算法，无讨论是否稳定的必要性
