数据结构——排序（3）：交换排序（续）

目录

一、快速排序

(1)hoare版本

①思路

②过程图示

③思考

④代码实现

⑤代码解释 

（2）挖坑法

①思路

②过程图示

③思考

④代码实现

⑤代码解释

（3）lomuto前后指针

①思路

②过程图示

③思考

④代码实现

⑤代码解释

（4）快速排序的复杂度

（5）非递归版本

①代码实现

②代码解释

二、写在最后

---

一、快速排序

我们上次学到了快速排序的递归方式，但是找基准值的函数（_QuickSort）如何实现呢？

(1)hoare版本

①思路

首先创建左右指针来寻找基准值。具体步骤为

一个指针从左到右找出比基准值大的数据，另一个指针从右到左找出比基准值小的数据，交换两者的位置，进入下一次循环。

②过程图示

1. 首先key指向第一个数据，left指向第二个数据，right指向最后一个数据；

2.right从右向左遍历找比key小的数据（3），left从左向右遍历找比key大的数据（7）；

3.将两者交换位置；

4..right往后走一步，left往前走一步；（此时两者相遇）

5.right向左找比key小的数据（3），left向右找比key大的数据（9）；（此时，left走到了right右边，跳出循环）；

6.将right位置和key位置的数据交换位置，此时right位置的数据就是我们要找的key值（基准值）；

7.基准值为6，此时基准值左侧的数据比其小，右侧的数据比其大。

③思考

1.若left==right是否继续循环？

 场景1：过程图示中的例子，此处不再赘述。

假设left==right时不再进行循环，则：

此时得到基准值为6，但是不满足“基准值左边都是小于它的数据，基准值右边都是大于它的数据”。 

---

场景2：

1. 首先key指向第一个数据，left指向第二个数据，right指向最后一个数据；

2.right从右向左遍历找比key小的数据（3），left从左向右遍历找比key大的数据（7）；

3.将两者交换位置；

4.right往后走一步，left往前走一步；（此时两者相遇）

5.right找到了比基准值<=的数据（6），left找到了比基准值>=的数据（6）；（此时，left走到了right右边，跳出循环）；

6.将right位置和key位置的数据交换位置，此时right位置的数据就是我们要找的key值（基准值）；

7.基准值为6，此时基准值左侧的数据比其小，右侧的数据比其大（或等于）。

---

 场景3：

1. 首先key指向第一个数据，left指向第二个数据，right指向最后一个数据；

2.right从右向左遍历找比key小的数据（3），left从左向右遍历找比key大的数据（7）；

3.将两者交换位置；

4.right往后走一步，left往前走一步；（此时两者相遇）

5.right找到了比基准值小的数据（4），left找到了比基准值大的数据（7）；（此时，left走到了right右边，跳出循环）；

6.将right位置和key位置的数据交换位置，此时right位置的数据就是我们要找的key值（基准值）；

7.基准值为6，此时基准值左侧的数据比其小，右侧的数据比其大。

---

通过场景1我们得出left==right仍继续循环，否则在“相遇值大于key值”的情况下会出错！

---

2.当left或right指向的值与key相等时，是否进行交换？

我们以数组{6，6，6，8，6，6}为例：

（1）假设left或right指向的值与key相等时交换：

在第三次交换中，left和right相遇，我们不跳出循环（思考1中已经解释）。因此得到基准值为6。 

---

 （2）假设left或right指向的值与key相等时不交换： 

1. 首先key指向第一个数据，left指向第二个数据，right指向最后一个数据；

2.right从右向左遍历找比key小的数据，没找到且越界了（此时left在right右边，跳出循环）；

3.将right位置与key交换（right和key在同一个位置，相当于没交换）；

4.基准值为6，那么没有左子树。

如果left或right指向的值与key相等时不交换，对于这种情况，分割后数据的个数为：n、n-1、n-2……并不是我们理想的类似于二叉树的分割，效率较低。

---

我们得出left或right指向的值与key相等时应该交换，否则效率会降低！

---

④代码实现

int _QuickSort(int* arr, int begin, int end)
{int left = begin;int right = end;int key = left;left++;while(left <= right){while(left <= right && arr[right] > arr[key]){right--;}while(left <= right && arr[left] < arr[key]){left++;}if(left <= right){swap(&arr[left++], &arr[right--]);}}swap(&arr[right], &arr[key]);return right;}

⑤代码解释 

首先我们让left位于第二个数据位置，right位于最后一个数据的位置，假设key为第一个数据。在left<=right的情况下，right从右向左找小于基准值的数据，left从左向右找大于基准值的数据，当两者均找到时交换位置，（不要忘记让两者继续遍历），直至left>right跳出循环。

（2）挖坑法

①思路

创建两个指针left和right，第一个数据的位置为“坑”。right从右向左找出比基准值小的数据，放入“坑”中，当前位置变成新的“坑”；接着lleft从左向右找出比基准值大的数据，放入“坑”中，当前位置又变成新的“坑”。以此循环……最后将最开始“坑”位置的值放入当前位置的坑中，当前位置即基准值。

