归并排序
程序员文章站
2022-06-04 17:14:37
...
归并排序思想:
一个数组,先将其左部分排好序,再将其右部分排好序,然后用我之前的外排方法,将左部分第一个数设为p1,将右部分第一个数设为p2,如果谁小就将其放到辅助的数组中然后指针向右移一位,最后考虑数组越界问题,如果p1先越界,则将右半部分的数组(没放入辅助数组中的数)全部放入辅助数组中。则整个数组全部排好序。
思想:
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int mid, int r) {
int i = 0;
int[] help = new int[r - l + 1];
int p1 = l;
int p2 = mid + 1;
while (p1 <= mid && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[l + j] = help[j];
}
}
全部代码:
package basic_class_01;
public class Code_05_mergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int mid, int r) {
int i = 0;
int[] help = new int[r - l + 1];
int p1 = l;
int p2 = mid + 1;
while (p1 <= mid && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[l + j] = help[j];
}
}
public static void main(String[] args) {
int[] arr = { 3, 2, 1, 6, 5, 4 };
mergeSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
代码讲解:
时间复杂度分析:
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid); //T(N/2)
mergeSort(arr, mid + 1, r); //T(N/2)
merge(arr, l, mid, r); //O(N)
//T(N) = 2*T(N/2)+O(N);
}
结论:所以在冒泡排序,选择排序,插入排序和归并排序中,归并排序的时间复杂度是最小的
上一篇: 【S-排序】python实现八大排序算法之7-归并排序
下一篇: 归并排序