2023/11/27 09:47

# 归并排序

• 划分：分解待排序的 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++];
}
}
}



### 当数组有序时，跳过 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)

• 原地排序

• 非稳定排序

• 自适应排序

### 切换到插入排序

    /**
* 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;
}



0 评论
10 收藏
1