程序员必知的十大基础实用算法之-快速排序算法

快速排序算法

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤

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

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

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

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

排序演示

示例

假设用户输入了如下数组：

创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。

我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：

i=0 j=3 k=6

接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：

i=2 j=3 k=6

称上面两次比较为一个循环。

接着，再递减变量j，不断重复进行上面的循环比较。

在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大：

如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。

然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

示例代码

• Ruby

def quick_sort(a) 
 (x=a.pop) ? quick_sort(a.select { |i| i <= x }) + [x] + quick_sort(a.select { |i| i > x }) : []
end

• C语言

void sort(int *a, int left, int right)
{
 if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
 {
 return ;
 }
 int i = left;
 int j = right;
 int key = a[left];
 
 while(i < j) /*控制在当组内寻找一遍*/
 {
 while(i < j && key <= a[j])
 /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
 序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
 {
 j--;/*向前寻找*/
 }
 
 a[i] = a[j];
 /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
 a[left]，那么就是给key）*/
 
 while(i < j && key >= a[i])
 /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
 因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
 {
 i++;
 }
 
 a[j] = a[i];
 }
 
 a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
 sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
 sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
 /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

• JavaScript

const quickSort = (array) => {
 const sort = (arr, left = 0, right = arr.length - 1) => {
 if (left >= right) {//如果左边的索引大于等于右边的索引说明整理完毕
 return
 }
 let i = left
 let j = right
 const baseVal = arr[j] // 取无序数组最后一个数为基准值
 while (i < j) {//把所有比基准值小的数放在左边大的数放在右边
 while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
 i++
 }
 arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
 while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
 j--
 }
 arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
 }
 arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
 sort(arr, left, j-1) // 将左边的无序数组重复上面的操作
 sort(arr, j+1, right) // 将右边的无序数组重复上面的操作
 }
 const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
 sort(newArr)
 return newArr
}

• Java

class　Quick {
 　public　void　sort(int　arr[],int　low,int　high) {
 　int　l=low;
 　int　h=high;
 　int　povit=arr[low];
 
 　while(l<h) {
 　while(l<h&&arr[h]>=povit)
 　 h--;
 　if(l<h){
 　arr[l]=arr[h];
 　l++;
 　}
 
 　while(l<h&&arr[l]<=povit)
 　 l++;
 
 　if(l<h){
 　arr[h]=arr[l];
 　h--;
 　}
 　}
 arr[l]=povit;
 　print(arr);
 　System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");
 　if(l-1>low)sort(arr,low,l-1);
 　if(h+1<high)sort(arr,h+1,high);
 　}
}
 
 
/*//////////////////////////方式二////////////////////////////////*/
更高效点的代码：
public<TextendsComparable<?superT>>
T[]quickSort(T[]targetArr,intstart,intend)
{
inti=start+1,j=end;
Tkey=targetArr[start];
SortUtil<T>sUtil=newSortUtil<T>();
 
if(start=end)return(targetArr);
 
 
/*从i++和j--两个方向搜索不满足条件的值并交换
*
*条件为：i++方向小于key，j--方向大于key
*/
while(true)
{
while(targetArr[j].compareTo(key)>0)j--;
while(targetArr[i].compareTo(key)<0&&i<j)i++;
if(i>=j)break;
sUtil.swap(targetArr,i,j);
if(targetArr[i]==key)
{
j--;
}else{
i++;
}
}
 
/*关键数据放到‘中间’*/
sUtil.swap(targetArr,start,j);
 
if(start<i-1)
{
this.quickSort(targetArr,start,i-1);
}
if(j+1<end)
{
this.quickSort(targetArr,j+1,end);
}
 
returntargetArr;
}
 
 
/*//////////////方式三：减少交换次数，提高效率/////////////////////*/
private<TextendsComparable<?superT>>
voidquickSort(T[]targetArr,intstart,intend)
{
inti=start,j=end;
Tkey=targetArr[start];
 
while(i<j)
{
/*按j--方向遍历目标数组，直到比key小的值为止*/
while(j>i&&targetArr[j].compareTo(key)>=0)
{
j--;
}
if(i<j)
{
/*targetArr[i]已经保存在key中，可将后面的数填入*/
targetArr[i]=targetArr[j];
i++;
}
/*按i++方向遍历目标数组，直到比key大的值为止*/
while(i<j&&targetArr[i].compareTo(key)<=0)
/*此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/
{
i++;
}
if(i<j)
{
/*targetArr[j]已保存在targetArr[i]中，可将前面的值填入*/
targetArr[j]=targetArr[i];
j--;
}
}
/*此时i==j*/
targetArr[i]=key;//应加判断
 
/*递归调用，把key前面的完成排序*/
this.quickSort(targetArr,start,i-1);
 
 
/*递归调用，把key后面的完成排序*/
this.quickSort(targetArr,j+1,end);
//两个递归应加判断
}

• C#

 using System; 
 using System.Collections.Generic; 
 using System.Linq; 
 using System.Text;
 namespace test
{
 class QuickSort
 {
 static void Main(string[] args)
 {
 int[] array = { 49, 38, 65, 97, 76, 13, 27 };
 sort(array, 0, array.Length - 1);
 Console.ReadLine();
 }
 /**一次排序单元，完成此方法，key左边都比key小，key右边都比key大。
 
 
**@param array排序数组 
 
 
**@param low排序起始位置 
 
 
**@param high排序结束位置
 
 
**@return单元排序后的数组 */
 private static int sortUnit(int[] array, int low, int high)
 {
 int key = array[low];
 while (low < high)
 {
 /*从后向前搜索比key小的值*/
 while (array[high] >= key && high > low)
 --high; 
 /*比key小的放左边*/
 array[low] = array[high]; 
 /*从前向后搜索比key大的值，比key大的放右边*/
 while (array[low] <= key && high > low)
 ++low; 
 /*比key大的放右边*/
 array[high] = array[low];
 }
 /*左边都比key小，右边都比key大。//将key放在游标当前位置。//此时low等于high */
 array[low] = key;
 foreach (int i in array)
 {
 Console.Write("{0}\t", i);
 }
 Console.WriteLine();
 return high;
 } 
 /**快速排序 
*@paramarry 
*@return */
 public static void sort(int[] array, int low, int high)
 {
 if (low >= high)
 return; 
 /*完成一次单元排序*/
 int index = sortUnit(array, low, high); 
 /*对左边单元进行排序*/
 sort(array, low, index - 1);
 /*对右边单元进行排序*/
 sort(array, index + 1, high);
 }
 }
} 

时间复杂度

最好情况的时间复杂度为O(nlogn)，过程比较复杂，就不在此赘述。

最差情况下每一次取到的数（基准数）都是当前要比较的数中的最大/最小值，在这种情况下，每次都只能得到比上一次少1个数的子序列（即要么全比基准数大，要么全比基准小），此时相当于一个冒泡排序，比较的次数 = (n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2，此时的时间复杂度为：O(n^2)。最差情况一般出现在：待排序的数据本身已经是正序或反序排好了。

使用场景

基本上在任何需要排序的场景都可以使用快速排序。虽然快速排序的最坏情况时间复杂度为O(n^2)，但是由于基本不会出现，因此可以放心的使用快速排序。在本人的电脑测试，100万的随机数字，快速排序大约耗时120毫秒。