算法-快速排序和归并排序

1. 快排

2. 归并排序

• 最好情况、最坏情况、平均情况，时间复杂度都为\(O(nlogn)\)
• 空间复杂度为\(O(n)\)。归并排序不是原地排序算法，需要额外的空间来存储tmp数组。

public static void mergeSort(int[] arr){if (arr == null || arr.length<=1)return ;int[] tmp = new int[arr.length];mergeSort(arr, 0, arr.length-1, tmp);
}private static void mergeSort(int[] arr, int left, int right, int[] tmp){if(left >= right) return;int mid = left + (right - left) / 2;    // 防止整数溢出// 分支递归mergeSort(arr, left, mid, tmp);         // 左半部分mergeSort(arr, mid+1, right, tmp);      // 右半部分// 合并两个有序数组merge(arr, left, mid, right, tmp);
}private static void merge(int[] arr, int left, int mid, int right, int[] tmp) {int leftIndex = left;int rightIndex = mid+1;int tmpIndex = left;        // 临时数组索引while(leftIndex<=mid && rightIndex<=right) {if(arr[leftIndex] <= arr[rightIndex]) {tmp[tmpIndex++] = arr[leftIndex++];         } else {tmp[tmpIndex++] = arr[rightIndex++];}}// 将剩余元素拷贝到临时数组中while(leftIndex <= mid) {tmp[tmpIndex++] = arr[leftIndex++]; }while(rightIndex <= right) {tmp[tmpIndex++] = arr[rightIndex++];}// 将临时数组的内容拷贝回原数组for(int i = left; i<=right; ++i) {arr[i] = tmp[i];}
}