C++复现基础排序算法

2021-03-12 约 400 字预计阅读 1 分钟 - 次阅读

复习一下基本的排序算法

快速排序

时间复杂度O(nlogn)，不稳定这个写法是我刻在DNA里的，应该没什么大问题，除了比较抽象之外都还好。

#include <string>
#include <vector>
#include <iostream>
using namespace std;

void quickSort(vector<int>& arr,int low,int high){
    if(low==high)
        return
    cout<<low<<" "<<high<<endl;
    int i = low;
    int j = high;
    int mid = (i+j)/2;
    int v = arr[mid];
    do{
        while(arr[i]<v) i++;
        while(arr[j]>v) j--;
        if(i<=j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++,j--;
        }
        cout<<"inside"<<i<<" "<<j<<endl;
    }while(i<=j);
    if(i<high){
        quickSort(arr,i+1,high);
    }
    if(j>low){
        quickSort(arr,low,j-1);
    }
}

int main(void){
    vector<int> arr{2,5,3,4,1,9,7};
    quickSort(arr,0,arr.size()-1);
    for(auto ele:arr){
        cout<<ele<<endl;
    }
}

堆排序

理论上可以到O(nlogn)，且是稳定的，所以之前打比赛的时候很喜欢用。 nlogn的版本堆就不能自己写了，要用优先队列

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

void heapSort(vector<int>& arr){
    priority_queue<int,vector<int>,greater<int> > q;
    for(auto ele:arr){
        q.push(ele);
    }
    while(!q.empty()){
        cout<<q.top()<<endl;
        q.pop();
    }

}

int main(void){
    vector<int> arr{2,5,3,4,1,9,7};
    heapSort(arr);
}

如果是自定义类型的话需要重写优先队列的比较函数

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

struct myClass{
    int ele;
    myClass(int e){
        this->ele = e;
    }
};

struct cmp{
    bool operator()(myClass a,myClass b){
        return a.ele>b.ele;
    }
};

void heapSort(vector<int>& arr){
    priority_queue<myClass,vector<myClass>,cmp > q;
    for(auto ele:arr){
        q.push(myClass(ele));
    }
    while(!q.empty()){
        cout<<q.top().ele<<endl;
        q.pop();
    }

}

int main(void){
    vector<int> arr{2,5,3,4,1,9,7};
    heapSort(arr);
}