数据结构-排序（2）

前言：

上一章节介绍了 排序中的插入排序和选择排序， 分别复盘了插入排序中的直接插入排序和希尔排序以及选择排序中的选择排序和堆排序。今天继续复盘交换排序。

目录

2.3交换排序

2.3.1冒泡排序

2.3.2快速排序

2.3.2快速排序非递归 

2.3交换排序

 基本思想：

     所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1冒泡排序
 

冒泡排序，已经很熟悉了，是我们接触的第一个排序，初学的时候，我单独对其进行了复盘，这里就不多介绍，可以根据下面动图和程序进行知识和程序的对比回忆：

程序代码： 

void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){bool exchange = false;for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1])//遍历到n - 1 会产生越界 所以这个地方要么 j = 1 前一个减一 要么遍历条件需要注意{swap(&a[j], &a[j + 1]);exchange = true;}}if (exchange == false){break;}}
}

 分析总结：

冒泡排序,通过两层遍历，第一层遍历数组中的每个元素，第二层遍历负责每个元素都要跟相邻的元素进行比较，找到自己的位置；所以当给的元素无序的时候，时间复杂度为o（N^2） 如果是有序的数组的话，我们可以通过设置标志位判断，减少时间复杂度，让其变为O(N)。

2.3.2快速排序

 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

 1.hoare版本

霍尔大佬思想就是快排最初版本，图解如下：

• 寻找合适的基准值key；

基准值可以是数组中的任意元素，但是为了程序方便，我们一般会选择两端。

• 2.定义两个下标L和R，我们让R先走，R从数组的右边往左边遍历，寻找比基准值小的数，L从左往右遍历，寻找比基准值大的元素，找到之后交换两个位置的元素。

开始出发进行寻找：

 找到元素后进行交换：

• 3.当两个下标相遇的时候，交换该下标的元素和基准值，基准值所在的位置就是它应该在的位置

 至此，霍尔大佬的单趟排序就完成，单趟排序我们确定了基准值key的最终位置，左边都比基准值小，右边都比基准值大，所以该位置为其最终位置，接下来我们使用二分的思想以。此基准值为分界点，将数组分成两部分，基准值的左区间和右区间，然后使用递归思想左区间，使用单趟排序，找到基准值，右区间同样，以此类推，结束条件就是区间不能划分，也就确定了最后一个key的位置，然后层层归回来。如下图所示：

代码如下： 

