????本文著重介紹快速排序算法(quick sort)，快速排序和冒泡排序一樣是交換排序的一種怜俐，快速排序算法可以看成是對冒泡排序算法的改進算法，其平均時間復(fù)雜度在nlog(n),基本上是已知的排序算法中速度最快的一種邓尤。
????冒泡排序的核心思想是通過一次冒泡交換將最大的元素置換到末尾拍鲤，通過N-1次這樣的冒泡交換贴谎，完成對待排序數(shù)組的排序。
????快速排序的核心思想是通過一個partition(分割)操作季稳，將數(shù)組的某一個元素放置到正確的排序位置擅这，接著遞歸對該元素的左側(cè)和右側(cè)分別進行partition操作，直到所有的元素都放到正確的位置景鼠，這樣排序就結(jié)束了仲翎。
????下面通過一個圖例的方式來介紹對待排序數(shù)組的一次partition操作。假設(shè)待排序數(shù)組int []A = new int[]{5,1,4,7,9,3,2,5}莲蜘。
一丶快速排序原理
隨便選取一個元素(后文簡稱特定元素)谭确，這里選取第一個元素5，目的是將元素5放置到正確的排序位置票渠，讓元素5左側(cè)的元素都小于或等于5逐哈，右側(cè)的元素都大于5。
-
在partition操作中问顷，維護三個重要成員昂秃，left指針指向區(qū)間的第一個元素，right指針指向區(qū)間的最后一個元素杜窄，以及對選中元素額備份肠骆。
image -
移動right指針，right=right-1塞耕，一直到A[right]<=5,停止移動移動left指針蚀腿，left = left+1，一直到A[left]>5停止移動扫外。
image -
left指針移動和right指針移動結(jié)束后莉钙，交換left指針和right指針指向的內(nèi)容。
image -
繼續(xù)重復(fù)步驟2筛谚，3磁玉，4
image
image -
繼續(xù)重復(fù)步驟2，3驾讲，4發(fā)現(xiàn)left=right,兩個指針相遇了蚊伞，那么結(jié)束本次partition操作，讓 left和right共同指向的元素去覆蓋選中的元素5吮铭。
image
image -
將備份的元素5覆蓋left和right共同指向的元素时迫。
image 執(zhí)行完步驟7之后，一次的partion操作就結(jié)束了谓晌，將數(shù)組分割成的兩個部分掠拳，在指定元素5的左側(cè)，所有的元素都小于或等于5扎谎，在指定元素的右側(cè)所有的元素都大于5碳想。對左側(cè)的數(shù)組{3烧董，1，4胧奔，5逊移，2}和右側(cè)數(shù)組{9，7}遞歸partition操作龙填。遞歸執(zhí)行partition函數(shù)后胳泉，快速排序就完成了，數(shù)組也由無序變?yōu)榱擞行虻臓顟B(tài)了岩遗。
二丶快速排序的細節(jié)分析
(1)在一次partition操作中扇商，對特定元素的指定一般都取待排序區(qū)間中的第一個元素。
(2)left指針和right指針的移動順序是存在區(qū)別的宿礁，必須先移動right指針案铺，后移動left指針。試想當(dāng)left和right指針相遇的時候梆靖，若先移動right指針控汉，可以保證最后left和right指向的元素是嚴格小于或等于被指定元素的。這樣在執(zhí)行步驟7和步驟8之后返吻，可以完全的保證被指定元素放置在合適的位置——左側(cè)的所有元素小于自身姑子，右側(cè)的所有元素大于自身。
(3)快速排序的每一次partition操作测僵，必須輸入兩個參數(shù)——start和end街佑。start代表待排序區(qū)間的開始位置，end代表待排序區(qū)間的結(jié)束位置捍靠。
(4)每一次partition操作沐旨，必須返回特定元素分割后的位置，用作下一次partition操作的依據(jù)剂公。
(5)每次partition操作希俩，如果start>end.則不執(zhí)行partition流程吊宋。
三丶java代碼實現(xiàn)
public static void quickSort(int [] num,intstart,int end){
if(start>end)
return ;
int mid = partition(num,start,end);
quickSort(num,start,mid-1);
quickSort(num,mid+1,end);
}
public static int partition(int[] num,int start,int end){
int copy = num[start];
int left = start;
int right = end;
while(left<right){
while(left<right&&num[right]>copy){
right = right -1;
}
while(left<right&&num[left]<=copy){
left++;
}
int temp = num[left];
num[left] = num[right];
num[right] =temp;
}
num[start] = num[left];
num[left] = copy;
return left;
}
Referecne:
[1] 數(shù)據(jù)結(jié)構(gòu)與算法 java語言描述版
[2] 原文博客鏈接
