详解快排+归并排序+堆排序 附源码
- 没发博客的日子，也在好好学习，这段时间，每天花四到五小时写算法，除了图论和dp都有了不少的认知，后面会减少算法的时间，主要就是复习之前刷分+刷完图论+并不断学习dp。
- 这篇文章，是因为在复习链表题的时候发现排序题不会写，重新复习了几个较难的排序。
三、排序
3.1快速排序总结 (升序排序)
-
选择基准元素：
- 在快速排序中，选择一个基准元素（pivot）。常见的做法是选取最右边的元素（
nums[right]）作为基准。
- 在快速排序中，选择一个基准元素（pivot）。常见的做法是选取最右边的元素（
-
分区过程：
- 快速排序通过 分区 操作将数组分为两部分：一部分包含所有小于基准元素的值，另一部分包含所有大于基准元素的值。
- 在此过程中，两个指针 l和r会在数组的两端移动：
l从左边开始，寻找第一个大于基准元素的元素。r从右边开始，寻找第一个小于基准元素的元素。
- 如果
l小于r，则交换这两个元素，直到l和r相遇。
-
基准元素交换：
- 在
l和r相遇后，基准元素会交换到l或r的位置，确保基准元素左边的元素都小于基准元素，右边的元素都大于基准元素。 - 此时，返回基准元素的位置
l（或者r，它们此时相同），将其放置在正确的排序位置。
- 在
-
递归排序：
- 基准元素确定位置后，递归地对左右两部分进行排序。
- 代码：
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
private int partition(int[] nums, int left, int right) {
// 选择基准元素，通常选择最右边的元素
int pivot = nums[right];
int l = left; // l 指向左边部分的开始
int r = right - 1; // r 指向右边部分的开始
while (l <= r) {
// 寻找一个小于基准元素的元素
while (l <= r && nums[l] < pivot) {
l++;
}
// 寻找一个大于基准元素的元素
while (l <= r && nums[r] >= pivot) {
r--;
}
if (l < r) {
swap(nums, l, r); // 交换 l 和 r 的元素
}
}
// 将基准元素放到正确位置
swap(nums, right, l); // 基准元素放置到 l 位置
return l; // 返回基准元素的位置
}
public void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int pivot = partition(nums, left, right); // 获取基准元素的最终位置
quickSort(nums, left, pivot - 1); // 排序左半部分
quickSort(nums, pivot + 1, right); // 排序右半部分
}
}
- 基准和谁交换，看的是，哪个指针指向的大小和基准原来位置的关系。例如选择升序排，左基准，那么就是基准和右指针换，因为右指针指向的是比基准小的数。例如升序，右基准，那么就是左指针和基准换，因为指针指向的是比基准大的数。
3.2基准优化
-
选择左中间右三个节点，选择中位数为基准，能大程度少优化时间复杂度
class Solution { public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } public void quickSort(int[] nums, int left, int right) { if (left >= right) { return; } int pivot = partition(nums, left, right); quickSort(nums, left, pivot - 1); quickSort(nums, pivot + 1, right); } public int medianThree(int[] nums, int left, int mid, int right) { int l = nums[left]; int m = nums[mid]; int r = nums[right]; if ((l <= m && m <= r) || (r <= m && m <= l)) { return mid; } else if ((m <= l && l <= r) || (r <= l && l <= m)) { return left; } return right; } public void swap(int[] nums, int left, int right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } public int partition(int[] nums, int left, int right) { int pivotIndex = medianThree(nums, left, (left + right) / 2, right); swap(nums, pivotIndex, left); int pivot = nums[left]; int l = left + 1; int r = right; while (l <= r) { while (l <= r && nums[l] <= pivot) { l++; } while (l <= r && nums[r] >= pivot) { r--; } if (l < r) { swap(nums, r, l); } } swap(nums, r, left); return r; } }
3.3尾递归优化
-
当按顺序排列，时间复杂度和空间复杂度最高，为了防止栈溢出，先对数组元素较小的子数组进行排序
class Solution { public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } public void quickSort(int[] nums, int left, int right) { while (left < right) { int pivot = partition(nums, left, right); if (pivot - left < right - pivot) { quickSort(nums, left, pivot - 1); left = pivot + 1; } else { quickSort(nums, pivot + 1, right); // 递归排序右子数组 right = pivot - 1; } } } public int medianThree(int[] nums, int left, int mid, int right) { int l = nums[left]; int m = nums[mid]; int r = nums[right]; if ((l <= m && m <= r) || (r <= m && m <= l)) { return mid; } else if ((m <= l && l <= r) || (r <= l && l <= m)) { return left; } return right; } public void swap(int[] nums, int left, int right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } public int partition(int[] nums, int left, int right) { int pivotIndex = medianThree(nums, left, (left + right) / 2, right); swap(nums, pivotIndex, left); int pivot = nums[left]; int l = left + 1; int r = right; while (l <= r) { while (l <= r && nums[l] <= pivot) { l++; } while (l <= r && nums[r] >= pivot) { r--; } if (l < r) { swap(nums, r, l); } } swap(nums, r, left); return r; } }如果是普通递归，那么一下就会占满，栈空间
我们可以在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过 n/2 ，因此这种方法能确保递归深度不超过 logn ，从而将最差空间复杂度优化至 O(logn) 。
3.2归并排序
3.2.1自顶向下（递归排序）
数组排序：先递归把数组切分到只剩一个元素（注意切分的时候每个数组元素的切分边界，虽然不影响结果，但我推荐使用整除2，因为这样易于理解）
假设我们有一个数组
[3, 5, 8, 4, 7, 2, 1]，它会按照如下步骤进行分解和合并：
- 初始数组：
[3, 5, 8, 4, 7, 2, 1]
- 拆分为两部分：
[3, 5, 8, 4]和[7, 2, 1]- 继续拆分：
[3, 5, 8, 4]拆分为[3, 5]和[8, 4][7, 2, 1]拆分为[7]和[2, 1]- 继续拆分直到每部分都为单个元素：
[3, 5, 8, 4]被拆分成[3]和[5],[8],[4][7, 2, 1]被拆分成[7],[2],[1]- 然后开始合并，合并的子数组大小不一定相等：
[3]和[5]合并为[3, 5][8]和[4]合并为[8, 4][7]和[2]合并为[7, 2][3, 5]和[8, 4]合并为[3, 5, 8, 4][1]和[7, 2]合并为[1, 2, 7]- 最后合并两大部分：
- 合并为
[1, 2, 3, 4, 5, 7, 8]
class Solution {
public int[] sortArray(int[] nums) {
int n = nums.length;
int[] temp = new int[n];
mergeSort(nums, 0, nums.length - 1, temp);
return nums;
}
public void mergeSort(int[] nums, int left, int right, int[] temp) {
if (left >= right) {
return;
}
// 整除2，就是偶数偏右，奇数中间，这里需要对半分所有是除2，这样好看些，但是其实并不影响结果
int mid = (left + right) / 2;
mergeSort(nums, left, mid, temp);
mergeSort(nums, mid + 1, right, temp);
merge(nums, left, mid, right, temp);
}
public void merge(int[] nums, int left, int mid, int right, int[] temp) {
int i = left, m = mid + 1, j = right, k = 0;
// 对半分，左边要包括mid，因为上面是/2
while (i <= mid && m <= right) {
if (nums[i] <= nums[m]) {
temp[k] = nums[i];
i++;
} else {
temp[k] = nums[m];
m++;
}
k++;
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (m <= right) {
temp[k++] = nums[m++];
}
k--; // k 指向最后一个有效元素
while (k >= 0) {
nums[right--] = temp[k--]; // 使用 right--，逐步填充 nums
}
}
}
-
链表的排序
class Solution { private ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode mid = slow.next; slow.next = null; // 断开mid的前一个节点和mid的连接 return mid; } private ListNode merge(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(); ListNode cur = dummy; while (list1 != null && list2 != null) { if (list1.val > list2.val) { cur.next = list2; list2 = list2.next; } else { cur.next = list1; list1 = list1.next; } cur = cur.next; } cur.next = (list1 != null ? list1 : list2); return dummy.next; } public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode head2 = middleNode(head); head = sortList(head); head2 = sortList(head2); return merge(head, head2); } }
3.2.2自顶向上（非递归排序）
-
合并过程和递归是一样的，只是在分隔的时候不一样，记住，如果数组元素有两个，加上2，就变成三个，记得减一。
思路就是先for循环递增一共step，表示合并区间不端变大，然后size标识合并数组区间，mid为什么去min？
是为了防止最后不满left + step - 1，防止越界访问。right也是同理，防止最后的区间不满足left + step*2 - 1然后非法访问出错
class Solution { public int[] sortArray(int[] nums) { int n = nums.length; int[] temp = new int[n]; mergeSort(nums, temp); return nums; } public void mergeSort(int[] nums, int[] temp) { int n = nums.length; for (int step = 1; step < n; step *= 2) { // 分块合并的过程 for (int left = 0; left < n; left += step * 2) { int mid = Math.min(left + step - 1, n - 1); // 中间位置 int right = Math.min(left + 2 * step - 1, n - 1); // 右边界 merge(nums, left, mid, right, temp); } } } public void merge(int[] nums, int left, int mid, int right, int[] temp) { int i = left, m = mid + 1, j = right, k = 0; // 对半分，左边要包括mid，因为上面是/2 while (i <= mid && m <= right) { if (nums[i] <= nums[m]) { temp[k] = nums[i]; i++; } else { temp[k] = nums[m]; m++; } k++; } while (i <= mid) { temp[k++] = nums[i++]; } while (m <= right) { temp[k++] = nums[m++]; } k--; // k 指向最后一个有效元素 while (k >= 0) { nums[right--] = temp[k--]; // 使用 right--，逐步填充 nums } } } -
链表排序
class Solution { private ListNode split(ListNode head, int size) { for (int i = 0; i < size - 1 && head != null; i++) { head = head.next; } if (head == null || head.next == null) { return null; } ListNode temp = head.next; head.next = null; return temp; } private ListNode[] merge(ListNode head1, ListNode head2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; while (head1 != null && head2 != null) { if (head1.val > head2.val) { cur.next = head2; head2 = head2.next; } else { cur.next = head1; head1 = head1.next; } cur = cur.next; } cur.next = head1 != null ? head1 : head2; while (cur.next != null) { cur = cur.next; } return new ListNode[]{dummy.next, cur}; } private int getLength(ListNode head) { int count = 0; while (head != null) { head = head.next; count++; } return count; } public ListNode sortList(ListNode head) { if (head == null) return null; // 先计算一次长度 int length = getLength(head); ListNode dummy = new ListNode(0, head); for (int step = 1; step < length; step *= 2) { ListNode cur = dummy.next; ListNode newTail = dummy; while (cur != null) { ListNode head1 = cur; ListNode head2 = split(head1, step); cur = split(head2, step); ListNode[] merged = merge(head1, head2); newTail.next = merged[0]; newTail = merged[1]; } } return dummy.next; } }
3.3堆排序
-
流程
- 输入数组并建立大顶堆。完成后，最大元素位于堆顶。
- 将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减 1 ，已排序元素数量加 1 。
- 从堆顶元素开始，从顶到底执行堆化操作（sift down）。完成堆化后，堆的性质得到修复。
- 循环执行第
2.步和第3.步。循环 n−1 轮后，即可完成数组排序。
-
代码
class Solution { public int[] sortArray(int[] nums) { return heapSort(nums); } public int[] heapSort(int[] nums) { int n = nums.length; for (int i = n / 2 - 1; i >= 0; i--) { shiftdown(nums, n, i); } for (int i = n - 1; i > 0; i--) { int tmp = nums[0]; nums[0] = nums[i]; nums[i] = tmp; shiftdown(nums, i, 0); } return nums; } private void shiftdown(int[] nums, int n, int i) { while (true) { int l = i * 2 + 1; int r = i * 2 + 2; int ma = i; if (l < n && nums[l] > nums[ma]) ma = l; if (r < n && nums[r] > nums[ma]) ma = r; // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出 if (ma == i) break; int temp = nums[ma]; nums[ma] = nums[i]; nums[i] = temp; i = ma; } } }首先根据堆的性质，shiftdown除叶子节点所有节点，只需要0（n）复杂度，然后进行原地交换排序实现