快速排序的核心思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
下面我们用图解的方式来演示这个排序过程：
假设下面这个数组是待排序数组：
（6, 1, 2, 7, 9, 3, 4, 5, 10, 8）
按照快速排序的思想，首先得把这组数分成相互独立的两部分，其中一部分比中的数比另一部分的数都小。如何实现这一步呢？
方法其实很简单：首先选取待排序数组的第一个数为基准数，也就是6，然后分别从初始序列“（6, 1, 2, 7, 9, 3, 4, 5, 10, 8）”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字8。
首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列为（6, 1, 2, 5, 9, 3, 4, 7, 10, 8）。
接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列为（6, 1, 2, 5, 4, 3, 9, 7, 10, 8）。
哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。3比6小所以我们将基准数6和3进行交换。交换之后的序列为（3, 1, 2, 5, 4, 6, 9, 7, 10, 8）。
此时第一趟排序结束，我们已经把待排序数组分成了以6为基准，左边一列序列，右边一序列，左边序列的数比右边序列的数都小。不过此时左右两部分中的数各自的排序仍然是混乱的，还有继续排序。
快速排序的排序过程已经通过上面的图解讲解清楚了，接下来左右两部分的数据继续按照快速排序的方式来排序。
其中左边的序列是（3, 1, 2, 5, 4），按照上面的排序图解哨兵j停下来的时候在2上面，哨兵i停下来的时候在5的上面，但此时哨兵i已经跑过哨兵j到他前面去了，所以此时不应该在把两个哨兵所对应的数交换，而应该把我们的基准数3和2交换，所以此时左侧的序列经过一次快速排序后变成了这样（2, 1, 3, 5, 4）。
右侧的序列经过一次快速排序后变成了这样（8, 7, 9, 10）。
合并基准数6以及左右两侧的序列：
(2, 1 || 3 || 5, 4 ||| 6 ||| 8, 7 || 9 || 10)
对于排序仍然混乱的部分继续以快速排序进行排序，最终的排序应该是这样的
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。
不同程序语言实现快速排序的代码示例：
//PHP
<?php
/**
* 快速排序
* @author chaselxu
*/
function qs($a, $s=0, $e=null) {
if($e === null) {
$e = count($a);
}
if($s >= $e) {
return $a;
}
$j = $e-1;
$i = $s;
$n = $a[$s];
//$ac = $a;
for(; $j>$i; $j--) {
if($a[$j] < $n) {
$t = $a[$i];
$a[$i] = $a[$j];
$a[$j] = $t;
for($i++;$i<$j;$i++) {
if($a[$i] > $n) {
$t = $a[$j];
$a[$j] = $a[$i];
$a[$i] = $t;
break;
}
}
}
}
//printf("\n[%s], %s ~ %s [%s] %s-%s-%s", implode($ac, ','), $s, $e, implode($a, ','), $i, $j, $e);
qs(&$a, $s, $i);
qs(&$a, $i+1, $e);
return $a;
}
$n = mt_rand(10000000, 99999999);
$n = '7,3,2,8,7,2,0,2';//trim(preg_replace('/(\d)/', '$1,', $n), ',');
$n = explode(',', $n);
echo "\n".implode($n, ',');
echo "\n".implode(qs($n), ',');#C++
#include <iostream>
using namespace std;
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];/*用字表的第一个记录作为枢轴*/
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/*将比第一个小的移到低端*/
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];
/*将比第一个大的移到高端*/
}
a[first] = key;/*枢轴记录到位*/
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
int main()
{
int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << "";
}
return 0;
}/*参考数据结构p274(清华大学出版社，严蔚敏)*/#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){
int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
l++;
}
while(l<h&&arr[l]<=povit)
l++;
if(l<h){
int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
h--;
}
}
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);
}#Python3 def quick_sort(data): """快速排序""" if len(data) >= 2: # 递归入口及出口 mid = data[len(data)//2] # 选取基准值，也可以选取第一个或最后一个元素 left, right = [], [] # 定义基准值左右两侧的列表 data.remove(mid) # 从原始数组中移除基准值 for num in data: if num >= mid: right.append(num) else: left.append(num) return quick_sort(left) + [mid] + quick_sort(right) else: return data # 示例： array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12] print(quickSort(array)) # 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]
