数据结构之-----“交换排序”“归并排序”“计数排序”

在此先总结一下之前的希尔排序和直接选择排序的不同之处。

希尔排序是将待排序的和有序的一一比较，将(无序序列中的第一个数据)和(前面有序序列的最后一个数据)先进行比较（和有序最后一个比完之后，还要和前面有序的数据也进行比较），遇到合适的位置将它放在那里。【插入类】

直接选择排序是将待排序的序列遍历一遍，找到最大和最小值，放在第一个位置和最后一个位置；接着在剩余无序的空间继续进行遍历，找最大和最小值，放在第二和倒数第二的位置。【选择类】

交换类

1. 冒泡排序

https://editor.csdn.net/md/?articleId=138645918，这个是冒泡排序的链接。

冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

这个在之前的笔记已经有了，不再过多赘述。

2. 快速排序

（1）霍尔法（递归版）

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：
（1）在待排序元素序列随意挑选一个元素作为基准值(按照该[排序码]将待排序集合分割成两子序列)

• 其中：小于基准值的都放在基准值左边，大于基准值的都放在基准值右边。
  至此，将数据分为两个子序列。左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值

（2）然后对第一步得到的左右子序列再进行上述过程(找基准值，划分)，先对左子序列进行划分，再对右子序列进行划分。

• 这里会使用到递归：先将整段划分为左右，再对左进行划分，再对左的左进行划分，当没有左之后，开始对右进行划分。
  （3）递归到何时为止呢？递归到基准值的左边只有0个或1个元素

有一个需要注意的点是：前面几种排序方法的参数是数组和元素个数，这里采取的是数组和数组元素的首尾下标(因为有右子序列，它不能单纯用元素个数来统计，需要用区间来表示)

• 实现思路：
• 这里我们采用的是双指针的方法（但注意，指针只是比喻，并不是真正的指针）
• 首先，先将序列的第一个值作为基准值(midi)，最后一个元素也可以，其他的就不可以了，不适合寻找值。
• 然后设两个指针，左指针left和右指针right，它们的作用分别是：左指针负责(从左往右遍历序列)找到比基准值大的，然后将它甩到右边，右指针负责(从右往左遍历序列)找到比基准值小的，甩到左边
• 刚开始，right先动，从右往左找比基准值小的，找到之后，left开始从左往右遍历，寻找比基准值大的。在都找到之后，将这两个值交换(这也是为什么快速排序属于交换类了，在交换完之后，【将left++以及right- -】如果left和right还没有相遇，那么继续遍历再交换。当它们相遇的时候，就可以将循环结束了。
• 在循环结束之后，就可以将下标midi和right交换了

整体递归的感觉是这个样子的

完整正确版：

int _QuickSort(int* arr, int left, int right)
{int midi= left;++left;while (left <= right)//left和right相遇的位置的值比基准值要大的时候是一个特殊情况{while (left <= right && arr[right] > arr[midi]){right--;}//循环条件：right找到比基准值小/  等于？while (left <= right && arr[left] < arr[midi]){left++;}if (left <= right){Swap(&arr[left++], &arr[right--]);}}//right keyi交换Swap(&arr[midi], &arr[right]);return right;
}void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//[left,right]--->找基准值midiint keyi = _QuickSort(arr, left, right);//左子序列：[left,midi-1]QuickSort(arr, left, midi- 1);//右子序列：[midi+1,right]QuickSort(arr, midi+ 1, right);
}

一步步进行解析

• 在找基准值的过程中也会有很多的细节问题：
  刚开始的简易版：
  

接下来逐步细节化：

1. 不管什么情况下，只要找到了合适的arr[left]和arr[right]，都可以交换吗？
   当left在左边，right在右边，它们找到合适的值就交换，使得左边值都<基准值，右边值都>基准值。那如果right在向左- -的时候，已经减到了left的左边，那它不就是在一堆堆(比基准值小的里面)找比基准值小的吗，随便一个都是符合要求的，如果left向右走，也找到了比基准值大的，那它俩交换一下，不就是将(原本已经放在合适位置的值)，又放到后面，放乱了。

