快速排序思想
快速排序號(hào)稱20世紀(jì)最偉大的十大算法之一，也是nlogn級(jí)別的排序算法，它的思想是類似冒泡排序，是一種交換排序，同時(shí)加入分治法。
上圖中我們選取待排序數(shù)組第一個(gè)元素為基準(zhǔn)元素，通過(guò)比較交換，將比基準(zhǔn)元素小的元素放在左邊，比基準(zhǔn)元素大的放在右邊。那么此時(shí)基準(zhǔn)元素(紫色元素)，就放在了最終排序后數(shù)組應(yīng)該在的位置。然后通過(guò)同樣的方式，將左邊(綠色)和右邊(橙色)部分排序。過(guò)稱如下：
每輪分成3個(gè)步驟：
- 選取基準(zhǔn)元素
- 基準(zhǔn)元素方法排好序后的位置
- 繼續(xù)拆分，直到剩下一個(gè)待排序元素
如何編碼 ？
當(dāng)知道了思想后，下面就要考慮到編碼。不管是算法還是排序中，邊界的定義和指針的指向是最重要的兩個(gè)因素，只有定義好了邊界范圍和指針的含義才能寫(xiě)好算法。
待排序數(shù)組 4 7 6 5 3 2 8 1
按照上面的思想，定義一下邊界：
- 選取待排序數(shù)組第一個(gè)元素為基準(zhǔn)元素4
- 左邊邊界為l(left)，右邊界為r(right)，形成全閉區(qū)間
- j指向左邊<=4區(qū)域的第一個(gè)元素
- i執(zhí)行待比較的元素e
執(zhí)行邏輯 單邊循環(huán)法
由上面得知，兩個(gè)區(qū)間的范圍是[l+1...j]<=4和[j+1...r]>4，經(jīng)過(guò)上面一輪比較后，4就在放在排好序的位置，然后分成左右2部分，然后這兩部分再分別繼續(xù)上面的步驟。
代碼如下：
/**
* 單邊循環(huán)法
* @param arr 排序數(shù)組
* @param l 左邊界 起始0
* @param r 右邊界 其實(shí)length-1
*/
public static void quickSort(int[] arr, int l, int r) {
if (l >= r) {//只有一個(gè)元素 無(wú)需排序
return;
}
//找到 arr[l] 的位置
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
/**
*
* @param arr
* @param l
* @param r
* @return
*/
public static int partition(int[] arr, int l, int r) {
int v = arr[l];
//左邊區(qū)間為[l+1...j] 初始時(shí)j=l那么[l+1...l]是個(gè)無(wú)效區(qū)間
//其實(shí)就是初始化時(shí) 左邊區(qū)間是沒(méi)有元素的
int j = l;
for (int i = l + 1; i <= r; i++) {
// if(arr[i]>v){
// //上面知道 i++ 但是已經(jīng)在循環(huán)中了 那么就什么都不做
// }
if (arr[i] <= v) {
swap(arr, j + 1, i);
j++;
}
}
swap(arr, l, j);
return j;
}
上面的代碼，完全是按照我們分析的步驟寫(xiě)的。理解后在看下開(kāi)始的圖：
更能理解這里的思想和在遞歸中都做了什么
雙邊循環(huán)法
上面我們用的是單邊循環(huán)法，也就是i指針從左到右一直移動(dòng)。下面再介紹下雙邊循環(huán)法，也就是從兩邊循環(huán)。
雙邊循環(huán)，那么也就是需要兩個(gè)指針一起移動(dòng)。
- 數(shù)組范圍[satrtIndex...endIndex]
- left代表左區(qū)間最后一個(gè)元素[startIndex...left] 并不斷向右移動(dòng)
- left代表右區(qū)間最后一個(gè)元素[right...endIndex] 并不斷向左移動(dòng)
- 當(dāng) left和right 指向同一個(gè)元素截至
接下來(lái)進(jìn)行第1次循環(huán),從right指針開(kāi)始,讓指針?biāo)赶虻脑睾突鶞?zhǔn)元素做
比較。如果大于pivot ,則指針向左移動(dòng);如果小于等于pivot ,則right指針停
止移動(dòng),切換到left指針。
由于1eft開(kāi)始指向的是基準(zhǔn)元素,判斷肯定相等,所以left右移1位。
由于7>4 , 1eft指針在元素7的位置停下。這時(shí),讓left和right指針?biāo)赶虻脑?br> 素進(jìn)行交換。
第二次循環(huán)
代碼實(shí)現(xiàn)
public static void quickSort(int[] arr, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
int p = partition(arr, startIndex, endIndex);
quickSort(arr, startIndex, p - 1);
quickSort(arr, p + 1, endIndex);
}
public static int partition(int[] arr, int startIndex, int endIndex) {
int v = arr[startIndex];
int left = startIndex;
int right = endIndex;
while (left != right) {
//TODO 這里移動(dòng)是先移動(dòng)右邊 再移動(dòng)左邊 否則當(dāng) left=3 right=5 時(shí)
//先移動(dòng)左邊 那么left=right的位置在5的位置，那么4和5交換，最后顯然不是有序的
while (right > left && arr[right] > v) {
right--;
}
while (left < right && arr[left] <= v) {
left++;
}
if (left < right) {
swap(arr, left, right);
}
}
swap(arr, startIndex, left);
return left;
}
注意點(diǎn)
在TODO位置處這里移動(dòng)是先移動(dòng)右邊 再移動(dòng)左邊 否則當(dāng) left=3 right=5 時(shí)，先移動(dòng)左邊 那么left=right的位置在5的位置，那么4和5交換，最后顯然不是有序的
復(fù)雜度分析
上圖中也知道8個(gè)元素遞歸3輪，4個(gè)元素2輪，2個(gè)元素1輪，正好是log28=3,log24=2,log2^2=1,每輪排序O(n) ，所以是nlogn
優(yōu)化
1. 數(shù)據(jù)小的時(shí)候用插入排序，這個(gè)優(yōu)化和歸并一樣
2. 隨機(jī)選取基準(zhǔn)元素的選擇
如上圖，當(dāng)數(shù)組像上面時(shí)，每次選的基準(zhǔn)值要么最大，要么最小，就無(wú)法起到分治的效果，從而退化成O(n^2)，隨意可以隨機(jī)原則數(shù)組中的數(shù)值，然后與arr[0]交換，再在排序
3. 雙路排序
4. 三路排序
雙路排序
雙路排序思想，當(dāng)數(shù)組相同元素比較多的時(shí)候也會(huì)退化成O(n^2),如給定一個(gè)數(shù)組如下：
左邊相同元素非常多。導(dǎo)致分治不平均。最后算法退化O(n^2)。
雙路排序就是將拆分的2個(gè)數(shù)組分配到兩端，左邊遍歷的元素為ei，右邊遍歷元素為ej，當(dāng)ei>4=和ej<=4時(shí)交換。那么此時(shí)相同的元素就會(huì)分到2端,而不會(huì)只在一端，退化成O(n^2)。
代碼實(shí)現(xiàn)
//對(duì)arr[l...r]進(jìn)行快速排序
private static void quickSort(Comparable[] arr, int l, int r) {
// if (l >= r) {//當(dāng)l=r的時(shí)候說(shuō)明只有一個(gè)元素 那么他就是有序的
// return;
// }
if (r - l <= 15) {
Main5.sort(arr, l, r);
return;
}
/**
* TODO 優(yōu)化1 : 上面邊界的優(yōu)化 對(duì)于小規(guī)模數(shù)組, 使用插入排序
*
*
* if( r - l <= 15 ){
* InsertionSort.sort(arr, l, r);
* return;
* }
*
*
*/
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
/**
* 這個(gè)的特點(diǎn)就是 當(dāng)出現(xiàn)了值相等的情況 我們不具體像第一版代碼 給他劃分到某一端 而是取分布在兩端了
*
* @param arr
* @param l
* @param r
* @return
*/
// 雙路快速排序的partition
// 返回p, 使得arr[l...p-1] <= arr[p] ; arr[p+1...r] >= arr[p]
// 雙路快排處理的元素正好等于arr[p]的時(shí)候要注意，詳見(jiàn)下面的注釋：）
private static int partition(Comparable[] arr, int l, int r) {
// TODO 最重要的優(yōu)化： 隨機(jī)在arr[l...r]的范圍中, 選擇一個(gè)數(shù)值作為標(biāo)定點(diǎn)pivot
// 這樣我們和l交換 這樣退化成一個(gè)鏈表 也就是O(n*n)的概率是非常低的
swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);
//我們找到這個(gè)數(shù)組中第一個(gè)位置 也就是l的位置 為基準(zhǔn)數(shù)
Comparable v = arr[l];
// TODO arr[l+1...i) <= v; arr(j...r] >= v
int i = l + 1;
int j = r;
while (true) {
// 注意這里的邊界, arr[i].compareTo(v) < 0, 不能是arr[i].compareTo(v) <= 0
// 思考一下為什么?
//TODO 因?yàn)?如果相等 就違背了我們這么設(shè)計(jì)的初衷
// 如果我們存在很多相同的元素 原來(lái)的排序就會(huì)導(dǎo)致 相同的元素永遠(yuǎn)在一側(cè) ，如果這里加上等于號(hào)
// [1,1,1,1,1,1,2] 按照之前的邏輯 v我們?nèi)? 那么就會(huì)導(dǎo)致 一側(cè)是全數(shù)據(jù)
// 另一側(cè)只有2 如過(guò)不加等于 那么 根據(jù)我們的邏輯會(huì)分成[111] [1112] 分布均勻
while (i <= r && arr[i].compareTo(v) < 0) {
i++;
}
while (j >= l + 1 && arr[j].compareTo(v) > 0) {
j--;
}
// 對(duì)于上面的兩個(gè)邊界的設(shè)定
// 注意這里的邊界, j >= l + 1和i <= r, 不能是j > l + 1和i < r
// TODO 因?yàn)?這里的區(qū)間是arr[l+1...i) <= v; arr(j...r] >= v i和j是指向?qū)⒁判虻脑? // 所以i<r時(shí) i還沒(méi)有比較
// 大家可以參考: http://m.itdecent.cn/p/e0364a3166f9
if (i > j) {
break;
}
swap(arr, i, j);
i++;
j--;
}
swap(arr, l, j);
return j;
}
三路排序
明白了雙路排序，再來(lái)看三路排序，其本質(zhì)的事項(xiàng)是一樣的.
將數(shù)組分成3部分，并按照?qǐng)D中標(biāo)示定義邊界位置
- lt<v 右邊界
- i待查看的元素
- gt >v 左邊界
e==v
直接i++
e<v
- arr[i]與arr[lt+1]交換
- lt++
- i++
e>v
- arr[i]與arr[gt+1]交換
- gt--
==注意此時(shí)i是不用變的因?yàn)間t+1的位置也是未排序的，交換后i位置還是待排序元素，所以i不變==
最后排序完成后的樣子
代碼實(shí)現(xiàn)
private static void quickSort(int[] arr, int l, int r) {
if (l >= r)
return;
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
public static int partition(int[] arr, int l, int r) {
int v = arr[l];
//[l+1...i) (j...r]
int i = l + 1, j = r;
while (true) {
while (i <= r && arr[i] < v) {
i++;
}
while (j >= l + 1 && arr[j] > v) {
j--;
}
if (i > j) {
break;
}
Main.swap(arr, j, i);
j--;
i++;
}
Main.swap(arr, l, j);
return j;
}
思考
隨機(jī)數(shù)組第K大的元素
快速排序 經(jīng)過(guò)隨機(jī)選擇，當(dāng)partition后返回P
當(dāng)arr[k]>arr[p] 那么在右側(cè)，否則在左側(cè)，
那么每次查找就減少一半
最終通過(guò)O(n)完成查找
O(n)=n/2+n/4+n/...=2n
