今天是个好天气
今天是个好天气
今天是个好天气
使得相邻两个元素比较大小，大的元素慢慢下沉，下次循环到len - 1 - i，因为底部有一部分已经排序完成了
void bubbleSort(vector<int>& a){
for (int i = 0; i < a.size(); i++){
for (int j = 0; j < a.size() - i - 1; j++){
if(a[j] > a[j + 1])
swap(a[j], a[j + 1]);
}
print(a, i);
}
}
优化方式时，当某一次循环，没有发生交换，说明当前的部分已经有序，可以跳出循环。
void bubbleSort(vector<int>& nums) {
int n = nums.size();
bool flag = false;
for (int i = 0; i < n - 1; ++i) {//i = 0 起，循环了n - 1趟，更符合规范理解
flag = false;
for (int j = 0; j < n - 1 - i; ++j) {
if (nums[j] > nums[j + 1]) {
//某一趟排序中，只要发生一次元素交换，flag就从false变为了true
//也即表示这一趟排序还不能确定所剩待排序列是否已经有序，应继续下一趟循环
swap(nums[j], nums[j + 1]);
flag = true;
}
}
//但若某一趟中一次元素交换都没有，即依然为flag = false
//那么表明所剩待排序列已经有序
//不必再进行趟数比较，外层循环应该结束，即此时if (!flag) break; 跳出循环
if (!flag) { break; }
}
}
时间复杂度：O(n^2)，各论冒泡的遍历数组长度为n - 1, n - 2, ... , 2, 1，求和可得。
空间复杂度：O(1)。
稳定排序：不交换相等元素。
选择排序就是将找打数组中最小的元素，将它和数组的第一个元素交换位置，然后再剩下的元素中找最小的元素，和第二元素的位置交换，如此反复。
void selectSort(vector<int>& nums) {
int len = nums.size();
int minIndex = 0;
for (int i = 0; i < len; ++i) {
minIndex = i;
for (int j = i + 1; j < len; ++j) {
if (nums[j] < nums[minIndex]) minIndex = j;
}
swap(nums[i], nums[minIndex]);
}
}
在保证左边有序的情况下，当第i个元素数值小于i-1时，将之插入到左边有序序列当中。
找到左边有序序列中小于a[i]的位置j，将之插入到j + 1这个位置，如果j这个位置元素数值大于a[i]，向后移动a[j]这个位置元素。
void print(vector<int>& a, int n, int i) {
cout << "step"<< i << ": ";
for (int j = 0; j < n; j++) {
cout << a[j] << " ";
}
cout << endl;
}
void insertionSort(vector<int>& a, int n) {//{ 9,1,5,6,2,3 }
for (int i = 1; i < n; ++i) {
if (a[i] < a[i - 1]) { //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
int j = i - 1;
int x = a[i]; //因为后续将i - 1的值后移，找到合适的位置插入，所以需要存储数 = x;值
while (j >= 0 && x < a[j]) { //查找在有序表的插入位置,还必须要保证j是>=0的 因为a[j]要合法
a[j + 1] = a[j];
j--; //元素后移
}
a[j + 1] = x; //插入到正确位置
}
print(a, n, i); //打印每趟排序的结果
}
}
时间复杂度：O(n^2)。
空间复杂度：O(1)。
稳定排序：不交换相等元素。
/* 元素交换 */
void swap(vector<int>& nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 哨兵划分 */
int partition(vector<int>& nums, int left, int right) {
// 以 nums[left] 作为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素，保证左边小于哨兵，右边大于哨兵,,
}
swap(nums, i, left); // 将哨兵交换到重合位置
return i; // 返回哨兵位置
}
/* 快速排序 */
void quickSort(vector<int>& nums, int left, int right) {
// 子数组长度为 1 时终止递归
if (left >= right)
return;
// 哨兵划分
int pivot = partition(nums, left, right);
// 递归左子数组、右子数组
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
平均时间复杂度：O(nlogn)，平均情况下，哨兵划分的递归层数为logn（基于二分的情况下考虑），每层中的总循环数为n，总体使用O(nlog)。
最差时间复杂度：O(n^2)，最拆的情况下，哨兵划分操作将长度为n的数组划分为长度为0和n - 1的两个子数组，此时递归的层数达到n层，每层的循环数为n，总体使用O(n^2)。
空间复杂度：O(n^2)。
非稳定排序：哨兵划分操作可能改变相等元素的相对位置。
/* 选取三个元素的中位数 */
int medianThree(vector<int>& nums, int left, int mid, int right) {
// 使用了异或操作来简化代码
// 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1
// 1 ^ 0 则nums[left]为中位数
if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right]))
return left;
else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right]))
return mid;
else
return right;
}
//随机选取基准
int SelectPivotRandom(vector<int>& nums, int left, int right){
srand((unsigned)time(NULL)); //保证随机数的不同
int pivotPos = rand() % (right - left) + left;
swap(nums[pivotPos], nums[left]);
return left;
}
/* 哨兵划分（三数取中值） */
int partition(vector<int>& nums, int left, int right) {
// 选取三个候选元素的中位数
int med = medianThree(nums, left, (left + right) / 2, right);
// 将中位数交换至数组最左端
swap(nums, left, med);
// 以 nums[left] 作为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素
}
swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
普通快速排序在某些输入下的时间效率变差。举个极端例子，假设输入数组是完全倒序的，由于我们选取最左端元素为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，从而 左子数组长度为 n−1、右子数组长度为 0 。这样进一步递归下去，每轮哨兵划分后的右子数组长度都为 0 ，分治策略失效，快速排序退化为「冒泡排序」了。
为了尽量避免这种情况发生，我们可以优化一下基准数的选取策略。首先，在哨兵划分中，我们可以 随机选取一个元素作为基准数。但如果运气很差，每次都选择到比较差的基准数，那么效率依然不好。
进一步地，我们可以在数组中选取 3 个候选元素（一般为数组的首、尾、中点元素），并将三个候选元素的中位数作为基准数，这样基准数“既不大也不小”的概率就大大提升了。当然，如果数组很长的话，我们也可以选取更多候选元素，来进一步提升算法的稳健性。采取该方法后，时间复杂度劣化至 O(n*n) 的概率极低
快排没有一定要重右边开始，只是看你基数的位置，如果你基数选的是最左边的。你一定要确保，你交换基数的时候，保证那个数要小于基数。
基数选择了左边，但是还从左边开始，在
l < r的条件，不能保证交换时num[l] < num[povit]。
除了需要随机选择中间点，还移动了povit相同的值，进一步缩小区别，避免几万个2的情况出现。
剪枝，哨兵位置在 k 时，可以返回，即前k个小的数都在左边。
l > k，说明第 k + 1个数在左边序列，前k个数还可能乱，要再排一下；
l < k，说明第 k + 1个数在右边序列，还没有选够k个数，要重新排一下。
void merge(vector<int>& nums, int left, int mid, int right){
//开辟一段空间保存有序的两段空间，[left, mid],[mid + 1, right]，后续覆盖nums原数组的内容
vector<int> tmp = vector<int>(nums.begin() + left, nums.begin() + right + 1);
int leftstart = left - left, leftend = mid - left;
int rightstart = mid - left + 1, rightend = right - left;
//应该看已经排序好数的个数，而不是具体下标
int i = leftstart, j = rightstart;
//用两个指针，分别遍历左右子树的内容
for (int k = left; k <= right; k++){
//左子树遍历完，选择右子树
if(i > leftend){
nums[k] = tmp[j++];
}
//右子树遍历完，或者tmp[i] < tmp[j]，选择左子树
else if(j > rightend || tmp[i] <= tmp[j]){
nums[k] = tmp[i++];
}
//tmp[i] > tmp[j]，选择右子树
else{
nums[k] = tmp[j++];
}
}
}
void mergesort(vector<int>& nums, int left, int right){
if(left >= right){
return;
}
int mid = (left + right) / 2;
mergesort(nums, left, mid);
mergesort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
时间复杂度：O(nlogn)，遍历划分高度为logn的递归树，每层合并的总操作数量为 n，总体时间为O(nlogn)。
空间复杂度：需借助辅助数组实现合并，使用O(n) 大小的额外空间；递归深度为 logn ，使用 O(logn)大小的栈帧空间。
稳定排序：在合并时可保证相等元素的相对位置不变。
归并排序有一个很特别的优势，用于排序链表时有很好的性能表现，空间复杂度可被优化至O(1) ，这是因为：
tmp ；某个菜鸡，花费一小时在折腾数组下标问题上，没想到num[3,4]复制到tmp中对应了tmp[0,1]。如果直接复制整个nums，数组下标问题确实很好解决了。
实际左子树就是[0, mid - left]，右子树[mid - left + 1, right - left]，通过长度划分左右子树，联系到前序和后序二叉树建立二叉树的题目上，划分子树。
略略略。
首先将入度为0（也就是没有先修课程的，肯定可以学）入队，然后不断弹出这些课（学了），找需要先修这门课的，如果这门课入度为0了（先修课修完了），入队。
最后判断学完的所有数量和当前的numCourses是否相等即可。
时间复杂度：
O(E+V)。这里 E 表示邻边的条数，V 表示结点的个数。
倒不如说是数学思路题了，满足顺子的条件，列出大小王的情况去做。
想不到，通过a + b > b + a，来判断摆放的顺序。
- 将后面的大数后前面的小数进行交换
- 肯定越靠近右边越好，并且相邻，这样增长幅度小
- 在 尽可能靠右的低位 进行交换，需要 从后向前 查找
- 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
- 将「大数」换到前面后，需要将「大数」后面的所有数 重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列