int PartSort1(int* a, int left, int right)
{int keyi = left;while (left < right){while (left<right && a[right] >= a[keyi]) // 要包含等于的条件 从右往左遍历{right--;}while (left < right && a[left] <= a[keyi]) 从左往右遍历{left++;}swap(&a[right], &a[left]);  //交换两个位置的数}swap(&a[left], &a[keyi]); 相遇后，相遇的位置就是key应该在的位置keyi = left;return keyi;
}

 复杂度分析：

因为是对数组进行二分，所以层数不会很多，只要分就会确定key，如下图示：

层数可以确定的是 logn，每一层都要进行寻找大小值；

这里需要注意的是，第一次，一个key 第二次就两个 以此 那就是 2^2,2^3.......每一次都要减掉确定的key 可以用具体数字来看，100w个数据 有 20层，第一层 1个k，第二十层 2^19 ，层数很少，所以寻找大小的次数累和加起来 可以近似看成 100w  上升到n个数据 时间复杂度也就是N*LOGN

通过分析我们可以注意到，如果 该数组是个有序数组，就会出现每一次确定的key只能在边上，这样时间复杂度就会上升到 O(N^2)，为了避免这样的问题，我们可以将key的选取进行优化，选取一个合适的key，具体代码如下;

//三个数，通过比较得到中间的数
int  GetmidNumi(int* a, int left, int right)
{int mid = (right - left) / 2;if (a[left] > a[mid]){if (a[mid] > a[right]){return mid;}else if (a[left] > a[right]){return right;}else{return left;}}else{if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}
}

 刚开始学的时候，我一直有个疑问，为什么左边为key的时候，右边要先走？为什么相遇的时候，一定是比key小的数或者和key相等，通过敲代码以及，画图分析，我明白了。具体分析如下：

为了演示，我只用四个数进行分析

因为左边是寻找大的值，右边是寻找小的值，如果L先走，相遇的时候，有可能会出现前面完成过交换，左遇右这样交换就会造成比key小的值虽然交换到左边，但是相遇后，key的值有可能交换到大的值得右边，如下图所示：

 右边先走的情况：只有两种情况

情况1：

r找到小，l没有找到大，相遇在r处 交换 满足

情况2：

r找小没找到，直接遇到l，要么就是bikey小的位置，要么就是key 。

2.挖坑法

   挖坑法就是在霍尔大佬的基础上，进行的改版，把基准值拿出来，让他的位置为坑，然后右边向左遍历寻找较小值，放进坑里然后自己成为新的坑，左边向右寻找较大值，交换后成为新的坑，两个坐标一定会在坑里相遇，然后将基准值填入。 示意图如下：

没有特别大的变动，代码如下：

// 挖坑法
int PartSort2(int* a, int left, int right)
{// 三数取中int mid = GetmidNumi(a, left, right);if (mid != left)swap(&a[left], &a[mid]);int keyi = a[left];//保存left内部数值，并将其当做坑位int hole = left;while (left < right){while (left < right && a[right] >= keyi){right--;}swap(&a[right], & a[hole]);hole = right;while (left < right && a[left] <= keyi){left++;}swap(&a[left], &a[hole]);hole = left;}a[hole] = keyi;//swap(&a[left], &keyi);return hole;
}

3.前后指针法

前后指针法，是针对前面提到的，左基值，右先走，右基值，左先走，混淆的情况做的改进，利用prev和cur两个前后指针，cur指针往前遍历，寻找比基值小的数 往前堆和prev交换，遍历完毕后，所有比基值小的数都堆在前面，这时候prev所在的位置是最后一个比基值小的数，将其和基值替换，就确定了基值的最终位置，动态图解如下：

如果cur的位置元素比基值小，prev和cur相邻的话，prev右移和cur下标相同的话，就不需要交换，同位置，如下图所示：

整体变化，交换如下： 

代码如下： 

// 前后指针法
int PartSort3(int* a, int left, int right)
{// 三数取中int mid = GetmidNumi(a, left, right);if (mid != left)swap(&a[left], &a[mid]);int keyi = left; // 方便返回下标int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur) // 需要注意的是 即使他俩相邻的时候，不交换prv也是要++的 这点主要不要再次犯错{swap(&a[cur], &a[prev]);}++cur;}swap(&a[prev], &a[keyi]);keyi = prev;return keyi;}

 快速排序，单趟排序确定一个key位置，但是他就像堆一样，二分二分之后，最后一层节点个数占了整体节点的一半，如果还去递归调用的话，会增加时间复杂度，所以我们可以小区间优化一下，在最后基层的时候，采用插入排序，优化如下：

void QuickSort1(int* a, int left, int right)
{// 结束递归条件if (left >= right) return;// 单趟确定 keyi位置//	// 小区间优化--小区间直接使用插入排序if ((right - left + 1) > 10){int keyi = PartSort3(a, left, right);//int keyi = PartSort1(a, left, right);//int keyi = PartSort2(a, left, right);QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);}else{InsertSort(a + left, right - left + 1);}}

2.3.2快速排序非递归 

递归的思想是层层调用，但内存空间是有限的，层层调用 ，就会面对栈溢出的问题，所以解决大数据快排，引入了快排非递归，通过模拟栈，将需要递归的区间，存进栈内，然后取出确定key的位置，然后将其左右区间存入栈，再次取出确定下个区间的key位置，直到剩一个元素不用存入栈内。数组也就有序了。整体思想还是跟快排递归一样，只是将开辟数组，变成入栈的时候，开辟区间左右端下标的空间，大大减少空间的开辟。

图解如下：

代码如下：

void QuickNorSort(int* a, int left, int right)
{//定义一个栈， 并初始化ST st;StackInit(&st);// 将数组左右下标入栈StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int keyi = PartSort3(a, begin, end);if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}if (begin < keyi - 1){StackPush(&st, keyi - 1);StackPush(&st, begin);}}StackDestroy(&st);}