1疯兼、算法描述
快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：
- 從數(shù)列中挑出一個元素穷吮，稱為 “基準”（pivot）鳞绕；
- 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面胳泉，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）拐叉。在這個分區(qū)退出之后岩遗，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作凤瘦；
- 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序宿礁。
2、動態(tài)演示
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梆靖、代碼實現(xiàn)
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);
}
