1、算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
2、动态演示
3、伪代码
function quick_sort(array,start,end){
if(start > = end){
return
}
int i=start
int j=end
int base=array[j]
while(i<j){
while(array[i]<=base&&i<j){
i++
}
while(array[j]=>base && j>i){
j--
}
swap[array[i],array[j]]
}
swap(base,array[j])
quick_sort(array,start,j-1)
quick_sort(array,j+1,end)
}
4、代码实现
public static void quick_sort(int[] array, int start, int end)
{
if (start >= end)
{
return;
}
int i = start;
int j = end;
int base = array[end];
while (i < j)
{
while (array[i] <= base && i < j)
{
i++;
}
while (array[j] >= base && j > i)
{
j--;
}
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
array[end] = array[j];
array[j] = base;
quick_sort(array, start, j - 1);
quick_sort(array, j + 1, end);
}
