算法基础： 快速排序

快速排序

概念

快速排序从算法的思维上来看，其实与归并排序一致，都是分治的思想，归并排序是先局部有序再整体有序，快速排序是先整体大致有序再局部有序。

从实现的原理上来说，可以大概分为三步：1. 设置锚点分割区间，2.以锚点为中心左右整体有序，3.细分区间，直到只有一个值。

思路

大致步骤如下：

首先设置一个分界值也就是基准值又是也称为监视哨，通过该分界值将数据分割成两部分。

将大于或等于分界值的数据集中到右边，小于分界值的数据集中到左边。一趟排序过后，左边部分中各个数据元素都小于分界值，而右边部分中各数据元素都大于或等于分界值，且右边部分个数据元素皆大于左边所有数据元素。

然后，左边和右边的数据可以看成两组不同的部分，重复上述1和2步骤

当左右两部分都有序时，整个数据就完成了排序。

代码实现

 int Paritition1(int A[], int low, int high) {
   int pivot = A[low];
   while (low < high) {
     while (low < high && A[high] >= pivot) {
       --high;
     }
     A[low] = A[high];
     while (low < high && A[low] <= pivot) {
       ++low;
     }
     A[high] = A[low];
   }
   A[low] = pivot;
   return low;
 }

 void QuickSort(int A[], int low, int high) //快排母函数
 {
   if (low < high) {
     int pivot = Paritition1(A, low, high);
     QuickSort(A, low, pivot - 1);
     QuickSort(A, pivot + 1, high);
   }
 }