1、常见排序算法，及其时间复杂度
5、归并排序
归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
递归方式：
非递归方式：arr[{L,M},{,R},...]
注意：步长相关计算的处理，不够左右组的情况，避免越界
- 根据步长 step 的值，顺序选取左右两段子数组进行合并
- 当左组的开始 L 越界时，说明剩余的数不能组成[{左},{右},...]
- 合并时，准备两个指针 p1，p2分别指向左组、右组的开始，比较谁小 copy 谁
- 当 p1 或 p2越界时，将未越界的数组剩下数顺序 copy 到临时数组中，p1,p2不可能同时越界。
- 将临时数组copy回原数组的对应位置：temp[0，R1] -> arr[L...R]
5.3、代码实现
点击查看代码
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
/**
* arr[L...R] 范围上，请让这个范围上的数，有序！
* 递归
* @param arr 待排序数组
* @param L 数组左下标
* @param R 数组右下标
*/
public static void process(int[] arr, int L, int R) {
if (L == R) {
return;
}
// 计算中点
int mid = L + ((R - L) >> 1);
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
/**
* 归并排序，合并
*
* @param mid 数组中点下标
*/
public static void merge(int[] arr, int L, int mid, int R) {
int[] temp = new int[R - L + 1];
int index = 0;
int p1 = L;
int p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
temp[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
// 要么p1 越界，要么p2 越界，不可能同时越界
while (p1 <= mid) {
temp[index++] = arr[p1++];
}
while (p2 <= R) {
temp[index++] = arr[p2++];
}
// copy 回原数组
for (int i = 0; i < temp.length; i++) {
arr[L + i] = temp[i];
}
// System.arraycopy(temp, 0, arr, L, temp.length);
}
/**
* 归并排序，非递归方式
* step: 为步长，从1开始，分为 {左,右}
* L：左的开始
* M：左的结束
* M + 1：右的开始
* R：右的结束
* @param arr 待排序数组
*/
public static void mergeSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
// 步长
int step = 1;
while (step < N) {
int L = 0;
while (L < N) {
if (step >= N - L) {
break;
}
int mid = L + step - 1;
int R = mid + Math.min(step, N - mid - 1);
merge(arr, L, mid, R);
L = R + 1;
}
if (step > (N >> 1)) {
break;
}
step <<= 1;
}
}
// 写对数器，随机进行测试
public static void main(String[] args) {
int testTimes = 50000;
int maxSize = 100_00;
int maxValue = 2000;
long start, end;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
int[] arr = CustomCollectionUtils.generateRandomArray(maxSize, maxValue);
int[] arr2 = CustomCollectionUtils.copyArray(arr);
mergeSort(arr);
QuickSort.quickSort(arr2, 0, arr2.length - 1);
if (!Arrays.equals(arr, arr2)) {
System.out.println("出错了！");
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(arr2));
break;
}
}
System.out.println("nice");
}
}
6、快速排序
数组arr[0...R]，以arr[R]为基数，进行数据调整
6.1、分割并调整数组方式一
调整：小于等于arr[R] 的放左边，大于arr[R]的放右边
示例：
public static void splitNum(int[] arr) {
// <= 区的右边界
int lessEqualR = -1;
int index = 0;
int mostR = arr.length - 1;
while (index <= mostR) {
if (arr[index] <= arr[mostR]) {
swap(arr, ++lessEqualR, index++);
} else {
index++;
}
}
}
输出：[4, 2, 6, 3, 5, 6, 7, 9]
6.2、分割并调整数组方式二
调整：小于arr[R] 的放左边，等于arr[R]的放中间，大于arr[R]的放右边
示例：
public static void splitNum(int[] arr) {
int N = arr.length;
int lessR = -1;
int moreL = N - 1;
int index = 0;
while (index < moreL) {
if (arr[index] < arr[N - 1]) {
swap(arr, ++lessR, index++);
} else if (arr[index] > arr[N - 1]) {
swap(arr, --moreL, index);
} else {
index++;
}
}
// index 与大于区域左边界相遇时，即表示，此时只有数组最后一个数未调整
swap(arr, moreL, N - 1);
}
输出：[4, 2, 5, 3, 6, 6, 7, 9]
6.3、给定数组的任意范围arr[..L...R..]，来做分区调整
- 给定一个数组arr[0...N]
- 给定一个区间[L,R] 属于 arr
- 在给定区间[L,R] 范围上做调整
- 以arr[R]为基数，将arr[..L...R..]调整为
- 返回等于指定基数区间，的左右下标res[EL,ER]
/**
* arr[..L...R..] 范围上，以arr[R] 为基数，做划分
*
* @param arr
* @param L 开始位置
* @param R 结束位置
* @return 等于arr[R]区域的左右下标，只有两个值 res[L,R]
*/
public static int[] partition(int[] arr, int L, int R) {
// 小于区域右边界，大于区域左边界
int lessR = L - 1;
int moreL = R;
int index = L;
while (index < moreL) {
if (arr[index] < arr[R]) {
swap(arr, ++lessR, index++);
} else if (arr[index] > arr[R]) {
swap(arr, index, --moreL);
} else {
index++;
}
}
swap(arr, moreL, R);
return new int[]{lessR + 1, moreL};
}
示例：
int[] arr = {4, 2, 7, 6, 3, 9, 5, 6};
partition(arr, 1, 4);
输出 [4, 2, 3, 7, 6, 9, 5, 6]
6.4、快速排序（递归）
代码实现
点击查看代码
public class PartitionAndQuickSort {
/**
* 快速排序(递归)，升序
*
* @param arr 待排序数组
*/
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
/**
* 数组arr[L,R] 范围上排序，升序
*
* @param arr 待排序数组
* @param left 左下标
* @param right 右下标
*/
public static void process(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int[] equalLR = partition(arr, left, right);
process(arr, left, equalLR[0] - 1);
process(arr, equalLR[1] + 1, right);
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
6.5、快速排序（非递归）
- 新建一个任务类Job,保存数组 arr[..L..R..] 待分割数组的左右下标
- 使用栈来保存待排序的数组的 Job，顺序执行当前Job，排序
- 如果当前Job 有左/右则继续分割成新的任务，压到栈中
Stack<Job> stack = new Stack<>();
代码实现
点击查看代码
public class PartitionAndQuickSort {
/**
* 保存数组 arr[..L..R..] 范围上，待分割数组的左右下标
*/
public static class Job {
public int L;
public int R;
public Job(int left, int right) {
this.L = left;
this.R = right;
}
}
/**
* 快速排序(非递归)，升序
*
* @param arr 待排序数组
*/
public static void quickSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
Stack<Job> stack = new Stack<>();
stack.push(new Job(0, arr.length - 1));
while (!stack.isEmpty()) {
Job cur = stack.pop();
int[] equalLR = partition(arr, cur.L, cur.R);
// 有小于区域
if (equalLR[0] > cur.L) {
stack.push(new Job(cur.L, equalLR[0] - 1));
}
if (equalLR[1] < cur.R) {
stack.push(new Job(equalLR[1] + 1, cur.R));
}
}
}
// 对数器随机，大批量测试
public static void main(String[] args) {
int[] arr0 = {4, 2, 7, 6, 3, 9, 5, 6};
int testTimes = 50000;
int maxSize = 100;
int maxValue = 2000;
long start, end;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
int[] arr = CustomCollectionUtils.generateRandomArray(maxSize, maxValue);
int[] arr2 = CustomCollectionUtils.copyArray(arr);
// quickSort(arr);
QuickSort.quickSort(arr, 0, arr.length - 1);
quickSort2(arr2);
if (!Arrays.equals(arr, arr2)) {
System.out.println("出错了！");
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(arr2));
break;
}
}
System.out.println("nice!");
}
}