912. 排序数组，快速排序
给你一个整数数组
nums，请你将该数组升序排列。示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 10(4)
-5 * 10(4) <= nums[i] <= 5 * 10(4)
1. srand(time(NULL)); start，rand开启随机器，给它一个种子time（NULL）。
2. void qsort(vector<int>& nums, int left, int right) { 定义递归函数，qsort，将nums数组left~right区间进行排序
递归内部逻辑，随机选取一个key值，[left,l][l+1,r-1][r,right]分成三个区间，左边元素值小于key，中间元素值等于key，右边元素值大于key。
意义：将key值的元素放到了排序的正确位置
接着将左边区间排序，右边区间排序即可。递归调用自己
3. if (left >= right) return;
递归函数出口，如果区间只有一个元素，left==right，此时不需要排序。
如果区间没有元素，left>right，此时也不需要排序。
合并起来就是left>=right，直接返回return。
4. int key = getRandom(nums, left, right);
编写一个函数直接返回nums数组区间left，right区间随机数值。
5.
递归函数内部逻辑。
[left,right]我们区间是这样的，目标区间划分是这样的[left,l][l+1,r-1][r,right]。
因此我们需要将[left,right]区间中的数全部添加到[left,l][l+1,r-1][r,right]中。
其中left和right是固定的位置，而l和r是我们可以控制的位置。
因此在[l+1,r-1]区间分割出一段区间表示待遍历的区间。
[left,l][l+1,i-1][i,r-1][r,right]左边全是小于key的元素，第二部分全是等于key的元素，第三部分是待遍历的部分，第四部分是小于key的部分。
6. int i = left; int l = left - 1, r = right + 1;
初始化区间，[i,r-1]区间一开始包括[left,right]区间所有元素。
7. while (i < r) {
while循环黑盒，将i位置元素添加到已经处理区间中。 if (nums[i] < key) { swap(nums[i++], nums[++l]);
[left,l][l+1,i-1][i,r-1][r,right]
如果nums[i]<key,说明i位置元素一个位于第一部分，因此将l+1与i位置元素交换，l++，i++。 } else if (nums[i] == key) { i++;
如果nums[i]==key，说明i位置元素位于第二部分，i++即可。 } else { swap(nums[i], nums[--r]);
如果nums[i]>key,说明i位置元素位于第四部分，交换r-1和i位置，r--，此时i不需要++，因为r-1位置原本是待排序元素。 } }
8.
上述代码意义：将元素值为key的元素放到正确的位置上，此时只需要排序左边和右边即可。 qsort(nums, left, l); qsort(nums, r, right); }
9.
获取nums数组left，right区间随机元素。
只需要随机获取left，right区间所有的下标即可。
也就是随机获取left~right这些数字。
等价于随机获取(0~right-left)这些数字，+left偏移量即可。 int getRandom(vector<int>& nums, int left, int right) { int rand1 = rand();
随机获取一个整形。
rand1%（right-left+1）意义：rand1的取值范围为0~right-left+1-1即0~right-left
+left偏移量就等于获取随机left~right，也就是随机区间下标
外面再套取一个nums获取随机值返回即可 return nums[(rand1 % (right - left + 1) + left)]; } };
class Solution {
public:
vector<int> sortArray(vector<int>& nums) { // 快排
// 递归排序---快速排序
// 定义qsort递归函数，排序nums数组
// 内部逻辑，选取key
//[0,left][left+1,right-1][right,n-1]左边小于key，中间等于key，右边大于key
// 先将数值等于key正确排序
// 然后排序左边，排序右边
srand(time(NULL));
int n = nums.size();
qsort(nums, 0, n - 1);
return nums;
}
void qsort(vector<int>& nums, int left, int right) {
// 排序[left,l][l+1,r-1][r,right] key
// 递归出口，如果left==right，区间只有一个数
// 此时不需要排序
// 如果left==l+1,left>right,此时区间没有数，不需要排序
if (left >= right)
return;
int key = getRandom(nums, left, right);
int i = left;
int l = left - 1, r = right + 1;
while (i < r) {
if (nums[i] < key) {
swap(nums[i++], nums[++l]);
} else if (nums[i] == key) {
i++;
} else {
swap(nums[i], nums[--r]);
}
}
qsort(nums, left, l);
qsort(nums, r, right);
}
int getRandom(vector<int>& nums, int left, int right) {
int rand1 = rand();
return nums[(rand1 % (right - left + 1) + left)];
}
};912. 排序数组，归并排序
给你一个整数数组
nums，请你将该数组升序排列。示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 10(4)
-5 * 10(4) <= nums[i] <= 5 * 10(4)
1. vector<int> tmp;
临时数组，用于存储排序后的序列。
2. vector<int> sortArray(vector<int>& nums) { tmp.resize(nums.size());
先给临时数组分配空间，大小为nums的size大小。 mergeSort(nums, 0, nums.size() - 1);
mergeSort函数给nums数组0~nums.size()-1区间排序。 return nums; }
3. void mergeSort(vector<int>& nums, int left, int right) {
定义递归函数mergeSort，给nums数组[left,right]区间排序。 if (left >= right) return;
递归的出口，如果left==right此时区间只有一个元素，不需要再排序。
如果left>right，此时区间没有元素，不需要排序。
合并起来就是left>=right直接返回return。
4.
计算区间中点，以便于我们平均化区间长度，尽可能平均化。 int mid = left + (right - left) / 2; //[left,mid][mid+1,right]
5.
先将[left,mid][mid+1,right]两部分区间进行排序。 mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); 6.
用双指针遍历两端区间，将两端区间进行合并排序区间。 int cur1 = left, end1 = mid; int cur2 = mid + 1, end2 = right; int index = left;
定义index对应tmp临时数组的下标存储合并排序区间。
7. while (cur1 <= end1 && cur2 <= end2) { // 黑盒，cur1,cur2小的放到tmp中index tmp[index++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++]; } 黑盒，每一次内部逻辑，将cur1和cur2中小的元素放到index位置。
放完之后，index++和（cur1++或者cur2++）。 while (cur1 <= end1) { tmp[index++] = nums[cur1++]; } while (cur2 <= end2) { tmp[index++] = nums[cur2++]; }
将还没有排序完的区间依次加入到index中。 8. for (int i = left; i <= right; i++) { nums[i] = tmp[i]; }
最后将排序完，合并完的序列依次赋值给原数组中。 } };
class Solution {
public:
vector<int> tmp;
vector<int> sortArray(vector<int>& nums) {
tmp.resize(nums.size());
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
void mergeSort(vector<int>& nums, int left, int right) {
if (left >= right)
return;
int mid = left + (right - left) / 2;
//[left,mid][mid+1,right]
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
int cur1 = left, end1 = mid;
int cur2 = mid + 1, end2 = right;
int index = left;
while (cur1 <= end1 && cur2 <= end2) { // 黑盒，cur1,cur2小的放到tmp中index
tmp[index++] =
nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
}
while (cur1 <= end1) {
tmp[index++] = nums[cur1++];
}
while (cur2 <= end2) {
tmp[index++] = nums[cur2++];
}
for (int i = left; i <= right; i++) {
nums[i] = tmp[i];
}
}
};小总结
1.快速排序和归并排序都是递归排序。
2.快速排序的递归内部逻辑，只做一小步，这一小步是，随机获取key值，将元素值为key值的元素放到排序的正确位置。
然后左边排序，右边排序。
3.归并排序的递归内部逻辑，只做一小步，将已经排序好的区间[left,mid][mid+1,right]合并成一个排序的区间。
结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！