排序入门之快速排序简单入门

本文章只是简单讲解快速排序的原理，并没有深入进行讨论

希望这篇文章适合你  :)

快速排序被广泛认为它是解决一般问题的最佳排序算法，它比较适合解决大规模数据的排序。

原理思想：（顺序是从小到大）

快速排序首先选取一个“基准数”，通过基准数将大于它和小于它的数无序地放在基准数的两边

什么叫无序？就是大于基准数的所有数只需要放在它的右边，这些数之间不被要求为有序，同样，小于基准数的数所有只需要放在它的左边，不被要求其有序

这样就利用“基准数”对整个原始数列进行了分割成两部分，然后通过递归，用上述同样的方法选取一个基准数进行分割，直至整个数列被分割的各部分已不能再被分割

下面进行演示，基准数用定义一个变量 pivot 存放，每一部分的分割开始都是选择low下标对应的数

这里演示的就是代码中 partition函数 的实现

开始：（假设low=0，high=6.  当前的low是红色，high是绿色，pivot是蓝色，被放置好在基准数两边的数用蓝色字体表示）

首先，选取基准数进行分割，选择low下标当前的元素5为基准数，即pivot = 5

然后将 pivot 与 high 下标对应的数进行对比

结果如下：

注意！

在这个时候，因 pivot = 5 被交换到 high 的下标处

那么接下来的比较就是将pivot与low下标当前的数进行对比

这里是比low对应的数大，结果如下：

结果如下：

这时候 pivot = 5比 a[low] 小，所以又进行a[low] 与 a[high]交换

结果如下：

注意！

在这个时候，因pivot = 5被交换到low的下标处

那么接下来的比较就是将pivot与high下标当前的数进行对比

结果如下：

同样进行交换，结果如下：

结果如下：（low++）

结果如下：

结果如下：（high--）

结果如下：（最终结果low == high，橙色表示）

到这里，已经利用 基准数pivot = 5 把这个数列分为了两部分（5 的左边都是小于它的，右边都是大于它的）

然后递归。用同样的方法，对分割出来的两部分用“基准数”继续进行分割

/快排函数  void sort(int *s, int low, int high)  {      int    pivot;      //if语句的判断是结束递归的简单情景，不能缺      if (low < high)      {          // partition 函数就是利用基准数进行分割的功能函数，这个函数是重点          pivot = partition(s, low, high);            sort(s, pivot + 1, high);          sort(s, low, pivot - 1);       }  }  partition 函数代码：
//这个函数就是上面演示的代码实现  int partition(int *s, int low, int high)  {      int    pivot;      pivot = s[low];        while (low < high)      {          while (low < high && pivot <= s[high])          {              high--;          }          swap(&s[low], &s[high]);          while (low < high && pivot >= s[low])          {              low++;          }          swap(&s[high], &s[low]);      }      return  low;  }