排序算法默写

图片说明

1.快速排序

#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*交换单个元素*/
void swap(vector<int>&vec,int a,int b){
    int temp;
    temp=vec[a];
    vec[a]=vec[b];
    vec[b]=temp;
}
int partition(vector<int>&vec,int lo,int hi){
    swap(vec,lo,lo+rand()%(hi-lo));//随机交换首元素,区间本来是要（hi-lo+1），但是数组区间是从0开始的，本来就小1，不然会越界
    int privot=vec[lo];
    while(hi>lo){
        while(hi>lo&&vec[hi]>=privot)//右边不小于轴点
            hi--;
        if(hi>lo){
           vec[lo]=vec[hi];
           lo++;
        }
        while(hi>lo&&vec[lo]<=privot)//左边不大于轴点
            lo++;
        if(hi>lo){
           vec[hi]=vec[lo];
           hi--;
        }
    }
    vec[lo]=privot;//当左右分堆完后（lo==hi），插入轴点值
    return lo;//返回轴点位置
}
void quicksort(vector<int>&vec,int lo,int hi){
    if(hi==lo){    //递归基，hi与lo不成区间的时候返回
        return;
    }
    int mi=partition(vec,lo,hi);
    if(hi>mi)
    quicksort(vec,lo,mi-1);  //递归得排左边
    if(mi>lo)
    quicksort(vec,mi+1,hi);  //递归得排右边
}
int main(){
    int nums[10]={8,4,2,3,1,5,12,100,9,42};
    vector<int> vec(nums,nums+10);
    int size=vec.size();
    int hight=size-1;
    quicksort(vec,0,hight);
    for(int i=0;i<size;i++){
        cout<<vec[i]<<" ";
    }
    cout<<endl;
}

图片说明
2.选择排序

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void select_sort(vector<int>& vec){  
    int size=vec.size();        
    for(int i=0;i<size-1;i++){    //排到倒数第二个，所以要size-1
        int mins=i;               //而且这里也要注意，对比下标要从i开始
        for(int j=i+1;j<size;j++){ //这里要注意内部循环要对比到最后一个，所以要j<size
            if(vec[j]<vec[mins])
                mins=j;
        }
        swap(vec[i],vec[mins]);
    }
}
int main(){
    int len=10;
    int nums[len]={8,4,2,3,1,5,12,100,9,42};
    vector<int> vec(nums,nums+10);
    int hi=len-1;
    select_sort(vec);
    for(int i=0;i<len;i++){
        cout<<vec[i]<<" ";
    }
    cout<<endl;
}

图片说明

3.插入排序

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void select_sort(vector<int>&vec){
    int size=vec.size();
    for(int i=1;i<size;i++){    //从第二个数开始
        int key=vec[i];         //先用额外空间保存要排的数
        int j=i-1;              //已排序的数的个数
        while((j>=0)&&(key<vec[j])){  //注意这里要对比到第0个数，而且这里要直到找到比第J个数大
            vec[j+1]=vec[j];          //不停的往后移动，刚好j+1=i，不怕被覆盖
            j--;
        }
        vec[j+1]=key;           //找到比j大的位置后相应插入，j+1的数已经往后移一位，已经预留好位置
    }
}
int main(){
    int len=10;
    int nums[len]={8,4,2,3,1,5,12,100,9,42};
    vector<int> vec(nums,nums+10);
    int hi=len-1;
    select_sort(vec);
    for(int i=0;i<len;i++){
        cout<<vec[i]<<" ";
    }
    cout<<endl;
}

图片说明
4.冒泡法

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void maopao_sort(vector<int>& vec){
    int size=vec.size();
    for(int i=0;i<size-1;i++){   //因为是和后面一个对比，所以再迭代过程中迭代到倒数第二个，不然溢出
        for(int j=0;j<size-i-1;j++){    //同样道理，对比到倒数第二个，而且要减去i，因为后面已经是排好的
            if(vec[j]<vec[j+1])
                swap(vec[j],vec[j+1]);
        }
    }
}
int main(){
    int len=10;
    int nums[len]={8,4,2,3,1,5,12,100,9,42};
    vector<int> vec(nums,nums+10);
    maopao_sort(vec);
    for(int i=0;i<len;i++){
        cout<<vec[i]<<" ";
    }
    cout<<endl;
}

图片说明