时间复杂度为O (nlogn)的排序算法
作者：京东云开发者-京东物流 王奕龙
链接：https://my.oschina.net/u/4090830/blog/10277308
归并排序
划分：分解待排序的 n 个元素的序列成各具 n/2 个元素的两个子序列，将长数组的排序问题转换为短数组的排序问题，当待排序的序列长度为 1 时，递归划分结束
合并：合并两个已排序的子序列得出已排序的最终结果
private void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 划分
int mid = left + right >> 1;
sort(nums, left, mid);
sort(nums, mid + 1, right);
// 合并
merge(nums, left, mid, right);
}
private void merge(int[] nums, int left, int mid, int right) {
// 辅助数组
int[] temp = Arrays.copyOfRange(nums, left, right + 1);
int leftBegin = 0, leftEnd = mid - left;
int rightBegin = leftEnd + 1, rightEnd = right - left;
for (int i = left; i <= right; i++) {
if (leftBegin > leftEnd) {
nums[i] = temp[rightBegin++];
} else if (rightBegin > rightEnd || temp[leftBegin] < temp[rightBegin]) {
nums[i] = temp[leftBegin++];
} else {
nums[i] = temp[rightBegin++];
}
}
}
空间复杂度：借助辅助数组实现合并，使用 O (n) 的额外空间；递归深度为 logn，使用 O (logn) 大小的栈帧空间。忽略低阶部分，所以空间复杂度为 O (n)
非原地排序
稳定排序
非自适应排序
将多次创建小数组的开销转换为只创建一次大数组
private void sort(int[] nums, int left, int right, int[] temp) {
if (left >= right) {
return;
}
// 划分
int mid = left + right >> 1;
sort(nums, left, mid, temp);
sort(nums, mid + 1, right, temp);
// 合并
merge(nums, left, mid, right, temp);
}
private void merge(int[] nums, int left, int mid, int right, int[] temp) {
System.arraycopy(nums, left, temp, left, right - left + 1);
int l = left, r = mid + 1;
for (int i = left; i <= right; i++) {
if (l > mid) {
nums[i] = temp[r++];
} else if (r > right || temp[l] < temp[r]) {
nums[i] = temp[l++];
} else {
nums[i] = temp[r++];
}
}
}
nums[mid] <= nums[mid + 1] 时我们认为数组已经是有序的了，那么我们就跳过 merge () 方法。它不影响排序的递归调用，但是对任意有序的子数组算法的运行时间就变成线性的了，代码实现如下： private void sort(int[] nums, int left, int right, int[] temp) {
if (left >= right) {
return;
}
// 划分
int mid = left + right >> 1;
sort(nums, left, mid, temp);
sort(nums, mid + 1, right, temp);
// 合并
if (nums[mid] > nums[mid + 1]) {
merge(nums, left, mid, right, temp);
}
}
private void merge(int[] nums, int left, int mid, int right, int[] temp) {
System.arraycopy(nums, left, temp, left, right - left + 1);
int l = left, r = mid + 1;
for (int i = left; i <= right; i++) {
if (l > mid) {
nums[i] = temp[r++];
} else if (r > right || temp[l] < temp[r]) {
nums[i] = temp[l++];
} else {
nums[i] = temp[r++];
}
}
}
/**
* M 取值在 5 ~ 15 之间大多数情况下都能令人满意
*/
private final int M = 9;
private void sort(int[] nums, int left, int right) {
if (left + M >= right) {
// 插入排序
insertSort(nums);
return;
}
// 划分
int mid = left + right >> 1;
sort(nums, left, mid);
sort(nums, mid + 1, right);
// 合并
merge(nums, left, mid, right);
}
/**
* 插入排序
*/
private void insertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int base = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j--];
}
nums[j + 1] = base;
}
}
private void merge(int[] nums, int left, int mid, int right) {
// 辅助数组
int[] temp = Arrays.copyOfRange(nums, left, right + 1);
int leftBegin = 0, leftEnd = mid - left;
int rightBegin = leftEnd + 1, rightEnd = right - left;
for (int i = left; i <= right; i++) {
if (leftBegin > leftEnd) {
nums[i] = temp[rightBegin++];
} else if (rightBegin > rightEnd || temp[leftBegin] < temp[rightBegin]) {
nums[i] = temp[leftBegin++];
} else {
nums[i] = temp[rightBegin++];
}
}
}
哨兵划分：选取数组中最左端元素为基准数，将小于基准数的元素放在基准数左边，将大于基准数的元素放在基准数右边
排序子数组：将哨兵划分的索引作为划分左右子数组的分界，分别对左右子数组进行哨兵划分和排序
private void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 哨兵划分
int partition = partition(nums, left, right);
// 分别排序两个子数组
sort(nums, left, partition - 1);
sort(nums, partition + 1, right);
}
/**
* 哨兵划分
*/
private int partition(int[] nums, int left, int right) {
// 以 nums[left] 作为基准数，并记录基准数索引
int originIndex = left;
int base = nums[left];
while (left < right) {
// 从右向左找小于基准数的元素
while (left < right && nums[right] >= base) {
right--;
}
// 从左向右找大于基准数的元素
while (left < right && nums[left] <= base) {
left++;
}
swap(nums, left, right);
}
// 将基准数交换到两子数组的分界线
swap(nums, originIndex, left);
return left;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
时间复杂度：平均时间复杂度为 O (nlogn)，最差时间复杂度为 O (n2)
空间复杂度：最差情况下，递归深度为 n，所以空间复杂度为 O (n)
原地排序
非稳定排序
自适应排序
归并排序的时间复杂度一直是 O (nlogn)，而快速排序在最坏的情况下时间复杂度为 O (n2)，为什么归并排序没有快速排序应用广泛呢？ 答：因为归并排序是非原地排序，在合并阶段需要借助非常量级的额外空间
切换到插入排序
/**
* M 取值在 5 ~ 15 之间大多数情况下都能令人满意
*/
private final int M = 9;
public void sort(int[] nums, int left, int right) {
// 小数组采用插入排序
if (left + M >= right) {
insertSort(nums);
return;
}
int partition = partition(nums, left, right);
sort(nums, left, partition - 1);
sort(nums, partition + 1, right);
}
/**
* 插入排序
*/
private void insertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int base = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j--];
}
nums[j + 1] = base;
}
}
private int partition(int[] nums, int left, int right) {
int originIndex = left;
int base = nums[left];
while (left < right) {
while (left < right && nums[right] >= base) {
right--;
}
while (left < right && nums[left] <= base) {
left++;
}
swap(nums, left, right);
}
swap(nums, left, originIndex);
return left;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
public void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 基准数优化
betterBase(nums, left, right);
int partition = partition(nums, left, right);
sort(nums, left, partition - 1);
sort(nums, partition + 1, right);
}
/**
* 基准数优化，将 left, mid, right 这几个值中的中位数换到 left 的位置
* 注意其中使用了异或运算进行条件判断
*/
private void betterBase(int[] nums, int left, int right) {
int mid = left + right >> 1;
if ((nums[mid] < nums[right]) ^ (nums[mid] < nums[left])) {
swap(nums, left, mid);
} else if ((nums[right] < nums[left]) ^ (nums[right] < nums[mid])) {
swap(nums, left, right);
}
}
private int partition(int[] nums, int left, int right) {
int originIndex = left;
int base = nums[left];
while (left < right) {
while (left < right && nums[right] >= base) {
right--;
}
while (left < right && nums[left] <= base) {
left++;
}
swap(nums, left, right);
}
swap(nums, originIndex, left);
return left;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
public void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 三向切分
int l = left, mid = left + 1, r = right;
int base = nums[l];
while (mid <= r) {
if (nums[mid] < base) {
swap(nums, l++, mid++);
} else if (nums[mid] > base) {
swap(nums, mid, r--);
} else {
mid++;
}
}
sort(nums, left, l - 1);
sort(nums, r + 1, right);
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
这也是经典的荷兰国旗问题，因为这就好像用三种可能的主键值将数组排序一样，这三种主键值对应着荷兰国旗上的三种颜色
巨人的肩膀
《Hello 算法》：11.5 和 11.6 小节 《算法 第四版》：2.3 节 快速排序 《算法导论 第三版》：第 2.2、2.3、7 章
END
马斯克怒：去他妈的广告
这里有最新开源资讯、软件更新、技术干货等内容
微信扫码关注该文公众号作者
戳这里提交新闻线索和高质量文章给我们。
来源: qq
点击查看作者最近其他文章