年底總是忙碌的時(shí)候........

作為一個(gè)極少刷算法的java開發(fā)，突然刷算法題很吃力，算法里常用到的思想基本不了解，比如分治、動(dòng)態(tài)規(guī)劃、貪心等。淚崩~

這篇文章整理排序算法----快速排序

快速排序（時(shí)間復(fù)雜度O(nlogn)）作為排序算法中的佼佼者，同樣采用分治的思想。

基本思想：

快速排序的主要思想是分治法。主要思路：

1、首先設(shè)定一個(gè)基準(zhǔn)值，通過(guò)該基準(zhǔn)值值將數(shù)組分成左右兩部分

2、將大于基準(zhǔn)值的數(shù)據(jù)集中到數(shù)組右邊，將小于基準(zhǔn)值的數(shù)據(jù)集中到數(shù)組左邊

3、左邊和右邊的數(shù)據(jù)再做獨(dú)立排序，各取基準(zhǔn)值，再分成兩部分，以此類推，可以看出這是一個(gè)遞推操作。

核心思路：

選一個(gè)基準(zhǔn)值（一般選擇第一個(gè)作為基準(zhǔn)值）。

一次循環(huán)中：從后往前比較（索引end），如果比基準(zhǔn)值小，則與基準(zhǔn)值交換位置；從前往后比較(索引start)，如果比基準(zhǔn)值大，則與基準(zhǔn)值交換位置。直到 索引end 小于 索引 start， 一次循環(huán)結(jié)束，基準(zhǔn)值左邊都是比基準(zhǔn)值小的數(shù)據(jù)（沒(méi)有順序），基準(zhǔn)值右邊都是比基礎(chǔ)值大的數(shù)據(jù)。

再依據(jù)基準(zhǔn)值將左右分成兩部分，重復(fù)上面操作。

圖解思路：

通過(guò)示例來(lái)了解快速排序。原數(shù)組如下：

基準(zhǔn)值key = 72；左邊索引start = 0；右邊索引end=4;

一次循環(huán)：

從后往前比較，當(dāng) end = 4時(shí)，值60小于基準(zhǔn)值72，交換位置。如下：

再?gòu)那巴蟊容^，當(dāng)start = 3時(shí)，值88大于基準(zhǔn)值72，交換位置。如下：

從后往前比較，當(dāng) end = 3時(shí)，start = end，一次循環(huán)結(jié)束。此時(shí)左邊數(shù)據(jù)都是比基準(zhǔn)值小的，右邊數(shù)據(jù)都是比基準(zhǔn)值大的。

依據(jù)基準(zhǔn)值將左右分成兩部分。如下：

左邊：

1578476018111.png

右邊：

1578476048564.png

重新選擇基準(zhǔn)值，如左邊部分，基準(zhǔn)值key = 60，再?gòu)暮笸氨容^，從前往后比較，循環(huán)操作。

完整的快速排序代碼（java）

/**
 * 快速排序
 *  * 算法思路：
 *  *     1、首先設(shè)定一個(gè)分界值，通過(guò)該分界值將數(shù)組分成左右兩部分
 *  *     2、將大于分界值的數(shù)據(jù)集中到數(shù)組右邊，將小于分界值的數(shù)據(jù)集中到數(shù)組左邊
 *  *     3、左邊和右邊的數(shù)據(jù)再做獨(dú)立排序，各取分界值，再分成兩部分，以此類推，可以看出這是一個(gè)遞推操作
 */
public class QuickSort {
?
 public static void sort(int[] arr, int left, int right) {
?
   int start = left;
   int end = right;
   int key = arr[left];//取基準(zhǔn)值，一般取第一個(gè)
?
   while (start < end) {
   // 從后往前 找到第一個(gè)比基準(zhǔn)值小的,并交換位置
   while (arr[end] >= key && start < end) {
     --end;
   }
  if (arr[end] <= key) {
     int temp = arr[end];
     arr[end] = arr[start];
     arr[start] = temp;
  }
?
   // 從前往后 找到第一個(gè)比基準(zhǔn)值大的
   while (arr[start] <= key && start < end) {
     ++start;
   }
?
   if (arr[start] >= key) {
     int temp = arr[start];
     arr[start] = arr[end];
     arr[end] = temp;
   }
 }
 //此時(shí)第一次循環(huán)比較結(jié)束，基準(zhǔn)值的位置已經(jīng)確定了。
 //左邊的值都比基準(zhǔn)值小，右邊的值都比基準(zhǔn)值大，但是兩邊的順序還有可能是不一樣的，進(jìn)行下面的遞歸調(diào)
?
 //遞歸
 if (start > left) {  //左邊序列。第一個(gè)索引位置到關(guān)鍵值索引-1
   sort(arr, left, start - 1);
 }
 if (end < right) { //右邊序列。從關(guān)鍵值索引+1到最后一個(gè)
   sort(arr, end + 1, right);
 }
?
?
 }
?
 public static void main(String[] args) {
?
     int[] arr = {72, 6, 57, 88, 60};
     sort(arr, 0, arr.length - 1);
     System.out.println(Arrays.toString(arr));
 }
}

復(fù)雜度：

• 最好情況

  在最好的情況下，每次我們進(jìn)行一次分區(qū)，我們會(huì)把一個(gè)序列剛好分為幾近相等的兩個(gè)子序列，這個(gè)情況也我們每次遞歸調(diào)用的是時(shí)候也就剛好處理一半大小的子序列。這看起來(lái)其實(shí)就是一個(gè)完全二叉樹，樹的深度為 O(logn)，所以我們需要做 O(logn) 次嵌套調(diào)用。但是在同一層次結(jié)構(gòu)的兩個(gè)程序調(diào)用中，不會(huì)處理為原來(lái)數(shù)列的相同部分。因此，程序調(diào)用的每一層次結(jié)構(gòu)總共全部需要 O(n) 的時(shí)間。所以這個(gè)算法在最好情況下的時(shí)間復(fù)雜度為 O(nlogn)。

  事實(shí)上，我們并不需要如此精確的分區(qū)：即使我們每個(gè)基準(zhǔn)值把元素分開為 99% 在一邊和 1% 在另一邊。調(diào)用的深度仍然限制在 100logn，所以全部運(yùn)行時(shí)間依然是 O(nlogn)。

• 最壞情況

  事實(shí)上，我們總不能保證上面的理想情況。試想一下，假設(shè)每次分區(qū)后都出現(xiàn)子序列的長(zhǎng)度一個(gè)為 1 一個(gè)為 n-1，那真是糟糕透頂。這一定會(huì)導(dǎo)致我們的表達(dá)式變成：

  這和插入排序和選擇排序的關(guān)系式真是如出一轍，所以我們的最壞情況是 O(n2)。

參考文獻(xiàn)：

http://www.itdecent.cn/p/69dc714f407a
http://www.itdecent.cn/p/442399ef0cf7