2018年12月23日
歸并排序
1会涎，算法思想
遞歸法（自上而下）
- 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和瑞凑，該空間用來存放合并后的序列
- 設(shè)定兩個(gè)指針末秃，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
- 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間籽御，并移動(dòng)指針到下一位置
- 重復(fù)步驟3直到某一指針到達(dá)序列尾
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
迭代法（自下而上）
- 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作练慕，形成
(向上取整)個(gè)序列，排序后每個(gè)序列包含兩/一個(gè)元素
- 若此時(shí)序列數(shù)不是1個(gè)則將上述序列再次歸并技掏，形成
個(gè)序列铃将，每個(gè)序列包含四/三個(gè)元素
- 重復(fù)步驟2，直到所有元素排序完畢哑梳，即序列數(shù)為1
2劲阎，算法圖解
3，算法實(shí)現(xiàn)
public class Merge<AnyType extends Comparable<? super AnyType>> {
private AnyType[] aux;
/**
* 自上向下
*/
public void sort(AnyType[] a) {
aux = (AnyType[]) new Comparable[a.length];
sort(a, 0, a.length - 1);
}
public void sort(AnyType[] a, int lo, int hi) {
if (lo >= hi) {
return;
}
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid);
sort(a, mid + 1, hi);
/**
* 因?yàn)樽笥也糠指髯杂行? * 則只需a[mid]>a[mid+1], 才進(jìn)行排序
*/
if (a[mid].compareTo(a[mid + 1]) > 0) {
merge(a, lo, mid, hi);
}
}
public void merge(AnyType[] a, int lo, int mid, int hi) {
/**
* i從左半部分開始
* j從右半部分開始
*/
int i = lo;
int j = mid + 1;
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
/**
* 左右兩半部分各自有序
* 若左半部分用盡涧衙，則直接取右半部分元素
* 若右半部分用盡哪工，則直接去左半部分元素
* 若右半部分當(dāng)前元素小于左半部分當(dāng)前元素奥此，則取右半部分元素
* 若右半部分當(dāng)前元素大于左半部分當(dāng)前元素弧哎，則取左半部分元素
*/
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (aux[j].compareTo(aux[i]) < 0) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
/**
* 自下向上
* 比較適合用鏈表組織的數(shù)據(jù)
*/
public void sortBU(AnyType[] a) {
int N = a.length;
aux = (AnyType[]) new Comparable[a.length];
for (int sz = 1; sz < N; sz *= 2) {
for (int lo = 0; lo < N - sz; lo += 2 * sz) {
/**
* mid=lo+((lo+sz+sz-1)-lo)/2=lo+(sz+sz-1)/2=lo+sz-1
* 之所以使用Math.min, 是因?yàn)楫?dāng)N為奇數(shù)時(shí)的情況
*/
merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
}
}
}
}
采用自上而下的方法其圖解：序列個(gè)數(shù)為偶數(shù)
當(dāng)序列的個(gè)數(shù)為奇數(shù)時(shí)：
采用自下而上的方法其圖解：當(dāng)序列個(gè)數(shù)為偶數(shù)時(shí)
當(dāng)序列個(gè)數(shù)為奇數(shù)時(shí)：
4，復(fù)雜度分析
-
merge方法在將兩個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組時(shí)稚虎，需要借助額外的存儲(chǔ)空間撤嫩，其空間復(fù)雜度為。
-
merge方法在合并數(shù)組時(shí)蠢终，不改變相同元素間的前后順序序攘，因此，歸并排序時(shí)穩(wěn)定的寻拂。
對(duì)N個(gè)數(shù)歸并排序的用時(shí)等于完成兩個(gè)大小為的遞歸排序所用時(shí)間加上合并所用的時(shí)間程奠，對(duì)于
merge方法，其時(shí)間復(fù)雜度為時(shí)瞄沙，歸并排序所用時(shí)間為常數(shù)，記為1慌核，那么有：
令距境，再將兩邊乘2，那么：
因此可以得到：
同理垮卓，令垫桂，并在兩邊乘4，那么：
又可以得到：
總結(jié)規(guī)律有：
其中
最后有：
因?yàn)闅w并排序的執(zhí)行效率與待排序數(shù)組的有序程度無關(guān)粟按，所以其時(shí)間復(fù)雜度是非常穩(wěn)定的诬滩，因此霹粥，無論是最好、最壞還是平均情況下的時(shí)間復(fù)雜度都為疼鸟。
快速排序
1蒙挑，算法思想
快速排序使用分治法（Divide and conquer）策略來把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。
步驟為：
- 從數(shù)列中挑出一個(gè)元素愚臀，稱為“基準(zhǔn)”（pivot）忆蚀，
- 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面姑裂，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）馋袜。在這個(gè)分割結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置舶斧。這個(gè)稱為分割（partition）操作欣鳖。
- 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸到最底部時(shí)茴厉，數(shù)列的大小是零或一泽台，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束矾缓，因?yàn)樵诿看蔚牡╥teration）中怀酷，它至少會(huì)把一個(gè)元素?cái)[到屬于它的位置去。
2嗜闻，算法圖解
3蜕依，算法實(shí)現(xiàn)
public class Quick<AnyType extends Comparable<? super AnyType>> {
public void sort(AnyType[] a) {
sort(a, 0, a.length - 1);
}
private void sort(AnyType[] a, int lo, int hi) {
if (lo >= hi) {
return;
}
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
private int partition(AnyType[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
AnyType pivot = a[lo];
int size = hi - lo + 1;
if (size >= 3) {
pivot = medianOfThree(a, lo, hi);
}
while (true) {
while (a[++i].compareTo(pivot) < 0) {
if (i == hi) {
break;
}
}
while (pivot.compareTo(a[--j]) < 0) {
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, lo, j);
return j;
}
private AnyType medianOfThree(AnyType[] a, int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[lo].compareTo(a[hi]) > 0) {
swap(a, lo, hi);
}
if (a[mid].compareTo(a[hi]) > 0) {
swap(a, mid, hi);
}
if (a[mid].compareTo(a[lo]) > 0) {
swap(a, mid, lo);
}
return a[lo];
}
private void swap(AnyType[] a, int i, int j) {
AnyType temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
4，復(fù)雜度分析
- 最好的情況最多需要
次的嵌套遞歸調(diào)用琉雳，所以它需要
-
如圖檐束，以3位基準(zhǔn)，兩個(gè)1前后順序改變了束倍，因此快速排序時(shí)不穩(wěn)定的
快速排序的運(yùn)行時(shí)間等于兩個(gè)遞歸調(diào)用的運(yùn)行時(shí)間加上partition方法運(yùn)行時(shí)間：
- 最好情況下被丧，基準(zhǔn)
pivot正好位于中間，那么肌幽，該情況與上面歸并排序分析相同晚碾，那么快速排序在最好情況下的時(shí)間復(fù)雜度為
- 最壞情況下喂急，每次選取的基準(zhǔn)
pivot為最小元素格嘁，此時(shí)
將兩邊相加后得到：
因此，最壞情況下快速排序的時(shí)間復(fù)雜度為廊移。為了避免這種極端情況糕簿，盡量避免基準(zhǔn)
pivot為最小元素探入，可以采用三數(shù)取中來選取pivot，即上述medianOfThree方法懂诗，該方法取頭中尾三個(gè)數(shù)之間的中位數(shù)蜂嗽。 - 平均情況下，選取基準(zhǔn)大小概率為
,那么
的平均值為
殃恒，那么
那么：
由上面式子可得：
又可以得到：
最終可得：
其中叫做歐拉常數(shù)植旧，于是
所以快速排序的平均時(shí)間復(fù)雜度為
5离唐，應(yīng)用
LeetCode 215.數(shù)組中第K個(gè)最大元素
在未排序的數(shù)組中找到第 k 個(gè)最大的元素病附。
請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素亥鬓，而不是第 k 個(gè)不同的元素完沪。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
使用快速排序思想，將K左右兩邊分區(qū)嵌戈，大的在左邊覆积，小的在右邊
public class FindKthLargest {
public static int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return Integer.MAX_VALUE;
}
return findKthLargest(nums, 0, nums.length - 1, k-1);
}
private static int findKthLargest(int[] nums, int start, int end, int k) {
if (start > end) {
return Integer.MAX_VALUE;
}
int pivot = nums[end];
int left = start;
for (int i = start; i < end; i++) {
if (nums[i] > pivot) {
swap(nums, left++, i);
}
}
swap(nums, left, end);
if (left == k) {
return nums[left];
} else if (left < k) {
return findKthLargest(nums, left + 1, end, k);
} else {
return findKthLargest(nums, start, left - 1, k);
}
}
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
第一次分區(qū)查找，需要對(duì)大小為的數(shù)組進(jìn)行分區(qū)熟呛，即需要遍歷n個(gè)元素宽档，平均情況下，在第二次分區(qū)查找時(shí)惰拱，需要對(duì)大小為
的數(shù)組進(jìn)行分區(qū)雌贱，以此類推，分區(qū)遍歷元素的個(gè)數(shù)分別為
偿短、
、
……1馋没，我們知道等比數(shù)列求和公式：
令昔逗，那么：
所以該方法的時(shí)間復(fù)雜度為。
總結(jié)
| 排序算法 | 空間復(fù)雜度 | 穩(wěn)定性 | 最好時(shí)間復(fù)雜度 | 最壞時(shí)間復(fù)雜度 | 平均時(shí)間復(fù)雜度 |
|---|---|---|---|---|---|
| 歸并 | √ | ||||
| 快速 |
|
× |
