void Bubble(vector<int>& nums)
{// 冒泡排序只能先确定最右边的结果，不能先确定最左边的结果for (int i = 0; i < nums.size(); i++){// 确定的右边的就不用排了并且不能让j+1越界// 所以判断条件是nums.size()-i - 1for (int j = 0; j < nums.size()-i - 1; j++)if (nums[j] > nums[j + 1])swap(nums[j], nums[j + 1]);}
}

选择排序重要的是选，先选出来，再将这个数交换进去

void Select(vector<int>& nums)
{for (int i = 0; i < nums.size(); i++){int t = i;// 记录需要交换的数的位置for (int j = i + 1; j < nums.size(); j++)if (nums[t] > nums[j])t = j;swap(nums[t], nums[i]);}
}

插入排序是一个一个往后挪，最后再插入

void Insert(vector<int>& nums)
{for (int i = 0; i < nums.size(); i++){int t = nums[i];// 注意j表示需要检查的位置，这个位置必须遵循j>=0for (int j =i-1; j >= 0; j--){if (nums[j] > t)nums[j + 1] = nums[j];else{nums[j + 1] = t;break;}}}
}

注意j的范围

这种写法类似于冒泡排序，他是往前冒，虽然能对，但是这已经不是插入排序的思想

int* sortArray(int* nums, int numsSize, int* returnSize)
{//插入排序：在已经排好序的数组中进行插入*returnSize=numsSize;for(int i=0;i<numsSize;i++){//从此位置向前比for(int j=i;j>0;j--){if(nums[j]<nums[j-1]){int tem=nums[j];nums[j]=nums[j-1];nums[j-1]=tem;}elsebreak;}}return nums;
}

希尔排序是在插入排序的基础上发展而来，所以要遵循插入排序的逻辑
他和插入排序不同在于，插入排序的gap=1，这个gap是从大到小变化

void Shell(vector<int>& nums)
{for (int gap = nums.size()/2; gap >0; gap/=2)// 间隔	{//每次向后跳间隔个长度for (int i = 0; i < nums.size(); i++) {int t = nums[i];// 注意j的范围for (int j = i-gap; j >= 0; j -= gap){if (nums[j] > t)nums[j + gap] = nums[j];else{nums[j + gap] = t;break;}}}}
}

注意j的范围

我们使用三段式进行排序
[l,left] [left+1,right-1] [right,r]
[l,left]——小于key
[left + 1 , right-1]—— 等于key，等于key的是不用排序
[right , r]——大于key

int getNum(vector<int>& nums, int l, int r)
{srand(time(nullptr));return nums[l + rand() % (r - l + 1)];
}
void quicksort(vector<int>& nums, int l, int r)
{if (l >= r) return;int key = getNum(nums, l, r);int left = l - 1, right = r + 1, g = l;// 采用三段式进行while (g < right){if (nums[g] == key) g++;else if (nums[g] < key) swap(nums[g++], nums[++left]);else swap(nums[g], nums[--right]);}// [l,left][left+1,right-1][right,r]quicksort(nums, l, left), quicksort(nums, right, r);
}

归并排序需要一个辅助数组，我们使用的是vector，使用之前需要进行resize，开足够大的空间的同时要运行进行随机访问

vector<int> tem;
void mergesort(vector<int>& nums, int l, int r)
{if (l >= r) return;int mid = l + r >> 1;mergesort(nums, l, mid), mergesort(nums, mid + 1, r);int left = l, right = mid + 1;int t = 0;while (left <= mid && right <= r){if (nums[left] < nums[right]) tem[t++] = nums[left++];else tem[t++] = nums[right++];}while (left <= mid) tem[t++] = nums[left++];while (right <= r) tem[t++] = nums[right++];t = 0;left = l;while (left <= r) nums[left++] = tem[t++];
}

void up(vector<int>& nums,int t)
{while (t > 0){int parent = (t - 1) / 2;// 大根堆if (nums[parent] < nums[t])swap(nums[parent], nums[t]);t = parent;}
}
void down(vector<int>& nums,int t)
{// 需要从这个位置开始向下down到底int child = t * 2 + 1;while (child < nums.size()){// 找到左右孩子中最小的位置//if (child + 1 < nums.size() && nums[child] > nums[child + 1])//	child++;//if(nums[t]>nums[child]) //	swap(nums[t], nums[child]);if (child + 1 < nums.size() && nums[child] < nums[child + 1]) child++;if (nums[t] < nums[child])swap(nums[t], nums[child]);t = child;child = t * 2 + 1;}
}
void Heap(vector<int>& nums)
{//筛选法建立初始堆——小大根堆都可以//for (int i = nums.size()/2; i >= 0; i--) down(nums, i);//for (int i = 0 ; i < nums.size(); i++) up(nums, i);// 如果想用up初始化堆，只能从头开始
}

1. 筛选法建堆——先将所有数据加入构成堆，在从中间位置开始进行down（只能down，不论是建大堆还是小堆）
   什么时候使用up，为什么up不能在筛选法建堆中使用
   
   就像上图中的情况，在建小堆的过程中，2是一定不能访问到的，就不能建成小堆，所以不能在筛选法中使用up(关键是筛选法起点是中间位置）
   如果想使用up，必须将每一个进行up，或者是某个位置上面的已经成堆，那么就可以在这个位置直接使用up
   对于down来说，如果某个位置下面已经成堆，那么就可以直接使用down