所以，将两个值交换是有条件的，需要满足left<right。（left==right时是否可以交换值，之后再讨论）

2. while (arr[right] > arr[midi]) {right--;}是否不够严谨？只要在右边那部分的某个值大于基准值，然后就不用交换，直接让right- -？
   那如果数组的值是arr[]={6,6,6,6,6,6},right从右往左遍历一直找不到比基准值小的值，一直向左- -，万一越界了(下标right都减到了负数)，之后怎么办，基准值是谁呢？
   

所以，当left>=right，且还没有找到适合的值，可以减减，如果right<left，那就不可以让right再继续减减

3. 一定要arr[right]>arr[midi]的时候才继续往左走吗？那arr[right]==arr[midi]的时候，是将这个right记录下来，用于之后交换？还是将right- -，继续往左走？接下来的解释仍然是以arr[]={6,6,6,6,6,6}为例。【答案是将right记录下来，之后交换】
   这个例子中，所有值都和基准值一样大，如果它俩相等，不记录right，而是直接将right- -，那么就会像上一张图片一样，基准值仍然是第一个元素。

快排的时间复杂度为什么比较优呢？是因为找基准值就像中间值一样，将整个数组二分了，每次都二分。那如果值相等时直接减减，减到最前面，左子序列为0，右子序列是n-1个元素，下次右子序列是n-2个元素。这样失去了找基准值的意义。

那记录right，之后用于交换又是一种怎样的情况呢？

会使得数组大致的二分。
所以，当arr[right]==arr[midi]的时候，记录right，以后swap。
所以，while( left <= right && arr[right] > arr[midi])的时候，right- -。另一个left++同理。

4. 为什么left==right的时候，也可以进入循环，去继续r- -,l++,找基准值？
   

给大家举一个（left和right相遇位置的值）比基准值大的例子：

以上图片就是原因。

5. 前面讲解的都是寻找基准值的各种细节，在找完基准值之后，我们做什么呢？开始写真正的快速排序。因为我们要寻找很多的基准值，首先找整个数组的基准值，将它分为左、右子序列，接下来找左子序列的基准值，然后找左的左子序列的基准值，直至某个序列不再有左子序列，然后开始归，归到刚开始的数组，开始找它的右子序列的基准值，再找右的右子序列，直至没有。
   

在整个过程中，有两个含义的left和right，一个是寻找基准值函数中的left和right(函数_QuickSort)，以及快排函数的参数left和right。它俩是不一样的（因为在_QuickSort这个函数中，我们将left=midi+1了(midi就是left)。而在快排中，它的left和right就是数组的首尾下标。

接下来的问题是：我们找数组的midi，又在找左子序列的midi，左的左的midi，那什么时候可以不用继续递归去找基准值了呢？

（1）就是这个序列只剩下一个元素了。
1.当这个序列只剩下一个元素，就不用找基准值了
那什么代表着序列只剩下一个元素呢？即left==right的时候（什么样的情况导致的呢？在上一次找基准值的时候，基准值是整数第二or倒数第二(下标是1or n-2)，使得左or右子序列的元素只剩下一个）

（2）左or右子序列下标不对：left<right

6. 从5可得出,递归结束的条件：left<=right.

（2） 挖坑法（递归）

在完成霍尔版本的之后，剩下的会感觉比较简单。

挖坑法就是：不断挖坑，不断填坑的过程。我们先将下标为0的这个地方设为坑，每找到一个比midi大或者小的值，就拿它去填坑。（霍尔版本是同时找到min和max，而挖坑法每次只需要找一个，这次right找，下次left找）
（1）先让right动，去寻找比midi小的，放在hole(坑)处，此时下标为right的地方没有值了，它就成为了新的坑（right是从右往左找比midi小的值，所以若此时right这个地方成为坑，那就需要用一个(大于midi的值)填这个坑。
（2）接下来让left从左往右找，比midi大的值，找到之后用这个填坑，紧接着left这个位置没有值了，成为了新的坑(因为它在左半部分，所以需要一个小值来填充它)，接下来就是right从右往左找比midi小的值了
（3）当left==right时，就不能再让left++或right- -了（为什么等于的时候，就不再进入循环了，和霍尔不一样？是的，霍尔是left和right同时走，都找到之后然后交换，而挖坑法是right和left分开走，right停在那里，说明right在的那个位置的值已经交换过了。left同理）
因为这里每次只动一个指针，如果是left++使得两个指针相遇，我们需要思考right在那里，）

