快速排序是交換類的排序，比如在站隊的時候，老師說：“第一個同學出列，其他同學以第一個同學為中心，比他矮的全排在左邊，比他高的全排在右邊。”這就是一趟快速排序。可以看出，一趟快速排序是以一個“樞軸”為中心，將序列分成兩個部分，樞軸的一邊全是比它小（或者小于等于）的，另一邊則全是比它大（或者大于等于）的。

---

快速排序算法采用了一種分治的策略，通常稱其為分治法，其基本思想是：

1、先從數列中取出一個數作為基準數；
2、分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊；
3、再對左右區間重復第二步，直到各區間只有一個數。

---

以一個簡單的數組為例，我們來看一下，快速排序算法的排序過程：

再對array[0…1]和array[3..4]重復上述操作步驟就行了。

注意：在一次查找中只有i和j的值在變，X的值是一直保持不變的。

---

以上步驟總結為：

1、i=l，j=r，x=array[i];
2、j- -從后向前找小于等于x的數，找到后用array[j]替代array[i];
3、i++從前向后找大于x的數，找到后用array[i]替代array[j];
4、一直重復執行2、3步驟，直到i=j為止，最后將基準數寫入array[i]。

---

算法實現如下：

int quickSort(int s[], int l, int r){int i = l, j = r;int x = s[l]; //s[l]即s[i]為基準數/樞軸while (i < j){// 從右向左找小于x的數來替換s[i]while(i < j && s[j] >= x) {j--;}if(i < j){s[i] = s[j];i++;}// 從左向右找大于或等于x的數來替換s[j]while(i < j && s[i] < x){i++;}if(i < j){s[j] = s[i];j--;}}//退出時，i等于j。將基準數填到這個位置上。s[i] = x;//返回調整后基準數的位置return i; }

java代碼實現如下：

public class quickSortDemo {public static void quickSort(int[] array, int left,int right){if (left < right){int i = left, j = right, x = array[left];//從右向左找第一個小于x的數放到array[i]中while (i < j){while(i < j && array[j] >= x){j--; }if(i < j){array[i] = array[j];i++;//等價于array[i++] = array[j]}//從左向右找第一個大于等于x的數放到array[j]中while(i < j && array[i] < x){i++; }if(i < j){array[j] = array[i];j--;//等價于array[j--] = array[i]}}array[i] = x;//遞歸調用quickSort(array, left, i - 1); quickSort(array, i + 1, right);}}public static void main(String[] args) {int[] array = {2,7,9,3,5,6,1,8};quickSort(array,0,7);for (int k = 0; k < array.length; k++) {System. out.println(array[k]);}} }

---

時間復雜度：

快速排序算法最好情況下的時間復雜度為O(N*logN){以2為底數}，待排序序列越接近無序，算法效率越高。最壞情況下的時間復雜度為O(N2){n的平方}，待排序序列越接近有序，算法效率越低。平均時間復雜度為O(N***logN){以2為底數}**。就平均時間而言，快速排序算法是所有排序算法中最好的快速排序的排序趟數和初始序列有關。

---

空間復雜度：

快速排序算法的空間復雜度為O(logN){以2為底數}，快速排序是遞歸進行的，遞歸需要棧的輔助，因此快速排序算法需要的輔助空間比其他的排序算法多。

總結

以上是生活随笔為你收集整理的【大话数据结构算法】快速排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。