2018年12月23日
归并排序
1，算法思想
递归法（自上而下）
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
迭代法（自下而上）
- 将序列每相邻两个数字进行归并操作，形成
(向上取整)个序列，排序后每个序列包含两/一个元素
- 若此时序列数不是1个则将上述序列再次归并，形成
个序列，每个序列包含四/三个元素
- 重复步骤2，直到所有元素排序完毕，即序列数为1
2，算法图解
3，算法实现
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);
/**
* 因为左右部分各自有序
* 则只需a[mid]>a[mid+1], 才进行排序
*/
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];
}
/**
* 左右两半部分各自有序
* 若左半部分用尽，则直接取右半部分元素
* 若右半部分用尽，则直接去左半部分元素
* 若右半部分当前元素小于左半部分当前元素，则取右半部分元素
* 若右半部分当前元素大于左半部分当前元素，则取左半部分元素
*/
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++];
}
}
}
/**
* 自下向上
* 比较适合用链表组织的数据
*/
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, 是因为当N为奇数时的情况
*/
merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
}
}
}
}
采用自上而下的方法其图解：序列个数为偶数
当序列的个数为奇数时：
采用自下而上的方法其图解：当序列个数为偶数时
当序列个数为奇数时：
4，复杂度分析
-
merge方法在将两个有序数组合并为一个有序数组时，需要借助额外的存储空间，其空间复杂度为。
-
merge方法在合并数组时，不改变相同元素间的前后顺序，因此，归并排序时稳定的。
对N个数归并排序的用时等于完成两个大小为的递归排序所用时间加上合并所用的时间，对于
merge方法，其时间复杂度为时，归并排序所用时间为常数，记为1，那么有：
令，再将两边乘2，那么：
因此可以得到：
同理，令，并在两边乘4，那么：
又可以得到：
总结规律有：
其中
最后有：
因为归并排序的执行效率与待排序数组的有序程度无关，所以其时间复杂度是非常稳定的，因此，无论是最好、最坏还是平均情况下的时间复杂度都为。
快速排序
1，算法思想
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为“基准”（pivot），
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到属于它的位置去。
2，算法图解
3，算法实现
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，复杂度分析
- 最好的情况最多需要
次的嵌套递归调用，所以它需要
-
如图，以3位基准，两个1前后顺序改变了，因此快速排序时不稳定的
快速排序的运行时间等于两个递归调用的运行时间加上partition方法运行时间：
- 最好情况下，基准
pivot正好位于中间，那么，该情况与上面归并排序分析相同，那么快速排序在最好情况下的时间复杂度为
- 最坏情况下，每次选取的基准
pivot为最小元素，此时
将两边相加后得到：
因此，最坏情况下快速排序的时间复杂度为。为了避免这种极端情况，尽量避免基准
pivot为最小元素，可以采用三数取中来选取pivot，即上述medianOfThree方法，该方法取头中尾三个数之间的中位数。 - 平均情况下，选取基准大小概率为
,那么
的平均值为
，那么
那么：
由上面式子可得：
又可以得到：
最终可得：
其中叫做欧拉常数，于是
所以快速排序的平均时间复杂度为
5，应用
LeetCode 215.数组中第K个最大元素
在未排序的数组中找到第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
使用快速排序思想，将K左右两边分区，大的在左边，小的在右边
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;
}
}
第一次分区查找，需要对大小为的数组进行分区，即需要遍历n个元素，平均情况下，在第二次分区查找时，需要对大小为
的数组进行分区，以此类推，分区遍历元素的个数分别为
、
、
……1，我们知道等比数列求和公式：
令，那么：
所以该方法的时间复杂度为。
总结
| 排序算法 | 空间复杂度 | 稳定性 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 |
|---|---|---|---|---|---|
| 归并 | √ | ||||
| 快速 |
|
× |
