文章結(jié)構(gòu)
- 歸并排序
- 快速排序
- 源碼
1. 歸并排序
1.1 什么是歸并排序
歸并排序的思想是：將待排序的區(qū)間平分成兩個(gè)子區(qū)間纳令，先對(duì)兩個(gè)子區(qū)間進(jìn)行排序，然后再將排好序的兩個(gè)子區(qū)間合并成一個(gè)有序序列进栽。而對(duì)子區(qū)間的排序也同樣遵循這個(gè)思想
1.2 動(dòng)畫(huà)演示
1.3 代碼實(shí)現(xiàn)
private static void sort(int[] a, int head, int tail) {
/**
* 遞推公式：sort(a,head,tail)=merge(sort(a,head,m),sort(a,m+1,tail))
* 退出條件：head=tail
*/
if (head == tail) {
return;
}
int mid = (head + tail) / 2;
//對(duì)左右兩個(gè)區(qū)間排序
sort(a, head, mid);
sort(a, mid + 1, tail);
//將排序好的左右兩個(gè)區(qū)間合并起來(lái)
merge(a, head, tail, mid);
}
1.4 歸并排序過(guò)程圖解
1.5 性能分析
時(shí)間復(fù)雜度
使用遞歸樹(shù)來(lái)分析歸并排序的時(shí)間復(fù)雜度漫仆，遞歸樹(shù)的最大深度為log2(n)，每一層的比較次數(shù)為n泪幌，所以遞歸排序的時(shí)間復(fù)雜度在各種情況下都是O(nlogn)盲厌。
空間復(fù)雜度
遞歸排序過(guò)程中需要借助額外的空間來(lái)歸并兩個(gè)有序的序列，這個(gè)空間的最大長(zhǎng)度等于帶排序序列的長(zhǎng)度祸泪，所以空間復(fù)雜度是O(n)
是否穩(wěn)定
歸并排序過(guò)程中不存在元素交換位置的情況吗浩，所以歸并排序是穩(wěn)定排序
2. 快速排序
2.1 什么是快速排序
快速排序的思想是：在要排序的區(qū)間選擇任意的一個(gè)點(diǎn)作為分區(qū)點(diǎn)，遍歷區(qū)間没隘，將小于分區(qū)點(diǎn)的數(shù)據(jù)都排到分區(qū)點(diǎn)的左邊懂扼；將大于分區(qū)點(diǎn)的數(shù)據(jù)都排到分區(qū)點(diǎn)的右邊。這樣經(jīng)過(guò)一輪排序之后分區(qū)點(diǎn)的左邊的數(shù)據(jù)都小于等于它右蒲，分區(qū)點(diǎn)右邊的順序都大于等于它阀湿，分區(qū)點(diǎn)的位置就確定了。然后再以相同的方式對(duì)左右兩個(gè)區(qū)間進(jìn)行排序瑰妄，直到分區(qū)區(qū)間只含有一個(gè)元素位為止陷嘴。
2.2 代碼實(shí)現(xiàn)
private static void sort(int[] a, int left, int right) {
/**
* 遞推公式：sort(a,p,r)=sort(a,p,m-1)+sort(a,m+1,r)
* 結(jié)束條件：head>=tail
*/
if (left < right) {
int low = left;
int hight = right;
int pivot = a[low];
//找到分區(qū)點(diǎn)的位置
while (low < hight) {//有元素之間的位置交換，所以不是穩(wěn)定排序
while (low < hight && a[hight] >= pivot) {
hight--;
}
a[low] = a[hight];
while (low < hight && a[low] <= pivot) {
low++;
}
a[hight] = a[low];
}
a[low] = pivot;
//對(duì)左右兩個(gè)分區(qū)進(jìn)行排序
if (left + 1 < low) {
sort(a, left, low - 1);
}
if (right - 1 > low) {
sort(a, low + 1, right);
}
}
}
2.3 過(guò)程分析
我們來(lái)分析一下一趟快速排序的過(guò)程
- 使用一個(gè)索引low指向待排序區(qū)間的最低位间坐；使用一個(gè)索引hight指向待排序區(qū)間的最高位
- 選擇待排序區(qū)間的最低位作為分區(qū)點(diǎn)pivot
- 從后往前遍歷灾挨，移動(dòng)hight索引，直到找到一個(gè)比分區(qū)點(diǎn)pivot小的值竹宋，將hight指向的值賦值給low指向的位置
- 然后從前往后遍歷劳澄，移動(dòng)low索引，直到找到一個(gè)比分區(qū)點(diǎn)pivot大的值蜈七，將low指向值賦值給hight指向的位置
- 重復(fù)3,4步驟秒拔，直到low=hight，此時(shí)low就是分區(qū)點(diǎn)在序列有序之后的位置
- 將pivot賦值給low飒硅，此時(shí)low前面的數(shù)據(jù)都比pivot小砂缩，low后面的數(shù)據(jù)都比pivot大，接著分別對(duì)low的前后兩個(gè)區(qū)間執(zhí)行這個(gè)排序過(guò)程
2.4 性能分析
時(shí)間復(fù)雜度
- 最好時(shí)間復(fù)雜度：O(nlogn)狡相，當(dāng)每次分區(qū)點(diǎn)都剛好在待排序區(qū)間的正中間時(shí)
- 最壞時(shí)間復(fù)雜度：O(n^2)梯轻，當(dāng)每次分區(qū)都是1,n-1時(shí)，總共要n次分區(qū)
- 平均是否復(fù)雜度：O(nlogn)尽棕，只有在極端情況下才會(huì)出現(xiàn)O(n^2)喳挑，所以它的平均時(shí)間復(fù)雜度還是O(nlogn)
空間復(fù)雜度
這里只使用了幾個(gè)零時(shí)空間來(lái)存儲(chǔ)中間值，所以空間復(fù)雜度是O(1)
是否穩(wěn)定
快排不是穩(wěn)定排序，因?yàn)樵谏厦娴牡?,4步中存在交換元素位置的情況
2.5 快速排序的應(yīng)用
如何在O(n)的時(shí)間復(fù)雜度下從無(wú)序序列中找出第K大的數(shù)
使用快速排序查找第K大的數(shù)的思路：
一趟快排之后伊诵，分區(qū)點(diǎn)左邊的數(shù)據(jù)都小于分區(qū)點(diǎn)单绑，分區(qū)點(diǎn)右邊的數(shù)據(jù)都大于分區(qū)點(diǎn)，也就是分區(qū)點(diǎn)的排序已經(jīng)排好了曹宴。如果此時(shí)分區(qū)點(diǎn)正好是第k大的數(shù)搂橙，則直接返回這個(gè)數(shù)即可。如果分區(qū)點(diǎn)的位置倒數(shù)倒數(shù)第k個(gè)數(shù)之前笛坦，則在右邊序列中繼續(xù)查找区转；如果分區(qū)點(diǎn)的位置在倒數(shù)第k個(gè)數(shù)之后，則在前面的序列中查找版扩。
代碼實(shí)現(xiàn)
/**
* 在O(n)的時(shí)間復(fù)雜度內(nèi)找出無(wú)序數(shù)組中的第K大數(shù)
*
* @param array
* @param k
*/
public static int getMaxK(int[] array, int k) {
if (array == null || array.length < k) {
return Integer.MIN_VALUE;
}
return sort(array, 0, array.length - 1, array.length - k);//計(jì)算第k大數(shù)在序列中的位置：array.length - k
}
private static int sort(int[] a, int left, int right, int index) {
if (left < right) {
int low = left;
int hight = right;
int pivot = a[low];
//找到分區(qū)點(diǎn)的位置
while (low < hight) {
while (low < hight && a[hight] >= pivot) {
hight--;
}
a[low] = a[hight];
while (low < hight && a[low] <= pivot) {
low++;
}
a[hight] = a[low];
}
a[low] = pivot;
if (low == index) {//分區(qū)點(diǎn)的位置就是要查找的第K大數(shù)
return pivot;
} else if (low < index) {//分區(qū)點(diǎn)的位置在要查找的位置的左邊
return sort(a, low + 1, right, index);
} else if (low > index) {//分區(qū)點(diǎn)的位置在要查找的位置的右邊
return sort(a, left, low - 1, index);
}
}
return a[left];
}
測(cè)試用例
@Test
public void testGetMaxKth() {
int size = 10;
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = new Random().nextInt(size * 10);
}
print(array, "org:");
int index = 5;
System.out.println("the " + index + "th:" + QuickSort.getMaxK(array, index));
print(array, "sorted:");
}
private static void print(int[] array, String s) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < array.length; i++) {
builder.append(array[i] + ",");
}
System.out.println(s + builder.toString());
}
輸出結(jié)果
org: 92,71,57,88,46,79,85,48,56,47,
the 5th: 71
sorted: 46,47,56,48,57,71,79,85,88,92,
我們看sorted之后的結(jié)果废离，71確實(shí)是無(wú)序序列的第5大數(shù)，它左邊的都比它小礁芦，它右邊的都比它大
時(shí)間復(fù)雜度分析
我們看一種情況蜻韭，假設(shè)每次分區(qū)都在中間點(diǎn)上，然后我們直到最后一趟快排才找到第K大數(shù)柿扣，這個(gè)時(shí)候的時(shí)間復(fù)雜的是多少呢肖方？我們總共經(jīng)歷了log2(n)趟快排，總共經(jīng)歷的比較次數(shù)是n+n/2+2/4+n/8……+n/n=2*n-1（等比數(shù)列求和）未状，所以時(shí)間復(fù)雜度還是O(n)
3. 源碼
源碼和測(cè)試用例請(qǐng)查看github之排序
說(shuō)明
文中圖片來(lái)源：極客時(shí)間俯画，王爭(zhēng)《數(shù)據(jù)結(jié)構(gòu)與算法之美》