//挖坑法
int _QuickSort2(int* arr, int left, int right)
{int hole = left;  //坑先设成第一个位置int midi = arr[hole]; //将基准值也先设为第一个元素while (left < right){while (left < right && arr[right] > midi)right--;arr[hole] = arr[right];hole = right;while (left < right && arr[left] < midi)left++;arr[hole] = arr[left];hole = left;}arr[hole] = midi;return hole;
}

我觉得这个是三种方法中最简单的，but这种方法有一点弊端：如果选的基准值是最小值或者最大值，那么就不能实现序列分为两段的理想状态了，那么序列就会呈现一边倒的情况。这也是快速排序的最差情况。

（3）lomuto前后指针法

设置两个前后指针，一个是prev，一个是cur，（current是现在的意思，prev是前一个的意思），cur永远在prev的前面。

将cur指向的数据和基准值midi进行比较，如果arr[cur]>midi，cur继续++。如果arr[cur]<midi，那就将prev往后走一步并和cur交换。

（也就是prev本来在最开始的位置，cur从左往右遍历（将整个数组都遍历了，将所有比基准值小的都放在左半边了），如果cur遇到了比基准值大的值，就将arr[cur]和arr[++prev]交换，使得比基准值小的值放在左半部分。

需要注意的点：
（1）但arr[cur]小于midi，不是要将prev++，然后将arr[cur]和arr[prev]交换嘛。如果prev+1==cur的话，那就不用交换了，因为arr[prev+1]就是arr[cur]。
（2）当cur越界，代表着整个数组已经遍历结束了。（prev指向的值还是(上次arr[cur]小于基准值，然后赋值给它的，所以prev此时指向的值，是小于基准值的）所以将arr[prev]和arr[midi]交换，然后再将return prev。
（3）arr[cur]==arr[midi]，是否需要swap(&arr[cur],&arr[++prev])呢？不需要的

//方法一
int _QuickSort3(int* arr, int left, int right)
{int prev = left, cur = left + 1;int keyi = left;while (cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[keyi], &arr[prev]);return prev;
}//方法二
int _QuickSort4(int* arr, int left, int right)
{int midi = left;int prev = left;int cur = prev + 1;while (cur <= right){// 找到第一个<=基准的cur,通过第一个循环之后，就找到第一个满足条件的值了，arr[cur]<arr[midi]while (cur <= right && arr[cur] > arr[midi])cur++;if (cur > right)   // 这里主要是防止cur越界，因为前面的while循环，结束的时候，可能是因为cur > right，所以要判断一下break;// 无论是否相邻，都交换并更新prevprev++;swap(&arr[prev], &arr[cur]);cur++;}swap(&arr[prev], &arr[midi]);return prev;
}

弊端：如果选的基准值是最小值或者最大值，那么就不能实现序列分为两段的理想状态了，那么序列就会呈现一边倒的情况。这也是快速排序的最差情况。

接下来我们具体来看看这个排序算法的效率如何。首先我们看看它的时间复杂度与空间复杂度。对于它的时间复杂度，我们就hoare版本进行计算，主要在查找基准值上，由于每次都会根据基准值将序列分段，于是最后要进行log2n次，这个是在left<right的循环条件为前提进行的，由于left++,right–，因此这个移动次数与交换次数也为n,因此时间复杂度就是O(N*logN),至于空间复杂度，快速排序运用了递归，而递归又运用了栈，栈会有额外的辅助空间开销，由于进行了logn次，因此它的空间复杂度是O(logN).

（4）非递归版本

前面三种找基准值都是递归版，现在学习非递归版本。
仔细看的话，会发现，其实上面的递归操作中最为主要且重要的就是对于数组区间的一个分割。

接下来思考，我们不使用递归，那使用什么数据结构呢？（栈：后进先出）

递归的话，是先遍历所有的左子序列，完成所有的左之后，才开始遍历右。那怎么才能先遍历所有的左呢？

一个数组先将它的整段放进去【先将right入栈，再将left入栈，使得后进来的left先出去，right再出来，成为了一个区间：[left,right]】

再进行计算之后，将它分为两个区间（左区间和右区间），再将右区间的right和left一次入栈，如何左区间的right和left一次入栈，这样下次出栈的就是左区间了(但是右区间可没有出栈，它还在里面)。然后再将出栈的左区间进行划分成两半，然后再将它的右区间入栈，左区间入栈。下次再将这次的左出栈，进行划分。当左结束之后，会发现栈里只剩下了那些右区间…，接下来最上面的那个右区间就会出栈，然后进行对它的数组分割，入栈什么的

1. 那如何将区间分成两半呢？：midi=（leift+right）/2。
   左区间：[begin,midi-1]，右区间[midi+1,end]，基准值是arr[midi]
2. 那怎么知道左结束了呢？什么情况下这个区间就不可以再入栈了，就结束了呢？（区间只剩下一个数据/或者非有效区间）

只有一个数据的例子：（左区间[0,0]，即midi-1=begin）或者（右区间[midi+1,end]中，midi+1=end）只有一个数据不入栈，所以= =的时候，不可以入栈

非有效区间的例子：（左区间[0,-1]，即midi-1<begin）或者（右区间[5,6]，即midi+1>end）非有效区间不入栈

那左区间入栈的条件：midi-1>begin，右区间入栈的条件：midi+1<end;

void QuikcSortNonR(int* arr, int left, int right)
{stack st;StackInit(&st);stackPush(&st, right);stackPush(&st, left);//只要栈顶数据不为空，就一直取栈顶元素while (!stackEmpty(&st)){//取栈顶（两次）---取left，删，再取right，再删int begin=stackTop(&st);stackPop(&st);int end = stackTop(&st);stackPop(&st);//left,right取到之后，开始找基准值----采用双指针法int prev = begin;int cur = begin+1;int midi = begin;while (cur <= end){if (arr[cur] <= arr[midi]){swap(&arr[cur], &arr[prev]);}   //这一步使得，小的值放在左边cur++;}swap(&arr[cur], &arr[midi]);    //接下来prev就是基准值midi = prev;//根据基准值划分左右区间:左[begin,midi-1]右[midi+1,end]//但需要注意，左右区间入栈有条件if (midi + 1 < end){stackPush(&st, end);stackPush(&st, midi+1);}if (midi - 1 > begin){stackPush(&st, midi - 1);stackPush(&st, begin);}//在入栈之后，继续进行循环，先判断是否为空，不是空，继续刚刚的操作}StackDestroy(&st);
}

归并排序

总共分成了两个部分：先将大的数组进行拆分，再将一个个单的数组进行合并。

(1)将数组一直进行”分半“，直至这个数组只剩下一个元素（可以将这一个元素也看成一个数组，而且因为只有一个，它还是有序的）

(2)接下来将两个有序的数组进行合并成为一个新的有序的数组【最开始那个有序的数组只有一个元素，将它俩合并成有序的很简单(将小的放前，大的放后即可)，但之后有序数组里的元素个数逐渐增多(不止一个)，如何让他们所有的数组合并之后也有序呢？例如：[1,5,7],[2,3,9][采用两个指针，同时遍历两个数组，将此时指向的值进行比较，小的先放在新的数组中]，以此达到新数组tmp中，数据从小到大）

注意点：
(1）在递归的时候，最先写的就是：递归结束条件。（在这里结束的条件就是：只剩一个数据）

(2）每次将数组分成一半，左区间是[left,midi]，右区间是[midi+1,right]。
差异点：在快排中，基准值是确定在数组中的值，下次继续划分的时候是不包括这个基准值的（那个黑色框框中的是基准值）。

但归并排序不一样，它跟着下次划分，它放在左区间里。

(3）创建新的数组tmp，那空间大小是多少呢？应该是和原数组大小一样的。（将合并好的数据先放在tmp中）[记得在结束的时候，将tmp这个数组free掉]

(4）每次将两个有序序列排好之后都先放在tmp中，之后都要将tmp中的数据给给arr，因为要比较的是原数组下标位置的数据

【1】在分解的过程中，发现数组不可以再进行分解了，就开始合并这两个有序序列（看上图：比如将10和6合并，成为{6,10}。每次合并好的值都现在tmp中，这个函数栈帧合并完成之后，再将tmp的值，一一对应给给原数组arr）

【2】当前函数栈帧合并结束之后，继续向上回溯

按照这个方式继续执行即可

void _MergeSort(int* arr, int left, int right, int* tmp)
{//递归结束条件if (left >= right)  return;int midi = (left + right) / 2;_MergeSort(arr, left, midi, tmp);_MergeSort(arr, midi+1, right, tmp);//将不能再分解的进行合并：[left,midi],[midi+1,right]int begin1 = left; int end1 = midi;int begin2 = midi + 1; int end2 = right;int index = begin1;   //为什么是index呢while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])tmp[index++] = arr[begin1++];else {tmp[index++] = arr[begin2++];}}//当其中一个数组已经遍历结束后，那就不用再比较了，tmp剩下的值就是没遍历结束的那个数组剩下的值了while (begin1 <= end1) //这个是{tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//最后将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);
}

非比较排序 ->计数排序（时间复杂度很优秀）

计数排序，它使用的是鸽巢原理。

这个排序使用的方法是什么呢？

1. 先统计每个元素出现的次数
2. 然后创建一个新的数数组count，让原数组的数据作为新数组的下标，再让这个次数变为新数组的元素
3. 最后一步，一 一对应回去。遍历新数组count，直到某个元素不为0，然后将它的下标赋给原来数组，元素为几，就将数组打印几次。

上图绘制了过程，但还存在其他问题

1. 新数组count的空间大小如何设置？

（1）如果按照原数组的最大值，将数组count的大小设为max+1？（为什么是max+1呢，要想让数组的下标为max，那元素个数(即空间大小就必须是max+1了)

但这种方法行不通，因为如果出现了这种情况：{100000，100001，100003，100001}，那新数组就会浪费掉很多空间，采取的方法：数组count的空间大小设置为max-min+1

2. 还需要考虑数组中的负数怎么办？

(1) 取它的绝对值？也是不可取的，万一数组中同时存在-5和5的话，取绝对值之后，就分不清正负了。

(可以按照某种方法，将最小的那个值被弄为0，其余后面的元素也按照这个方法对应比如{-3，-9，-1，9}，我们将它对应为{6，0，8，17}，在这里例子中，我们将每个值都加了这个最小值的绝对值。即每个值减去最小值，(-3) - (-9) =6,(-9) -(-9)=0等等诸如此类。新数组的下标j = 原来元素arr[i] - min

现在将上面的第三步进行更清晰的解释：3. 将新数组count中的（下标 j+min）这个值在，在原数组arr中写arr[j]次。

那到时候，看着count数组的下标，如何反应过来原数组的值是多少呢？值=j+min.

3. 还需要关注：新数组创建好之后，它的初始值都设为0.（使用memset()函数）

void CountSort(int* arr, int n)
{//先确定最大最小值int max = arr[0]; int 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 new_n = max - min + 1;int* count = (int*)malloc(sizeof(int) * new_n);if (count == NULL){perror("malloc fail!");exit(1);}//初始化新数组memset(count, 0, new_n * sizeof(int));//统计次数for (int i = 0; i < n; i++){count[arr[i] - min]++;}//将count中的数据，按特定方法，往arr中放int new_index = 0;  // new_index是新数组下标for (int i = 0; i < new_n; i++)  //i代表count数组下标{while (count[i]--){arr[new_index++] = i + min;}}
}