排序算法
冒泡排序
正序：将最大的不断交换到序列末尾
void Bubble_sort(vector<int> &nums){int n = nums.size();bool flag = 0;for(int i = 0;i<n-1;i++){flag = 0;for(int j = 0;j<n-i-1;j++){if(nums[j]>nums[j+1]){// swap(nums[j],nums[j+1]);int t = nums[j];nums[j] = nums[j+1];nums[j+1] = t;flag= 1;}}// 优化:有序后直接，排序结束if(flag == 0) break;}}
选择排序
每一次选择最大的/最小的到最新有序序列末尾
void select_sort(vector<int> &nums){int n = nums.size();for(int i = 0;i<n;i++){for(int j = i+1;j<n;j++){if(nums[j]>nums[i]){int t = nums[i];nums[i] = nums[j];nums[j] = t; }}}}
插入排序
将有序序列的下一个数字插入到有序数列中
void insert_sort(vector<int> &nums){for(int i = 1;i<nums.size();i++){int key = nums[i];int j = i-1;while (j>=0 && nums[j]>key){/* code */nums[j+1] = nums[j];j--;}nums[j+1] = key;}
}
快速排序
子问题：荷兰国旗问题
void quick_sort(vector<int> &nums,int l,int r){// 定基准const int pivot = nums[l+(rand()%(r-l))];int j,k,i;
// partioni = l;j = l;k = r;while (i<k){if(nums[i]<pivot){swap(nums[i++],nums[j++]);}else if(nums[i]>pivot){swap(nums[--k],nums[i]);}else{i++;}}quick_sort(nums,l,i);quick_sort(nums,k,r);}
归并排序
两个步骤
1、左右连部分各自排序
2、左右部分合并到一起
void merge_sort(vector<int> &nums,int l,int r){if (l>=r) return ;int mid = l+((r-l)>>1);// 分int l1 = l,r1 = mid;int l2 = mid+1,r2 = r;merge_sort(nums,l1,r1);merge_sort(nums,l2,r2);// 合vector<int> temp;int k = l;// 比较while (l1<=r1 && l2<=r2){/* code */if(nums[l1]<nums[l2]){temp.push_back(nums[l1++]);}else{temp.push_back(nums[l2++]);}}while (l1<=r1){temp.push_back(nums[l1++]);}while (l2<=r2){temp.push_back(nums[l2++]);}for(int i = l;i<=r;i++){nums[i] = temp[i-l];// temp.pop_back();}}