This wiki is built in Notion. Here are all the tips you need to contribute.
总结
vector<int> BubbleSort(vector<int> &nums) {
int m = nums.size();
if (m == 1) return nums;
for (int i = 0; i < m; i++) {
//每个i的循环都会有一个当前最大值被sort出来
for (int j = 0; j < m - i - 1; j++) {
if (nums[j + 1] < nums[j])
swap(nums[j + 1], nums[j]);
}
}
return nums;
}
选择后面中最小的一个和当前交换
vector<int> SelectSort(vector<int> &nums) {
int numsSize = nums.size();
if (numsSize == 1) return nums;
for (int i = 0; i < numsSize; i++) {
int index = i;
for (int j = i + 1; j < numsSize; j++) {
if (nums.at(j) < nums.at(index)) {
nums.at(index) = nums.at(j);
index = j;
}
}
swap(nums[i], nums[index]);
}
return nums;
}
void merge(vector<int> &nums, int left, int mid, int right){
vector<int> tmp{};
int i=left;
int j=mid+1;
//两指针分别指向待合并数组,按顺序放到tmp中
while(i<=mid && j<=right){
if(nums[i]<=nums[j]){
tmp.emplace_back(nums[i]);
i++;
}else{
tmp.emplace_back(nums[j]);
j++;
}
}
//剩下的元素进入tmp,以下两个while只会运行一个
while(i<=mid){
tmp.emplace_back(nums[i]);
i++;
}
while(j<=right){
tmp.emplace_back(nums[j]);
j++;
}
//将tmp赋给nums
for(int x=0;x<tmp.size();x++){
nums[left+x] = tmp[x];
}
}
void mergeSort(vector<int> &nums, int left, int right){
if(left < right){
int mid = (right + left) >> 1;
mergeSort(nums, left, mid);
mergeSort(nums, mid+1, right);
merge(nums, left, mid, right);
}
}