09.排序：快排和归并排序
2020-05-24 本文已影响0人
学海一乌鸦
1.归并排序
image.png
大体思路 归并排序核心思想：分治思想(大问题化分为小问题去解决，小的问题解决了，大问题自然也能解决掉)
其中分治是一种解决问题的思想，而递归是一种编程技巧；
递归二要素：
递推公式：merge_sort(p,r)=merge(merge_sort(p,q),merge_sort(q+1,r));其中q=(p+q)/2
截止条件:p>=r,结束递归
中间的merge函数：申请一个新的数组，对两个子数组分别进行比较，按照从小到大的顺序排列好
临界条件：
写代码时一定要小心，费了半天劲终于分析清楚了，不要在细节上被绊倒
public class MergeSort {
public static void mergeSort(int[] arr) {
// 非空校验
if (arr == null || arr.length <= 0) {
return ;
}
merge_sort(0,arr.length-1,arr);
}
/**
*
* @param p 元素开始的位置
* @param r 元素结束的位置
* @param arr 待合并的数组
*/
private static void merge_sort(int p,int r,int []arr){
if(p>=r){
return ;
}
//防止越界
int q=p+(r-p)/2;
merge_sort(p,q,arr);
merge_sort(q+1, r, arr);
mergeArrBySentry(p,q,r,arr);
}
/**
*
* @param arr1
* @param arr2
* @return
*/
private static void mergeArr(int p, int q, int r, int[] arr) {
// 申请一个新数组
int[] merge = new int[r - p + 1];
// 初始化 ijk
int i = p;
int j = q + 1;
int k = 0;
while (i <= q && j <= r) {
// 这里的等号很重要，保证元素排序的稳定性
if (arr[i] <= arr[j]) {
merge[k++] = arr[i++];
} else {
merge[k++] = arr[j++];
}
}
// 判断哪个子数组子数组中有剩余元素
if (i > q) {
while (j <= r) {
merge[k++] = arr[j++];
}
}
if (j > r) {
while (i <= q) {
merge[k++] = arr[i++];
}
}
// 将tmp中的数组拷贝回a[p...r]
for (i = 0; i <= r - p; ++i) {
arr[p + i] = merge[i];
}
}
/**
*
* @param p
* @param q
* @param r
* @param arr
*/
private static void mergeArrBySentry(int p, int q, int r, int[] arr) {
// 比原定的数组大一个，用来储存哨兵
int[] leftArr = new int[q - p + 2];
int[] rightArr = new int[r - q + 1];
// 给新数组赋值
for (int i = 0; i < q - p + 1; i++) {
leftArr[i] = arr[i + p];
}
leftArr[q - p + 1] = Integer.MAX_VALUE;
// 给新数组赋值
for (int i = 0; i < r - q; i++) {
rightArr[i] = arr[i + q + 1];
}
rightArr[r - q] = Integer.MAX_VALUE;
int k = p;
int i = 0;
int j = 0;
while (k <= r) {
// 当左边数组到达哨兵值时，i不再增加，直到右边数组读取完剩余值，同理右边数组也一样
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
}
public static void main(String[] args) {
MergeSort mergeSort=new MergeSort();
int []arr={8,7,6,5,4,3,3,2};
mergeSort.mergeSort(arr);
ArrUtils.printAll(arr);
}
}
归并排序的复杂度分析
1.是否是稳定的排序算法？
这个主要取决于mergeArr的实现，对于两个待合并的数组，如果相同，先选择左边的数组，那么就是稳定的排序算法。
2.时间复杂度？
归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。
3.空间复杂度？
空间复杂度是 O(n)。
递归代码的空间复杂度并不能像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小。
2.快排
大体思路：采用自上而下的分治思想 ，如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。然后将数据分为小于分区点的数据和大于分区点的数据。
- 递归二要素
quick_sort(arr,s,e)=quick_sort(arr,s,q)+quick_sort(arr,q+1,e);
if(s>=e) return； - 分区方法
选择最后一个元素作为target -
分区过程
image.png
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 0) {
return;
}
quick_sort(arr, 0, arr.length - 1);
}
/**
* 进行快排
*
* @param arr
* @param start
* @param end
*/
private static void quick_sort(int[] arr, int start, int end) {
// 递归终止条件
if (start >= end) {
return;
}
int q = partition(arr, start, end);
quick_sort(arr, start, q-1);
quick_sort(arr, q + 1, end);
}
/**
* 对数组arr从[start,end]进行排序，并返回临界点
*
* @param arr
* @param start
* @param end
* @return
*/
private static int partition(int[] arr, int start, int end) {
// 默认选择最后一个元素
int target = arr[end];
// 变量i用来遍历每一个元素；变量j是大于target和小于target的临界点,在此之前的值都是小于target
int j = start;
int i = start;
for (; i < end; i++) {
//如果小于target，需要移动到j前面
if (arr[i] < target) {
if(i!=j){
swap(arr, i, j);
}
j++;
}
}
// 最后把target元素放在中间
swap(arr, end, j);
return j;
}
private static void swap(int[] arr, int m, int n) {
int tmp = arr[m];
arr[m] = arr[n];
arr[n] = tmp;
}
public static void main(String[] args) {
int []arr={1,2,4,8,6,5,7};
quickSort(arr);
ArrUtils.printAll(arr);
}
}
2.2与归并排序的区别与联系
image.png
归并排序：自下而上。先递归在比较；
快速排序：自上而下。先 比较再递归；
归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法
2.3 性能分析
- 原地排序算法？
是的，不需要额外的空间 - 稳定排序？
不是 - 时间复杂度
T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n2)。
一个比较极端的例子。如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。
3.排序优化
插入排序:
- 原地排序
- 稳定排序
- 时间复杂度:对于已经排好序的序列，O(n),常规情况O(n2)
快速排序 - 原地排序
- 不稳定的排序
- 时间复杂度:平均O(logn),极端情况O(n2)
优化：
小于一定规模的数，采用插入排序；
对于快速排序，每次随机选取一个数字作为分区点
public class TheBestSort {
private static int DEFAULT_LENGTH = 10;
public static void theBestSort(int[] arr) {
if (arr == null || arr.length <= 0) {
return;
}
// 插入排序
if (arr.length <= DEFAULT_LENGTH) {
InsertSort(arr);
return;
}
// 否则使用快排
quickSort(arr, 0, arr.length - 1);
}
// 快速排序
private static void quickSort(int[] arr, int l, int r) {
// 递归的终止条件
if (r - l <= DEFAULT_LENGTH) {
InsertSort(arr);
return;
}
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
// 分区方法
private static int partition(int[] arr, int l, int r) {
// 随机取数法
int m = (int) ((Math.random() * (r - l + 1)) + l);
swap(arr, m, r);
int target = arr[r];
// 计数器
int i = l;
// 分界区[0,j-1] <target [j,r] >=target
int j = l;
// 最后的r不用比较
for (; i < r; i++) {
if (arr[i] < target) {
// 简单优化一，当i=j的时候，不用交换了
if (i != j) {
swap(arr, i, j);
}
j++;
}
}
swap(arr, r, j);
return j;
}
// 插入排序
private static void InsertSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int val = arr[i];
int j = i - 1;
for (; j >= 0; j--) {
// 不加==。保证稳定排序
if (arr[j] > val) {
swap(arr, j, j + 1);
} else {
// 一个不满足，结束循环
break;
}
}
arr[j + 1] = val;
}
}
// 交换
private static void swap(int[] arr, int n, int m) {
int tmp = arr[m];
arr[m] = arr[n];
arr[n] = tmp;
}
public static void main(String[] args) {
int arr[] = { 5, 6, 4, 3, 6, 2, 6, 2, 6, 7, 5, 8, 4, 33, 22, 66, 788, 33, 22 };
theBestSort(arr);
ArrUtils.printAll(arr);
}
}