②过程图示

我们以数组{6，1，2，7，9，3}为例：

1.首先left、hole指向第一个数据，right指向最后一个数据；

2.right找到比基准值小的数据（3），将该位置的数据放入原来的坑中，该位置变成新的“坑” ；

3.left找到比新基准值大的数据（7），将该位置的数据放入原来的坑中，该位置变成新的“坑”；

4..right找到比新基准值<=的数据（7），将该位置的数据放入原来的坑中，该位置变成新的“坑” ；

5.将最开始坑位置的数据放在当前坑中，当前数据为基准值。

③思考

1.若left==right是否继续循环？

假设left==right继续循环：

我们得到基准值为6，不满足“基准值左边都是小于它的数据，基准值右边都是大于它的数据”。

---

因此若left==right时不继续循环 ！

---

 2.当left或right指向的值与key相等时，是否将其设为新的“坑”？

假设当left或right指向的值与key相等时，将其设为新的“坑”：

我们可以看到，如果将其设为新的坑，会降低效率。

---

因此，当left或right指向的值与key相等时，不必将其设为新的“坑”！

---

④代码实现

int _QuickSort(int* arr, int left, int right)
{int mid = arr[left];int hole = left;int key = arr[hole];while(left < right){while(left < right && arr[right] >= key){right--;}arr[hole] = arr[right];hole = right;while(left < right && arr[left] <= key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}

⑤代码解释

创建两个指针left和right，第一个数据的位置为“坑”。在left<right的情况下，right从右向左找出比基准值小的数据，放入“坑”中，当前位置变成新的“坑”；接着lleft从左向右找出比基准值大的数据，放入“坑”中，当前位置又变成新的“坑”。以此循环……最后将最开始“坑”位置的值放入当前位置的坑中，返回当前位置（即基准值）。

（3）lomuto前后指针

①思路

创建前后两个指针，从左向右找比基准值小的数据进行交换，使小的数据都排在基准值的左边。

②过程图示

我们以数组{6，1，2，7，9，3}为例：

1. prev指向第一个数据，cur指向第二个数据位置，key指向第一个数据位置；

2.此时cur指向的数据小于key，但是prev的下一个数据为cur；

3.让cur往后走一步；

4.此时cur指向的数据也小于key，但是prev的下一个数据仍为cur；

5.让cur继续往后走一步；

6.此时cur指向的数据小于key且prev的下一个数据不为cur，我们让prev和cur位置的数据交换位置；

7.cur继续往后走，此时越界，跳出循环；

8.让key和prev位置的数据交换；

9.此时prev位置的数据就是我们要找的基准值（prev左边的数据都比它小，prev右边的数据都比它大）。

③思考

1.当cur==right是否继续循环？

当然继续循环，在这个代码中，cur相当于在前面遍历，需要遍历到每个元素，而right位置的元素就是最后一个元素。

---

2.如果cur和key指向的元素相同，cur和prev是否交换？

其实两者情况的结果是一样的。

---

解释：

我们以数组{6，6，6，6，6}为例：

如果相等不交换：

 如果相等交换：

因此，相等交不交换都是一样的，要么递归左区间，要么递归右区间（二叉树理想下为递归左右区间）。对于全部相等的数组，复杂度都很高。 

④代码实现

int _QuickSort(int* arr, int left, int right)
{int prev = left;int cur = left + 1;int key = left;while(cur <= right){if(arr[cur] < arr[key] && ++prev != cur)//如果prev和cur相同就不进行交换{swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[key], &arr[prev]);return prev;
}

⑤代码解释

我们先假定第一个元素是基准值，用cur来递归数组的每一个元素，如果小于（或小于等于）基准值，我们设法将它放在前面，即将其放在cur前面的prev位置（prev是一直在++的），循环进行。最后将key和prev交换位置，返回的prev即为基准值。

（4）快速排序的复杂度

1.时间复杂度：O(N*logN)；

2.空间复杂度：O(logN)。

（5）非递归版本

需要借助数据结构——栈 。

①代码实现

void QuickSortNonR(int* arr, int left, int right)
{Stack 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 key = begin;int prev = begin;int cur = begin + 1;//找基准值while(cur <= end){if(arr[cur] < arr[key] && ++prev != cur){swap(&arr[prev], &arr[cur]);}cur++;}swap(&arr[key], &arr[prev]);key = prev;//右子树if(key + 1 < end){StackPush(&st, end);StackPush(&st, key + 1);}//左子树if(begin < key -1){StackPush(&st, key - 1);StackPush(&st, begin);}}StackDestroy(&st);
}

②代码解释

首先非递归实现排序，我们用到栈，也就是说用栈来模拟递归。

二、写在最后

至此，我们已经学习了插入排序、选择排序、交换排序，还剩下最后一个归并排序，我们下期见~