数据结构之八大排序

!!‧✧̣̥̇‧✦‧✧̣̥̇‧✦ ‧✧̣̥̇:Solitary_walk
⸝⋆━━━┓
– 个性标签 – ：来于“云”的“羽球人”。 Talk is cheap. Show me the code
┗━━━━━━━ ➴ ⷯ
本人座右铭：欲达高峰,必忍其痛;欲戴王冠,必承其重。
自
信
　希望在看完我的此篇博客后可以对你有帮助哟
此外，希望各位大佬们在看完后，可以互相支持，蟹蟹！

思维导图：

1直接插入排序

1.1插入排序的思想

把待排序的数据依次与当前已经有序的数据进行比较，直到待排的数据全部排完得到一组新的有序的数据

生活中的玩扑克牌就是插入排序的一种体现

动图的过程：

分析：

1.2代码的实现

void Insert_sort(int* a, int num){for (int i = 1; i = 0){if (key = a[end]break;}a[end + 1] = key;//break出来或者是end= -1都可以把key解决掉}}

1.3插入排序对应的时间复杂度以及空间复杂度的分析

时间复杂度
最好的情况下：原数组本身就是升序的，在对数组进行升序排列，（N-1）个数一共比较（N-1）次，此时不需要进行数据的挪动，所以时间复杂度是 O（N）
最坏情况：原数组本身就是逆序的，当你想进行升序排列的话，（N-1）个数一共需要进行O（N^2）级别次，每比较一次就进行一次数据挪动，所以对应时间复杂度 O(N^2)

2希尔排序（缩小增量法）

希尔排序是对直接插入排序的优化。

2.1希尔排序的思想

先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为gap(取决于数组大小)分在同一组内，并对每一组内的记录进行排序，重复上述分组和排序的工作。当 gap=1时，所有记录在一组内已经是有序。

总的来说就是先对原数组进行预排序，让数组接近有序，在进行一次直接排序即可有序

插入排序可以视为特殊的希尔排序。

分析：
接下来就是对数组进行预排序：注意是在原数组的空间进行排序的，预排序的关键就是如何确定 gap的值以及下标边界的范围
单趟排序用直接插入排序来进行。
进行第一趟的排序：
不止一趟的排序：再来一个for循环搞定多趟的排序

gap具体的取值由数组的东西而决定，一般对于gap的取值有2个方法可行，但是需要注意条件的判断以及必须保证 gap = 1的时候也能进行排序，gap = N / 2 或者是 gap =( N / 3) + 1，注意gap取不同的值对应结束的条件不同

2.2代码的实现

void Shell_sort(int* a, int num){/*1：预排序：让他内部接近有序2：整个直接排序*///int gap = 3;int gap = num;//for (int i = 0; i = 1){gap /= 2; //一定可以保证gap = 1的时候进行排序for (int i = 0; i < gap; i++)//多趟排序{//单趟排序//int end_i = i;for (int j = i + gap; j < num - i; j += gap) // j = 0)//条件注意{if (tmp < a[end_i]){//挪动数据//a[end_i + gap] = tmp;// erra[end_i + gap] = a[end_i];// errend_i = end_i - gap;}elsebreak;}a[end_i + gap] = tmp;}}}//Insert_sort(a, num);}

2.3希尔排序对应的时间复杂度以及空间复杂度的分析

空间复杂度是O(1)并不需要额外的空间

对于时间复杂度的分析其实是有争议的，并没有一个具体的，但在 O(N *logN）~O(N^2)

3选择排序

3.1选择排序的思想

如果有N个元素需要排序，默认第一个元素为有序的，那么首先从N-1个元素中找到最小的那个元素与第0位置上的元素交换（重复以上过程）然后再从剩下的N-2个元素中找到最小的元素与下标为的1元素交换，之后再从剩下的N-2个元素中找到最小的元素与倒数第2位置上的元素交换，…….直到所有元素都排序好。

分析：

3.2代码的实现

void Select_sort(int* a, int num){for (int j = 0; j < num; j++){int min_i = j;int i = j + 1;//单趟排序for (i; i < num; i++){//升序排if (a[i] < a[min_i])min_i = i;}Swap(&a[j], &a[min_i]);}}

这个代码很好理解，其实他还是有可以优化的空间

优化版本：每一趟排序把最大的数和最小的数同时选出

void Select_sort(int* a, int num){//进行优化 每一趟排序找出当前数组里最小和最大的数因为一个升序的数组最小的数一定在第一个位置（相对而言）最大的数一定在最后一个位置（相对而言）int begin = 0;int end = num - 1;while (begin < end){//假设每趟排序中第一个数最大，最小，注意第一个数不一定下标为0int min_i = begin;int max_i = begin;for (int i = begin+1; i  a[max_i])max_i = i;if (a[i] < a[min_i])min_i = i;}Swap(&a[min_i], &a[begin]);//注意可能begin对应的数为最大，当与最小的数交换后，最大的数来到min_i对应的位置if (begin == max_i) //注意是下标max_i = min_i;//if (max_i != end) //当end位置就是最大的数就不用交换Swap(&a[max_i], &a[end]);begin++;end--;}}

4.1.1.1堆排序之前建大堆还是建小堆

在进行堆排序之前（默认排升序），需要先建一个大堆：建大堆可以保证最大元素与堆尾元素交换后，当前最大元素一定是在堆尾的（只是相对而言），或者说建大堆后，堆顶与队尾元素交换后，可以视为把堆顶元素尾插到堆尾，这样就能保证数组是以升序排列。同理，若是降序排的话，需要建小堆

4.1.1.2 向上建堆分析

建大堆：
从最后一个节点开始向上建堆，要是当前位置 child大于双亲parent 所对应的值，就进行交换，接下来就是进行更新 child= parent: child来到双亲所对应位置， parenrt = (child-1) / 2
在执行这个逻辑：child大于双亲parent 所对应的值，就进行交换

分析见下：

堆顶元素与堆尾元素交换后，对除堆尾的所有元素进行上调重新建大堆，选出当前最大的元素以此头插到堆尾元素的前面

4.1.2向下调整进行堆排序

get 到了上调算法，那么咱也就轻松拿捏下调算法了，二者大同小异

还是老问题，先对当前数据进行下调建大堆，再利用堆顶与堆尾元素交换，依次进行下调

若是从4这个节点开始进行下调的话，他的左右子树都不符合堆的要求。很显然不能从4这个节点调整。只能倒着往前进行下调：从第一个非叶节点开始进行下调
分析见下：

4.2代码的实现

上调代码：

void Adjust_up(int*a,int child) //问题1;第二个参数传孩子节点位置而不是双亲节点下标{int parent = (child - 1) / 2;while (child >= 0)//问题2 ： 结束条件必须是 chind >= 0而不能parent>= 0 最终parent的值永远是0 ，会出现死循环{if (a[child] > a[parent]){Swap(&a[child], &a[parent]);//依次上调进行更新child = parent;parent = (child - 1) / 2;}elsebreak;}}void Heap_sort(int* a, int num){ int pos = num - 1;for (pos; pos > 0; pos--){Adjust_up(a, pos);}//排序：上调pos = num - 1;while (pos > 0) //不能取等{Swap(&a[0], &a[pos]);//堆顶元素依次放到堆尾 //问题4 //对于下的n-1 (n-2)(n-3)重新建大堆 不是建一次就OK的for (int i = pos - 1; i > 0; i--){Adjust_up(a, i);}pos--;}}

下调代码

void Adjudt_down(int* a, int parent, int num){int child = 2 * parent + 1;//假设左孩最小while (child < num){if (child + 1 < num && a[child]  a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}}void Heap_sort(int* a, int num){//升序：建大堆 => 排序：堆顶元素依次与堆尾元素交换最终结果： 第一小，第二小，…… 倒数次次大，倒数第二大，最大//下调来进行的//下调来进行的int pos = num;pos = (num - 1 - 1) / 2;//建大堆while (pos >= 0){Adjudt_down(a, pos, num);//pos-1 最后一个节点下标 (pos - 1 - 1) / 2 最后一个节点的双亲位置pos--;}//排序//if (num =0) //一定要取等{Swap(&a[0], &a[pos]);/*for (int i = pos - 1; i >= 0; i--){Adjudt_down(a, (i-1)/2,pos);}*/Adjudt_down(a,0,pos );pos--;}}

4.3堆排序对应的时间复杂度以及空间复杂度的分析

空间复杂度：O（1），并没有额外空间的消耗

利用向上调整来进行排序的时间复杂度： O（N * log N）

利用向下调整来进行排序的时间复杂 O（N）

5冒泡排序

5.1冒泡排序的思想

相邻两哥元素进行比较，若是满足条件，进行两两相邻元素进行交换

动图示范：

单趟排序

5.2代码的实现

void Bubble_sort(int* a, int num){int flag = 0;//默认数组有序for (int i = 0; i < num; i++){for (int j = 0; j  a[j + 1])//升序排{Swap(&a[j], &a[j + 1]);flag = 1;}}if (flag == 0)break;//数组本身就有序}}

5.3冒泡排序对应的时间复杂度以及空间复杂度的分析

时间复杂度：O（N^2）

空间复杂度：O(1)

6快排

6.1快排的思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

6.1.1Hoare法的快排实现

先选出一个元素作为基准，遍历原数组，把小于基准数的放到左边，大于基准数的放到右边

具体实现见下：默认一个数作为基准（只是相对而言，因为需要层层递归），定义2个变量 left ,right，其中left找大于基准数，right找小于基准数的，找到后让left 与right 对应位置的数交换，再继续找知道left right相遇，此时与基准数进行交换，并记录当前left的位置，作为下一次的查找范围
注意一些细节：在left找大，right找小，谁先走取决于基准数是在左边还是在右边
基准数（key_i）在左边，right先走进行找小，要是基准数（key_i）在右边，left先走进行找大
当key_i与left，right重合的时候也可以不进行交换
递归结束条件： begin >= end : begin = end 只有一个数，本身就是有序的不用进行排序， begin >end:说明区间不存在

6.1.2挖坑法的快排实现

挖坑法和Horea法思想一样，只不过是另一种写法，不用注意left ，right先后走的顺序问题
假设第一个数为基准，同时也为坑所在位置（只是相对而言），依然是left找比 key大的，right找比key小的，因为left所在位置为坑，right先找找到与坑所在位置交换，让hole来到right所在位置，此时left找大，找到与hole所在位置交换，hole来到left坐在位置，最终left，right相遇（同时也是hole所在位置）让key 赋给hole所在位置单趟排序完成，接下来重复进行即可。
分析见下：

6.1.3前后指针法的快排实现

6.2代码的实现

6.2.1Hoare法

intPart_sort1(int*a,int begin,int end) //Hoare 法{int key_i = begin;//默认第一个数所在位置为基准int left = begin;int right = end;while (left < right){while (left < right){if (a[right] < a[key_i]) //找小break;right--;}while (left  a[key_i]) //找大break;left++;}Swap(&a[left], &a[right]);}//left right一定相遇if(left != key_i)Swap(&a[key_i], &a[left]);return left;}void Quick_sort(int* a,int begin, int end)//下标{if (begin >= end)return;int meet_i = Part_sort3(a,begin,end);//此时数组分为3个区间 [begin,meet_i-1] meet_i [meet_i+1,end]Quick_sort(a, begin, meet_i-1 );Quick_sort(a,meet_i + 1,end);}

6.2.2 挖坑法

int Part_sort2(int* a, int begin, int end){int left = begin;int right = end;int key = a[begin];int hole = begin;while (left < right){while (left < right){if (a[right] < key){a[hole] = a[right];hole = right;break;}right--;}while (left  key){a[hole] = a[left];hole = left;break;}left++;}}a[hole] = key;return left;}void Quick_sort(int* a,int begin, int end)//下标{if (begin >= end)return;int meet_i = Part_sort3(a,begin,end);//此时数组分为3个区间 [begin,meet_i-1] meet_i [meet_i+1,end]Quick_sort(a, begin, meet_i-1 );Quick_sort(a,meet_i + 1,end);}

6.2.3前后指针

int Part_sort3(int* a, int left, int right)//前后指针{int pre = left;int cur = left;int key = a[left];while (cur = key)cur++;else //cur = end)return;int meet_i = Part_sort3(a,begin,end);//此时数组分为3个区间 [begin,meet_i-1] meet_i [meet_i+1,end]Quick_sort(a, begin, meet_i-1 );Quick_sort(a,meet_i + 1,end);}

6.3快排对应的时间复杂度以及空间复杂度的分析

空间复杂度：O（1）

时间复杂度：O（）

分析时间复杂度：
这三个方法实现的快排思想都是一样的，通过前期画图的理解，其实不难发现，快排的过程和二叉树往下递归的过程一样的
最坏的情况：O（N^2）当数组是降序的时候，这时候需要排成升序或者是数组本身就是升序需要排成降序的就是最坏的情况了，假设第一个数为基准，总的比较次数就是一个等差数列
最优的时间复杂度：O（N*logN）每一轮的排序都把区间差不多对半分（也就是基准数都来到中间位置）

6.4快排的优化

很显然快排对随机数据的排序是很友好滴，当我们数据与要排序的方向相反的时候，那就很糟糕了，针对这个情况我们可以做些改进
三数取中：对left right mid（中间位置下标）取出一个不大不小的数

优化之后的代码：

int Get_mid(int* a, int left, int right){//三数取中 找不大不小的数所在位置int mid_i = (right + left) / 2;if (a[mid_i] > a[left]){if (a[left] > a[right])return left;else if (a[right] > a[mid_i]) //同时说明 left <= rightreturn mid_i;return right;}else// mid_i <= left{if (a[right]  a[left]) //right>= mid_ireturn left;elsereturn right;}return mid_i;}intPart_sort1(int*a,int begin,int end) //Hoare 法{//三路划分优化：针对数组本身就有序int key_i = Get_mid(a, begin, end);Swap(&a[begin], &a[key_i]);//让中位数与下标0的数交换 key_i = begin;//默认第一个数所在位置为基准int left = begin;int right = end;while (left < right){while (left < right){if (a[right] < a[key_i]) //找小break;right--;}while (left  a[key_i]) //找大break;left++;}Swap(&a[left], &a[right]);}//left right一定相遇if (left != key_i)Swap(&a[key_i], &a[left]);return left;}

进阶版的优化：当有大量的重复元素的时候，对应最坏的时间复杂度O（N^2）

分析见下

代码：

7归并排序

7.1归并排序思想

为了方便理解这个思想先以一个题列来引入：合并2个有序数组，arr1,arr2：思想依次取小的尾插即可最终便可以实现整个数组有序。

对于归并而言也是一样的：先把数组进行分解，最后在层层回溯进行归并

把数组对半分直至分成只有一个元素的时候，再进行归并
分析见下：
注意在进行归并的时候一定不能再原数组进行：造成数据的覆盖，所以查立就需要开辟一个数组大小同原数组大小一样

7.2代码实现

void _Merge_sort(int* a,int* tmp ,int begin,int end){if (begin >= end)return;int mid_i = (end + begin) / 2;//中位数下标//此时分成2个区间[begin,mid+i] [mid_i+1,end];//左区间递归_Merge_sort(a,tmp, begin, mid_i);//右区间递归_Merge_sort(a,tmp, mid_i + 1, end);//归并int left1 = begin;int right1 = mid_i;int left2 = mid_i + 1;int right2 = end;int i = begin;//注意这里不能设置为0 ，每次递归调用的时候要不都会在0 重新赋值while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){tmp[i++] = a[left1++];}else{tmp[i++] = a[left2++];}}while (left1 <= right1){tmp[i++] = a[left1++];}while (left2 = end)return;_Merge_sort(a, tmp, begin, end);}

7.3时间复杂度以及空间复杂度分析

空间复杂度：O（N）需要为每次拷贝开辟额外空间

时间复杂度：O（N*logN）归并排序在进行递归调用的时候其实是一个二叉树往下递归的过程，外循环所指向次数就是二叉树的高度 logN，内循环是所执行次数N

7.4优化

当递归层次太深的时候，会造成栈顶溢出，因此就需要减少递归调用的次数
小区间优化
当递归到元素个数少于10个的时候，这时候可以采用一些其他排序进行（效率高的），比如直接插入排序
为什么是少于10个呢？因为当递归到只有10个元素的时候这是就已经减少了80%以上的递归调用次数

7.5非递归的实现

先一一进行归并，再二二进行归并，依次类推直至数组有序
这个看起来是容易理解但是写起来很容易有问题：频繁的越界，以及拷贝数据下标的选择
分析见下：

代码：

void Merge_sortNonR(int* a, int num){int* tmp = (int*)malloc(sizeof(int) * num);if (tmp == NULL)return;memset(tmp,0, sizeof(int) * num);//全部初始化0int gap = 1;//int i = 0;//记录tmp中下标位置while (gap < num) //需要取等{int i = 0;//记录tmp中下标位置for ( int j = 0; j = num){end1 = num - 1;begin2 = num;end2 = num;}if (begin2 >= num){begin2 = num;end2 = num;}if (end2 >= num){end2 = num - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[i++] = a[begin1++];elsetmp[i++] = a[begin2++];}while (begin1 <= end1 ){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}} memcpy(a, tmp, sizeof(int) * num);//memcpy(a, tmp, sizeof(int) *i);gap *= 2;}}

8计数排序

8.1计数排序的思想

对于前面的七大排序都是基于数据比较之后实现的，而计数排序的实现是通过记录当前数据出现的次数来实现的

具体实现：
当数组的数据比较大的时候难道也要放到指定的下标位置：比如说最大的数89需要放到下标为89的位置吗，这样岂不是很浪费空间
采用相对映射的思想：让当前数据减去最小的数：min = 80,即为要存放的位置，这样就减少了空间浪费的现象，注意只是相对减少，但多多少少还是存在浪费的情况
当还原到原数组的时候让当前下标再加上min即为原始数据