1、排序算法概述
常用的内部排序方法有:交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、堆排序)、插入排序(直接插入排序、希尔排序)、归并排序、基数排序(一关键字、多关键字)。
- 所需辅助空间最多:归并排序
- 所需辅助空间最少:堆排序
- 平均速度最快:快速排序
- 不稳定:快速排序,希尔排序,堆排序。
选择排序算法的依据:任何排序算法在数据量小的时候基本体现不出来差距。选择依据有:
- 1.数据的规模 :当数据规模较小时,选择直接插入排序或冒泡排序。
- 2.数据的类型 :如全部是正整数,那么考虑使用桶排序为最优。
- 3.数据已有的顺序 :快排是一种不稳定的排序(当然可以改进),对于大部分排好的数据,快排会浪费大量不必要的步骤。
数据量极小,而且已经基本排好序,冒泡是最佳选择。我们说快排好,是指大量随机数据下,快排效果最理想。而不是所有情况。
2、归并排序时空复杂度
最好最差时间复杂度均为O(nlogn),平均时间复杂度O(nlogn),空间复杂度O(n),是一种稳定的排序算法。
时间复杂度:对长度为n的文件,需进行趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlogn)。
空间复杂度:需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。
3、归并排序原理
归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序,也可以用于外排序。
- 归并排序是一种概念上最简单的排序算法,与快速排序一样,归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列,为每一个子序列排序,然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。
4、归并排序思路
分而治之(divide - conquer);每个递归过程涉及三个步骤:
- 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素。
- 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。
- 第三, 合并: 合并两个排好序的子序列,生成排序结果。
动图展示:
5、归并排序举例说明
1.归并排序的流程:
2.合并两个有序数组的流程
6、归并排序代码
public class MergeSort {
// 两路归并算法,两个排好序的子序列合并为一个子序列
public static void merge(int[] a, int low, int mid, int high) {
int[] tmp = new int[a.length];// 辅助数组
// int[] tmp = new int[high-low+1];
int p1 = low, p2 = mid + 1, k = low;// p1、p2是检测指针,k是存放指针
// 把较小的数先移到新数组中
while (p1 <= mid && p2 <= high) {
tmp[k++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
}
// 上面的循环退出后,把剩余的元素依次填入到temp中
// 以下两个while只有一个会执行
// 把左边剩余的数移入数组
while (p1 <= mid) {
tmp[k++] = a[p1++];// 如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
}
// 把右边边剩余的数移入数组
while (p2 <= high) {
tmp[k++] = a[p2++];// 同上
}
// 复制回原数组 // 把新数组中的数覆盖nums数组
for (int i = low; i <= high; i++) {
a[i] = tmp[i];
}
}
public static void mergeSort(int[] a, int start, int end) {
if (start < end) {// 当子序列中只有一个元素时结束递归
// int mid = (start + end) / 2;// 划分子序列
int mid = start + ((end - start) >> 1);
// System.out.println(start+"-"+mid+"-"+end);
mergeSort(a, start, mid);// 对左侧子序列进行递归排序
mergeSort(a, mid + 1, end);// 对右侧子序列进行递归排序
merge(a, start, mid, end);// 左右归并
}
}
public static void main(String[] args) {
int[] arr = { 6, 3, 8, 2, 9, 1,7,4 };
System.out.print("排序前的数组为:");
for (int num : arr) {
System.out.print(num + " ");
}
mergeSort(arr, 0, arr.length-1);
System.out.println();
System.out.print("排序后的数组为:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
// 排序前的数组为:6 3 8 2 9 1 7 4
// 排序后的数组为:1 2 3 4 6 7 8 9
评论区