喜欢文章的话可以收藏或者关注一下…
冒泡排序（从小到大）
相邻两个值比较大小，按照排序规则摆放，重复之前操作，下面代码：
void BubbleSort(vector<int>& nums)
{
for(int i=nums.size()-1;j>0;j--)
{
for(int j=0;j<i;j++)
{
if(nums[j]>nums[j+1])
{
swap(nums[j],nums[j+1]);//元素交换函数
}
}
}
}
以上为最基础的冒泡排序，由于存在最优时间复杂度和最差时间复杂度，所以可以进行简单的优化。
优化方法：
创建一个flag=false；标识，当内层循环发生了一次交换数据就把flag=true；当其中一趟冒泡排序走完之后检查此flag是否为true，未发生修改则直接跳出循环避免空循环没操作。
应用场景：
选择排序（从小到大）
最易于理解的排序，每次选出数组中最值放在相应位置，下面代码：
void SelectSort(vector<int>& nums)
{
int MinIndex=0;
for(int j=1;j<nums.size()-1;j++)
{
MinIndex=j;
for(int i=j;i<nums.size();i++)
{
if(nums[i]<nums[MinIndex])
{
MinIndex=i;
}
}
if(j!=MinIndex)
{
swap(nums[j],nums[i]);
}
}
}
插入排序（从小到大）
将数组分为已排和待排序列，例如：0, 5，6,4，2,3 我们最开始认为0为已排序，然后从5开始向已排查询，寻找到合适位置插入。
void InsertSort(vector<int>& nums){
for (int i = 1; i < nums.size(); i++){
int j = i - 1;//未排序部分
int tmp = nums[i];//待排数
while (j>=0 && tmp<nums[j]){//不越界且大于待排数
nums[j+1] = nums[j];//向后移
j--;
}
nums[j+1] = tmp;//j+1因为循环出来是因为j--后找到的位置
}
}
希尔排序
是一种不稳定排序（相同的元素在排序前后相对位置不变称为稳定排序），按步长分组进行组内排序，当步长为1的时候就相当于插入排序。
void Gap_InsertSort(vector<int>& nums, int start, int gap){//此处用插入排序对 组内排序
for (int i = start; i < nums.size(); i += gap){//以每组第一个开始
int j = i-gap;
int tmp = nums[i];
while (j >= start&&tmp<nums[j]){
nums[j + gap] = nums[j];
j -= gap;
}
nums[j + gap] = tmp;
}
}
void ShellSort(vector<int>& nums){
for (int gap = nums.size() / 2; gap>=1; gap /= 2){//步长 最小为1 对半缩小
for (int i = 1; i < gap; i++){//每组起始角标
Gap_InsertSort(nums,i,gap);
}
}
}
桶排序
根hash的键值差不多，桶建立出来就是有序的只要确定和桶的标号的元素存不存在就好，不适合最值差较大的数组排序，桶会很大懂吧。
void BucketSort(vector<int>& nums){
//找出最值 也就是桶包含所有元素的最大大小
int max = INT_MIN;
for (int c : nums){
max = c > max ? c : max;
}
int* bucket = new int[max + 1];//桶个数=角标+1 直接下面写释放
memset(bucket,0,sizeof(int)*(max+1));//数组初始化函数 容器名 初始值 大小
for (int i = 0; i < nums.size(); i++){
bucket[nums[i]]++;
}
int index = 0;//排序完的数组下标
for (int i = 0; i <= max; i++){
while (bucket[i]--){
nums[index++] = i;//桶标号及为元素值
}
}
delete bucket;
}
堆排序
建立一个最大堆（堆顶元素为整个堆里最大值），每次把堆顶值和最后一个值交换，完成排序。
void max_heap(vector<int>& nums,int start,int end){//建立一个最大堆
int father = start;
int child = 2 * start + 1;
while (child <= end){
if (child + 1 <= end&&nums[child] < nums[child + 1]){//选出一个孩子中大的
child++;
}
if (nums[child]>nums[father]){
swap(nums[child], nums[father]);
}
else{
break;
}
father = child;
child = 2 * father + 1;
}
}
void HeapSort(vector<int>& nums){
for (int i = nums.size() / 2 - 1; i >= 0; i--){
max_heap(nums, 0, i);
}
for (int i = nums.size() - 1; i >0;){//--i传入参数时候减所以不能等于0
swap(nums[i], nums[0]);
max_heap(nums,0,--i);
}
}
快排序
头尾双指针，选择基准值。（快排的复杂度在于基准值的选择 因此衍生出topK问题的目前最优算法BFPRT）
递归写法：
你可以把他想象成挖坑，有点拆了东墙补西墙的味道，基准值就是挖的第一个坑，从right往前找一个比坑小的数，然后挖了去填上一个坑，然后从left往后找第一个比坑小的数挖了去填上一个坑…不断循环直到left=right，最后剩下的那个坑就是最开始挖的那个数最后排序位置（相当于找一个值在排序后的位置）只不过不是从头或者从尾而已。
从后往前找第一个小宇基准值的数 ：左边界和坑一起移；
从后往前找第一个等于基准值的数：右边界单移；
从前往后找第一个大于基准值的数：只动坑；
pair<int, int> partition(vector<int>& nums, int left, int right){
int i = left - 1;
int j = right + 1;
int index = left;//循环结束条件
int tmp = nums[left];
while (index < j){
if (nums[index]>tmp){
j--;
swap(nums[j], nums[index]);
}
else if (nums[index] == tmp){
index++;
}
else {
i++;
swap(nums[i], nums[index]);
index++;
}
}
return {i,j};
}
void QuickSort(vector<int>& nums, int left, int right){
if (left >= right) return;
pair<int, int> p = partition(nums, left, right);
QuickSort(nums, left, p.first);
QuickSort(nums, p.second, right);
}
非递归（栈）
调用函数还是上面那个三色旗函数partition;
void Quick(vector<int>& nums){//压栈出栈顺序就是递归
int left = 0;
int right = nums.size() - 1;
stack<pair<int, int>> stk1;
stk1.push(make_pair(left,right));
while (!stk1.empty()){
pair<int, int> p = stk1.top();
stk1.pop();
pair<int,int> q=partition(nums, p.first, p.second);
if (p.first < q.first){//判断区间内是否有元素
stk1.push(make_pair(p.first, q.first));
}
if (q.second < p.second){
stk1.push(make_pair(q.second, p.second));
}
}
}
归并排序
void merge(vector<int> &nums, int left, int mid, int right)
{
//开辟一块足够大的空间
vector<int> help(right - left + 1, 0);
int i = left, j = mid + 1, index = 0;
while (i <= mid && j <= right)
{
if (nums[i] < nums[j])
{
help[index++] = nums[i++];
}
else
{
help[index++] = nums[j++];
}
}
while (i <= mid)
{
help[index++] = nums[i++];
}
while (j <= right)
{
help[index++] = nums[j++];
}
index = 0;
for (int i = 0; i <= help.size() - 1; i++)
{
nums[left++] = help[index++];//传进来的left不一定是0
}
}
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);
}
本篇文章可以保证代码均运行有效，但不一定保证你能听懂…
复杂度就不总结了随便一搜都有…
转载：https://blog.csdn.net/weixin_44843571/article/details/106297508
查看评论