理解实现八大排序
目录
一、初步认识
二、直接插入排序
三、希尔排序
四、直接选择排序
五、堆排序
六、冒泡排序
七、快速排序
7.1 Hoare版本
7.2 挖坑法
7.3 前后指针法
7.4 非递归
7.5 优化方法
7.5.1 三数取中
7.5.2 小区间优化
八、归并排序
九、计数排序
一、初步认识
排序：就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中时，根据排序过程的要求不能在内外存之间移动数据的排序
二、直接插入排序
基本思想: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。( 即当插入第i个元素时，前面的array[0]……array[i-1]已经排好序，此时用array[i]的排序码与array[0]……array[i-1]的排序码进行比较，
找到插入位置将array[i]插入,原来位置上的元素顺序后移 )
但在起始情况时，并不知道待排元素中究竟哪一部分是有序的，所以起初只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。
#include
void InsertSort(int* arr, int n)//升序
{for (int i = 0; i < n-1; ++i)//一共插入n-1趟{int end = i;int temp = arr[end + 1];while(end >= 0){if (temp < arr[end]){arr[end + 1] = arr[end];--end;}else {break;//找到位置}}arr[end + 1] = temp;}
}
int main()
{int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };InsertSort(arr, 10);for (int i = 0; i < 10; ++i){printf("%d ", arr[i]);}return 0;
} 时间复杂度: O(N^2) 空间复杂度: O(1) 稳定性: 稳定
三、希尔排序
希尔排序（缩小增量排序），是直接插入排序的优化，其基本思想是：
1. 先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作。
2. 当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
为什么需要gap由大到小呢？
gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。
#include
void ShellSort(int* arr, int n)//升序
{int gap = n;while (gap > 1)//gap取值无官方规定(2、3……){gap = gap / 3 + 1;//把间隔为gap的多组数据同时排for (int i = 0; i < n - gap; ++i){int end = i;int temp = arr[end + gap];while (end >= 0){if (arr[end] > temp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;}}
}
int main()
{int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };ShellSort(arr, 10);for (int i = 0; i < 10; ++i) {printf("%d ", arr[i]);}return 0;
} 时间复杂度: O(NlogN)
平均时间复杂度: O(N ^ 1.3)
《数据结构-用面相对象方法与C++描述》--- 殷人昆
空间复杂度: O(1) 稳定性: 不稳定
四、直接选择排序
基本思想: 在元素集合中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，再在剩余的集合中重复上述步骤，直到集合剩余1个元素
#include
void Swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}
void SelectSort(int* arr, int n)
{for (int i = 0;i < n - 1;++i){int min = i;for (int j = i+1; j < n; ++j){if (arr[j] < arr[min]) {min = j;}}if (min != i) {Swap(&arr[i], &arr[min]);}}
}
int main()
{int arr[10] = { 10,9,8,7,4,3,2,1,6,5 };SelectSort(arr, (int)(sizeof(arr) / sizeof(int)));for (int i = 0; i < 10; ++i){printf("%d ", arr[i]);}return 0;
} 优化: 每一趟遍历可以同时查找最大值和最小值，效率提升一倍
#include
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
void SelectSort(int* arr,int n)
{for (int begin = 0,end = n - 1; begin < end; ++begin, --end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (arr[i] < arr[mini]) mini = i;if (arr[i] > arr[maxi]) maxi = i;}Swap(&arr[begin], &arr[mini]);if (begin == maxi)maxi = mini;//前面的交换可能改变了此趟最大值的位置Swap(&arr[end], &arr[maxi]);}
}
int main()
{int arr[10] = { 10,9,8,7,4,3,2,1,6,5 };SelectSort(arr, (int)(sizeof(arr) / sizeof(int)));for (int i = 0; i < 10; ++i){printf("%d ", arr[i]);}return 0;
} 时间复杂度: O(N^2) 空间复杂度: O(1) 稳定性: 不稳定
五、堆排序
堆排序也属于选择排序中的一种。具体可以看下面这篇文章:
(28条消息) 堆结构的深度理解_GG_Bond19的博客-CSDN博客_堆的深度
https://blog.csdn.net/GG_Bruse/article/details/127742947
六、冒泡排序
这个算法的思想与它的名字息息相关，即通过交换每一趟冒出一个最大（或最小）值
#include
void Swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}
void BubbleSort(int arr[],int n)
{for (int i = 0; i < n; ++i){int exchange = 0;for (int j = 0; j < n-i-1; ++j){if (arr[j] > arr[j+1]){Swap(&arr[j], &arr[j + 1]);exchange = 1;}}if (exchange == 0) {//若没发生交换，则已有序break;}}
}
int main()
{int arr[10] = { 10,9,8,7,4,3,2,1,6,5 };BubbleSort(arr, (int)(sizeof(arr) / sizeof(int)));for (int i = 0; i < 10; ++i) {printf("%d ", arr[i]);}return 0;
} 时间复杂度: O(N^2) 空间复杂度: O(1) 稳定性: 稳定
七、快速排序
快速排序是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
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
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
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
#include
#include
#include
//利用栈实现非递归
/************************************************************************************/
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
#include
#include
#include
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
#include
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
#include
#include
#include
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)
稳定性: 对于只能排序整型的排序算法，无讨论是否稳定的必要性