c语言-快速排序

目录

一、实现快速排序三种方法

 1、hoare法

2、挖坑法

3、双指针法

4、快速排序的优化

5、测试对比

结语：

---

前言：

        快速排序作为多种排序方法中效率最高的一种，其底层原理被广泛运用，他的核心思想与二叉树结构中的递归逻辑相似，首先标记一个元素作为基准点，然后利用该基准点把数组分成左右两个区间，并且使小于该基准点的元素放在左区间，大于该基准点的元素放在右区间，如此反复递归，直到数组为一个有序数组。

        实现快速排序的原理有三种方法：hoare方法，挖坑方法，双指针方法。

一、实现快速排序三种方法

 1、hoare法

        比如将一个数组的起始位置记成left，最后一个元素位置记成right，那么标记left的位置的元素，把该元素看成基准点（key）。

---

        .这时候right要不断的向左移动，若right所在位置的元素是小于key位置的元素，那么right停止移动。left要不断的向右移动，若left所在位置的元素是大于key位置的元素，那么left停止移动。总结就是：left找大，right找小。（注意：若将left设置为key，则先移动right然后才能移动left）

---

         当left和right都停下来后，把他们的元素进行交换，交换过后继续移动。

---

        如此反复操作，最后left会走到right的位置，这时候left和right是处于同一位置的，把该位置的元素和key位置的元素进行交换，更新key的位置。

---

        可以观察到，此时数组有了一个特点：以key为中心点，左边区间的元素都是小于基准点key元素的，右边区间的元素都是大于key元素的。

---

        但是此时数组并不是一个有序的数组，所以要通过多重递归，因此将左边区间又看成一个小数组，右边区间也看成一个小数组。此时左边区间的left就是下标为0的位置，左边区间的right是key-1的位置。右边区间的left是key+1的位置，right是整个大数组的末尾处，既大数组的right。通过递归不断让每个小数组变得有序，最后整个数组也就有序了。

        递归逻辑图如下：

        hoare版本快速排序代码实现：

#includevoid swap(int* p1, int* p2)//交换函数{int temp = *p1;*p1 = *p2;*p2 = temp;}int PatrSort1(int* a, int left, int right)//hoare法{int key = left;//定义基准点keywhile (left  
        运行结果：
  
2、挖坑法
 
        思路：和hoare法一样先定义一个基准点，只不过把这个基准点叫做“坑”，“坑”里的元素是要被抹除的（也就是“坑”里不能有元素），因此先用一个变量key来保存“坑”里的元素。right向左移动找到小于该基准点（“坑”）的元素就把这个元素填到“坑”里，这时候“坑”里有了元素，可以表示“坑”被填满了，但是right位置的就变成了新的“坑”，因为right位置的元素被用来“填坑”了。
  
        下一次就是left找大的元素给到right位置的”坑“，然后left的位置就成了新坑，如此反复，直到left和righ相遇，待到他们相遇的位置必然是一个”坑“，这时候把key存储的元素放到这个”坑“里，此时会发现数组也以5（key）为中心点分成了两个区间，而且左区间的元素都是小于key的，右区间的元素都是大于key的。
  
        挖坑法代码实现快速排序：
 
#includevoid swap(int* p1, int* p2)//交换函数{int temp = *p1;*p1 = *p2;*p2 = temp;}int PatrSort2(int* a, int left, int right)//挖坑法{int key = a[left];//把基准点元素的值保存起来int hole = left;//设置hole更加形象表示坑while (left = key)//right找小{right--;}a[left] = a[right];//填坑hole = right;//right处变成新坑if (left  
        运行结果：
  
        从结果可以看到，不管是挖坑法还是hoare法都可以实现排序，因为他们本身的逻辑是一样的。 
 
3、双指针法
 
        顾名思义就是依靠两个类似指针的变量去变量数组并且完成排序，首先定义一个变量prev和一个变量cur，分别在数组的第一个元素位置和第二个元素位置，cur在prev的后边（既cur在第二个元素位置），并且把prev的位置设置成key基准点。当cur遇到比key小的元素则prev往后走一步，然后prev的元素与cur的元素进行交换，交换过后cur继续走。当cur遇到比key大的元素则prev不动，cur继续走。
  
        最后当cur走到数组外面表示遍历结束，这时候prev所在位置的元素与key元素交换，并且作为新的基准点。
  
        此时数组也被分成了两个区间，并且左边区间的元素小于key，右边区间的元素大于key。 
 
        双指针法实现快速排序代码如下：
 
#includevoid swap(int* p1, int* p2)//交换函数{int temp = *p1;*p1 = *p2;*p2 = temp;}int PatrSort3(int* a, int left, int right)//双指针法{int key = left;//定义基准点int prev = left;//定义两个变量int cur = left + 1;while (cur  a[right])return right;elsereturn mid;}else{if (a[mid] > a[right])return mid;else if (a[right] > a[left])return left;elsereturn right;}}
 
5、测试对比
 
        通过测试对比优化前的快速排序的效率和优化后快速排序的效率，测试代码如下：
 
#include#include#includeint GetMid(int* a, int left, int right)//针对有序数组排序的三数取中{int mid = (left + right) / 2;//先定义一个mid中间值//对比他们三者之间的关系，选出三者之间的中间值if (a[left]  a[right])return right;elsereturn mid;}else{if (a[mid] > a[right])return mid;else if (a[right] > a[left])return left;elsereturn right;}}void swap(int* p1, int* p2)//交换函数{int temp = *p1;*p1 = *p2;*p2 = temp;}int PatrSort3(int* a, int left, int right)//双指针法{int key = left;//定义基准点int temp = GetMid(a, left, right);swap(&a[temp], &a[key]);//使keyi处的元素是三数取中的结果int prev = left;//定义两个变量int cur = left + 1;while (cur