快速排序算法
快速排序（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两边的阵列分别执行此步骤，然后再分解阵列，直到阵列不能再分解为止（只有一个数据），才能得到正确结果。
示例程式码
Rubydef quick_sort(a)
(x=a.pop) ? 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 {
while(i /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
{
j--;/*向前寻找*/
}
a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
a[left]，那么就是给key）*/
while(i = 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 为止*/
}
JavaScriptconst 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 while (i 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
}
Javaclass Quick {
public void sort(int arr[],int low,int high) {
int l=low;
int h=high;
int povit=arr[low];
while(l while(l=povit)
h--;
if(l arr[l]=arr[h];
l++;
}
while(l l++;
if(l arr[h]=arr[l];
h--;
}
}
arr[l]=povit;
print(arr);
System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+" ");
if(l-1>low)sort(arr,low,l-1);
if(h+1 }
}
/*//////////////////////////方式二////////////////////////////////*/
更高效点的程式码：
public>
T[]quickSort(T[]targetArr,intstart,intend)
{
inti=start+1,j=end;
Tkey=targetArr[start];
SortUtilsUtil=newSortUtil();
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)if(i>=j)break;
sUtil.swap(targetArr,i,j);
if(targetArr[i]==key)
{
j--;
}else{
i++;
}
}
/*关键资料放到‘中间’*/
sUtil.swap(targetArr,start,j);
if(start{
this.quickSort(targetArr,start,i-1);
}
if(j+1{
this.quickSort(targetArr,j+1,end);
}
returntargetArr;
}
/*//////////////方式三：减少交换次数，提高效率/////////////////////*/
private>
voidquickSort(T[]targetArr,intstart,intend)
{
inti=start,j=end;
Tkey=targetArr[start];
while(i{
/*按j--方向遍历目标阵列，直到比key小的值为止*/
while(j>i&&targetArr[j].compareTo(key)>=0)
{
j--;
}
if(i{
/*targetArr[i]已经储存在key中，可将后面的数填入*/
targetArr[i]=targetArr[j];
i++;
}
/*按i++方向遍历目标阵列，直到比key大的值为止*/
while(i/*此处一定要小于等于零，假设阵列之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/
{
i++;
}
if(i{
/*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 {
/*从后向前搜寻比key小的值*/
while (array[high] >= key && high > low)
--high;
/*比key小的放左边*/
array[low] = array[high];
/*从前向后搜寻比key大的值，比key大的放右边*/
while (array[low] low)
++low;
/*比key大的放右边*/
array[high] = array[low];
}
/*左边都比key小，右边都比key大。//将key放在游标当前位置。//此时low等于high */
array[low] = key;
foreach (int i in array)
{
Console.Write("{0} ", 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毫秒。
