常用算法之快速排序

算法对开发的重要性不言而喻，所以准备记录一些常用算法。

本篇文章先介绍一下快速排序算法。这是在实际中最常用的一种排序算法，速度快，效率高。快速排序是非常优秀的排序算法。它是由是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，属于分治法(Divide-and-ConquerMethod)的一种。

算法思想：

1．先从数列中取出一个数作为基准数（理论上可以随便找一个）。

2．将比基准数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

举例说明：

40,20,10,70,50,60

排序过程（选取第一个元素作为基准（pivot））

pivot[40] 40,20,10,70,50,60 首先用40当作基准（pivot），使用low（红色表示，从左往右扫描） ，high（蓝色表示，从右向左扫描）两个指针分别从两边进行扫描，把比40小的元素和比40大的元素分开。首先比较40和60，60比40大，j左移

pivot[40] 40,20,10,70,50,60 比较40和50，60比40大，high左移

pivot[40] 40,20,10,70,50,60 比较40和70，70比40大，high左移

pivot[40] 40,20,10,70,50,60 比较40和10，10比40小，将10移动到40的位置（high停止移动）

pivot[40] 10,20,10,70,50,60 比较40和20，20比40小，low右移 （右移后low==high，将基准40放到此位置）

pivot[40] 10,20,40,70,50,60 第一次排序过程结束，此时已经把比40小的元素和比40大的元素分开（分治）。

对[10,20],[70,50,60]分别重复以上过程，知道完成排序。很明显这是一个递归过程。如下图是使用算法演示软件的演示效果（感谢软件的作者）：

代码如下：

public static void Qsort(int[] arr, int low, int high)
        {
 if (low >= high) return; //递归出口
 int partition = Partition(arr, low, high);      //将 >= x 的元素交换到右边区域，将 <= x 的元素交换到左边区域
 QsortCommon(arr, low, partition - 1);   //递归调用，对左部排序     
 QsortCommon(arr, partition + 1, high); //递归调用，对右部排序
  } 
 public static int Partition(int[] arr, int low, int high)
        {
 int first = low;
 int last = high;
 int key = arr[low]; //取第一个元素作为基准元
 while (first < last)
 {
 while (first < last && arr[last] >= key)
 last--;
 arr[first] = arr[last];
 while (first < last && arr[first] <= key)
 first++;
 arr[last] = arr[first];
 }
 arr[first] = key; //基准元居中
 return first;
        }

总结：快速排序算法利用分治法，将比基准小的都放到左边，将比基准大的放到右边（当然如果是降序排，则与之相反）。在排序过程中先从后往前扫描，在从后向前扫描。直到完成排序。另外快速排序有较多的改进版本（主要是对基准数的选取），如随机选取基准，中间数作为基准快排。这些都不讨论了，有兴趣的可以去了解了解。另外还有时间复杂度，因为快速排序不是稳定的排序，其最坏情况的时间复杂度Θ(n^2)，平均的时间复杂度O(nlogn）。其公式的数学推导，可以参考算法导论。