八大排序——快速排序

Hello，大家好，今天分享的八大排序里的快速排序，所谓快速排序是一个叫霍尔的人发明，有很多人可能会觉得为什么不叫霍尔排序，其中原因就是因为它快，快速则体现了它的特点，今天我们就来讲一下快速排序，现在开始我们的学习吧。

快速排序

1.基本思想

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

实现逻辑

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

① 从数列中挑出一个元素，称为 “基准”（pivot），

② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

我们来看一下它的图是怎么实现的

首先我们给定它一个数组，并且定义左边为left，右边为right，然后我们的有个中间值，中间值这里我们就叫它为k，定义这个k是从left开始，当然我们也可以从right开始，等一下会来讲原因，现在我们只要看懂它的图就行

因为是从左边开始，所以要从右边先走，原因是我们这样才能确定left和right相遇的时候的值一定比k的值小，这里再详细展开讲解一下，我们的left和right相遇有两种可能，一种是left和right相遇，这个时候相遇是怎样的呢，因为right先走，遇到比k小的时候停下来，然后left又开始走，除非遇到比l大的值才会停下，否则就继续，但是我们还有一个结束条件那就是left要小于right，所以如果left没有找到比k大的值，他们就会相遇，那这样的话，因为我们right找到小的值了，所以最后k肯定比right所指向的值要大，还有一个就是我们right遇到left，那同样的道理，说明我们的right没有找到比k大的值，所以相遇之后也是一样的道理，结论就是相遇的值一定比k指向的值小。那我们再继续来看图

这个时候我们的right找到比k小的值，然后才开始动left，那我们现在开始动left

left也找到了，那现在就是交换它们的，这里我们用一个swap函数就可以了，因为后面还需要用到swap这个函数的，交换之后变成这样的

可以看到先在我们已经开始交换，我们找值需要一个两个while，外面还需要一个大while控制

那我们现在可以继续开始动right了

这下又找到了

开始动left

那现在我们需要交换他们

现在我们也交换好了，现在right在走一步就会爆炸（小编是小黑子，实锤了），这个时候循环就应该结束

我们需要做的就是在循环外面再进行k和left的交换

void swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
int PartSort(int* a,int left, int right)
{
  int k = left;
  while (left < right)
  {
    while ( a[right] > a[k])
    {
      right--;
    }
    while ( a[left] < a[k])
    {
      left++;
    }
    swap(&a[left], &a[right]);
  }
  swap(&a[left], &a[k]);
  return left;
}

这里其实会有问题，有两个问题，一个是会存在越界，一个就是会出现死循环，先讲一下死循环的例子，比如我们再第一次找left和right的值，这两个值的大小是相等的，那他们进行交换之后，left和right的值就不会变了，因为循环他们进不去了，所以要加一个等于的条件就行了，还有就是越界，我们之前讲过越界就像查酒驾一样，是有随机性的，为什么会越界，是因为right可能一直找不到小的值，然后就会比left还小，所以我们只需要加上一个条件就行了

看看代码

void swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
int PartSort(int* a,int left, int right)
{
  int k = left;
  while (left < right)
  {
    while (left < right && a[right] >= a[k])
    {
      right--;
    }
    while (left < right && a[left] <= a[k])
    {
      left++;
    }
    swap(&a[left], &a[right]);
  }
  swap(&a[left], &a[k]);
  return left;
}

现在就是这只是我们走了一遍并不能实现将他们变成有序数列，所以这里我们就可以用递归进行遍历，怎么进行遍历，为什么能进行遍历呢，我们来分析

会这样分成左边和右边，然后再左边和右边再进行我们上面的操作，那是不是和二叉树很 相似的，所以我们递归实现一下，这里不过多的讲解，等我更新二叉树的文章后，大家可能看起来就明白了

void QuickSort(int* a, int begin,int end)
{ 
  if (begin >= end)
    return;
  int ret = PartSort(a, begin, end);
  QuickSort(a, begin, ret - 1);
  QuickSort(a, ret + 1, end);
}

完整代码加测试代码

void swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
int PartSort(int* a,int left, int right)
{
  int k = left;
  while (left < right)
  {
    while (left < right && a[right] >= a[k])
    {
      right--;
    }
    while (left < right && a[left] <= a[k])
    {
      left++;
    }
    swap(&a[left], &a[right]);
  }
  swap(&a[left], &a[k]);
  return left;
}
void QuickSort(int* a, int begin,int end)
{ 
  if (begin >= end)
    return;
  int ret = PartSort(a, begin, end);
  QuickSort(a, begin, ret - 1);
  QuickSort(a, ret + 1, end);
}
#include<stdio.h>
int main()
{
  int arr[] = { 6,1,2,7,9,3,4,10,8 };
  QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
  for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
  {
    printf("%d ", arr[i]);
  }
  return 0;
}

反正最后排序成功了，这个挡住了一部分结果，我换个大的

好好好，今天的学习就到这吧，拜拜。。。。