【排序知多少】归并排序(递归和非递归实现)
2020-01-09 本文已影响0人
齐鑫
归并排序思路
1、将待排序元素一分为二
2、对于左半边和右半边元素分别再次进行拆分,直到无法再拆
3、把拆分过的元素进行重新排序并且合并
4、合并之后最终的数组即为排序之后的数组
归并排序理解
归并排序适用了完全二叉树排序的想法,将带排列数组逐层均分,尽可能分成完全二叉树的形式,再把每组查分的元素从最底层开始,逐层向上的合并起来,直到再次和成一个有序的数组,即完成整个排序过程。
归并排序复杂度
由于归并排序采用了完全二叉树的形式,根据二叉树的复杂度可知,耗费的时间为O(logn),而且一趟归并排序需要将相邻的元素两两进行归并,即所有待排序元素都要扫描一遍,时间复杂度为O(n),所以,归并排序的总时间复杂度为O(nlogn)。
由于归并排序需要将和原数据同样数量级的存储空间存放归并结果,以及递归时深度为logn的站空间,因此,归并排序的空间复杂度为O(n+logn)。
归并排序特点
由于归并排序中需要两两进行比较,不存在跳跃的比较方式,所以归并排序是一种稳定的排序算法。
综上所述,归并排序是一种比较占用内存空间,但是高效且稳定的排序算法。
归并排序JAVA实现
递归实现
public static void main(String[] args) {
int[] arr = {2, 56, 2, 13, 54, 23, 1};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
// p1是左半边指针
int p1 = left;
// p2是右半边指针
int p2 = mid + 1;
// 合并后数组指针
int k = 0;
while (p1 <= mid && p2 <= right) {
if (arr[p1] < arr[p2]) {
temp[k++] = arr[p1++];
} else {
temp[k++] = arr[p2++];
}
}
while (p1 <= mid) {
temp[k++] = arr[p1++];
}
while (p2 <= right) {
temp[k++] = arr[p2++];
}
for (int i = 0; i < temp.length; i++) {
arr[left + i] = temp[i];
}
}
private static void mergeSort(int[] arr, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
}
非递归实现
public class Main {
public static void main(String[] args) {
int[] arr = {2, 56, 2, 13, 54, 23, 1};
mergeSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void mergeSort(int[] arr) {
// 使用非递归方式实现归并排序
int len = arr.length;
int k = 1;
while (k < len) {
mergePass(arr, k, len);
k *= 2;
}
}
private static void mergePass(int[] arr, int k, int n) {
int i = 0;
// 从前往后走,将2个长度为k的子序列合并为1个
while (i < n - 2 * k + 1) {
merge(arr, i, i + k - 1, i + 2 * k - 1);
i += 2 * k;
}
// 这段代码保证了,讲那些落单的长度不足两两merge的部分和前面merge起来
if (i < n - k) {
merge(arr, i, i + k - 1, n - 1);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
// p1是左半边指针
int p1 = left;
// p2是右半边指针
int p2 = mid + 1;
// 合并后数组指针
int k = 0;
while (p1 <= mid && p2 <= right) {
if (arr[p1] < arr[p2]) {
temp[k++] = arr[p1++];
} else {
temp[k++] = arr[p2++];
}
}
while (p1 <= mid) {
temp[k++] = arr[p1++];
}
while (p2 <= right) {
temp[k++] = arr[p2++];
}
for (int i = 0; i < temp.length; i++) {
arr[left + i] = temp[i];
}
}
}