几种基本排序算法

包括了选择排序、冒泡排序、插入排序、快排、堆排、归并排序、基数排序、计数排序

推荐课程：
左神算法基础班

#include
#include
#include
using namespace std;

void swap(vector& nums,int i,int j){
    if(i==j)return;
    nums[i]=nums[i]^nums[j];
    nums[j]=nums[i]^nums[j];
    nums[i]=nums[i]^nums[j];
}

//选择排序，不稳定，时间复杂度最优==平均
void choiceSort(vector& nums){
    int len=nums.size();
    for(int i=0;i//该范围内选出一个最小值，
        int minIndex=i;//记录最小值的下标
        for(int j=i+1;j
            if(nums[minIndex]>nums[j])minIndex=j;
        }
        swap(nums,i,minIndex);
    }
}
//冒泡排序，稳定，时间复杂度最优==平均
void bubbleSort(vector& nums){
    int len=nums.size();
    for(int i=0;i
        for(int j=0;j
            if(nums[j]>nums[j+1])swap(nums,j,j+1);
        }
    }
}
//插入排序，稳定，时间复杂度最优<平均
void insertSort(vector& nums){
    int len=nums.size();
    for(int i=1;i//在0到i范围内保证有序
        int j=i;
        while(nums[j-1]>nums[j]&&j>=1){
            swap(nums,j-1,j);
            --j;
        }
    }
}
//归并排序，稳定，时间复杂度最优=平均
void mergeSort(vector& nums,int l,int r){
    if(l>=r)return;
    int mid=l+((r-l)>>1);
    mergeSort(nums,l,mid);
    mergeSort(nums,mid+1,r);
    vectortemp(r-l+1);
    int indL=l;
    int indR=mid+1;
    int i=0;
    while(indL<=mid&&indR<=r){
        if(nums[indL]<=nums[indR])temp[i++]=nums[indL++];
        else temp[i++]=nums[indR++];
    }
    while(indL<=mid){
        temp[i++]=nums[indL++];
    }
    while(indR<=r){
        temp[i++]=nums[indR++];
    }
    //将临时数组拷贝
    for(int i=0;i<=r-l;++i){
        nums[l+i]=temp[i];
    }
}

//堆排序，不稳定(若自己实现堆，则实现heapInsert和heapify两个功能)，最优时间复杂度=平均
void heapSort(vector& nums){
    priority_queue,greater>que;
    for(int kk:nums){
        que.push(kk);
    }
    for(int i=0;i
        nums[i]=que.top();
        que.pop();
    }
}

//快速排序，不稳定，最优时间复杂度<平均
vector partition(vector& nums,int l,int r){//做一个荷兰国旗问题
    if(l>=r)return {l,r};
    int standard=nums[r];
    int indLess=l-1;
    int indGreater=r+1;
    int ind=l;
    while(ind//1.当前位置小于标准值 2.当前位置大于标准值 3.当前位置等于标准值
        if(nums[ind]==standard)ind++;
        else if(nums[ind]
            swap(nums,++indLess,ind++);
        }
        else{
            swap(nums,--indGreater,ind);
        }
    }
    return {indLess+1,indGreater-1};//返回等于位置的起始和结束
}
void quickSort(vector& nums,int l,int r){
    if(l>=r)return;
    vector arr=partition(nums,l,r);
    quickSort(nums,l,arr[0]-1);
    quickSort(nums,arr[1]+1,r);
}
//计数排序
void countSort(vector& nums){
    vectortimes(100001);
    for(auto kk:nums){
        times[kk]++;
    }
    int ind=0;
    for(int i=0;i<=100000;++i){
        while(times[i]){
            nums[ind++]=i;
            times[i]--;
        }
    }
}
//基数排序
int getDigit(int n){
    int ans=0;
    while(n){
        n/=10;
        ans++;
    }
    return ans;
}
int getNumberByDigit(int num,int digit){
    while(digit>1){
        num/=10;
        --digit;
    }
    return num%10;
}
void radixSort(vector& nums){
    int len=nums.size();
    int max=0;
    for(auto kk:nums){
        max=max>=kk?max:kk;
    }
    int digit=getDigit(max);//最大数有多少位
    for(int i=1;i<=digit;++i){
        vectortempNums(len);
        vectorcount(10);//存0-9出现的次数
        for(int j=0;j
            count[getNumberByDigit(nums[j],i)]++;
        }
        for(int j=1;j<10;++j){
            count[j]+=count[j-1];
        }
        for(int j=len-1;j>=0;--j){
            int b=getNumberByDigit(nums[j],i);
            tempNums[--count[b]]=nums[j];
        }
        nums=tempNums;
    }
    
}
int main(){
    int n;
    cin>>n;
    vectornums(n);
    for(int i=0;i>nums[i];
    int flag;
    cin>>flag;
    //choiceSort(nums);
    //bubbleSort(nums);
    //insertSort(nums);
    //mergeSort(nums,0,n-1);
    //heapSort(nums);
    //quickSort(nums,0,n-1);
    //countSort(nums);
    radixSort(nums);
    if(!flag){
        for(int i=0;i
        for(int i=n-1;i>=0;--i)cout< 
时间复杂度
额外空间复杂度
稳定性
选择排序
O(N^2)
O(1)
不稳定
冒泡排序
O(N^2)
O(1)
稳定
插入排序
O(N^2)
O(1)
稳定
归并排序
O(N*logN)
O(N)
稳定
堆排序
O(N*logN)
O(1)
不稳定
快速排序
O(N*logN)
O(logN)
不稳定
基数排序
O(N)
O(N)
稳定
计数排序
O(N)
O(N)
稳定