论坛 › C\C++交流 › C++实现9大排序算法

糖逗 发表于 2020-5-8 14:18:42

C++实现9大排序算法

本帖最后由 糖逗 于 2020-5-14 14:58 编辑

一、冒泡排序
参考视频：https://www.bilibili.com/video/av26394341?p=6

n代表待排序的元素个数
时间复杂度：最好情况O(n）、最坏情况O(n^2)、平均情况O(n^2)       
空间复杂度:O(1)
稳定性：稳定
属于内排序

代码实现：
#include <iostream>
#include <vector>

using namespace std;


void quick_sort(vector<int>& input){
        int len = input.size();
        for(int i = 0; i < len; i++){//i是辅助
                for(int j = 1; j < len - i; j++){
                        if(input > input){
                                swap(input, input);
                        }
                }
        }
}

int main(void){
        vector<int> temp;
        int number;
        while(cin >> number){
                temp.push_back(number);
        }
        quick_sort(temp);
        for(auto cha : temp) cout << cha << " ";
        return 0;
}


注意事项：
1.参考链接：https://mp.weixin.qq.com/s/KWf_1Ntbo3WM52JWkP70Cg
2.稳定性和内外排序的定义参考《大话数据结构》第九章


二、选择排序
参考视频：https://www.bilibili.com/video/BV1N7411B7Nu?from=search&seid=6255878836178982189

n代表待排序的元素个数
时间复杂度：最好情况O(n^2)、最坏情况O(n^2)、平均情况O(n^2)       
空间复杂度:O(1)
稳定性：稳定
属于内排序


#include <iostream>
#include <vector>

using namespace std;


void select_sort(vector<int>& input){
        int len = input.size();
        int index;
        for(int i = 0; i < len-1; i++){
                index = i;
                for(int j = i+1; j < len; j++){
                        if(input < input) index = j;
                       
                }
                swap(input, input);
        }
}

int main(void){
        vector<int> temp;
        int number;
        while(cin >> number){
                temp.push_back(number);
        }
        select_sort(temp);
        for(auto cha : temp) cout << cha << " ";
        return 0;
}

三、插入排序
参考视频：https://www.bilibili.com/video/BV1St411w7X6?from=search&seid=15355451024347335047

n代表待排序的元素个数
时间复杂度：最好情况O(n)、最坏情况O(n^2)、平均情况O(n^2)       
空间复杂度:O(1)
稳定性：稳定
属于内排序

#include <iostream>
#include <vector>

using namespace std;


void sort(vector<int>& input){
        int len = input.size();
        for(int i = 1; i <len; i++){
                for(int j = i; j > 0; j--){
                        if(input < input){
                                swap(input, input);
                        }else{
                                break;
                        }
                       
                }
        }
}

int main(void){
      vector<int> temp;
      int number;
      while(cin >> number){
                temp.push_back(number);
      }
      sort(temp);
      for(auto cha : temp) cout << cha << " ";
      return 0;
}

四、希尔排序

参考视频：https://www.bilibili.com/video/BV1rE411g7rW?from=search&seid=9271654472112320607
https://www.bilibili.com/video/BV1Cx411E7xc?from=search&seid=9243453532555366843
n代表待排序的元素个数
时间复杂度：最好情况O(n^1.3)、最坏情况O(n^2)、平均情况O(nlogn)~O(n^2)
空间复杂度: O（1）
稳定性：不稳定
属于内排序

#include <iostream>
#include <vector>

using namespace std;


void sort(vector<int>& input){
        int len = input.size();
        for(int gap = len/2; gap > 0; gap /=2){
                for(int i = gap; i < len; i++){
                        for(int j = i; j > 0; j--){
                                if(input < input){
                                        swap(input, input);
                                }else{
                                        break;
                                }
                        }
                }
        }
       
}

int main(void){
    vector<int> temp;
    int number;
    while(cin >> number){
            temp.push_back(number);
    }
    sort(temp);
    for(auto cha : temp) cout << cha << " ";
    return 0;
}

五、堆排序
参考视频：https://www.bilibili.com/video/BV1Eb41147dK?from=search&seid=9245800988927155643
n代表待排序的元素个数
时间复杂度：最好情况O(nlogn)、最坏情况O(nlogn)、平均情况O(nlogn)
空间复杂度: O（1）
稳定性：不稳定
属于内排序

#include <iostream>
#include <vector>

using namespace std;

void maxHeap(vector<int>&input, int n, int len){
        if(n >= len) return;
        int root = n, left = 2*n+1, right = 2*n+2;
        if(left < len && input > input) root = left;
        if(right < len && input > input) root = right;
        if(root != n){
                swap(input, input);
                maxHeap(input, root, len);
        }
}

void build(vector<int>&input, int n){
        for(int i = (n-2)/2; i >= 0; i--) maxHeap(input, i, n);
}

void sortHeap(vector<int>&input, int n){
        build(input, n);
        for(int i = n; i > 0; i--){
                swap(input, input);
                maxHeap(input, 0, i-1);
        }
}

int main(void){
        vector<int> input = {3,23,1,6,24,99,35,2,5};
        sortHeap(input, input.size());
        for(auto cha : input) cout << cha << " ";
       
        return 0;
}

六、归并排序

视频参考：https://www.bilibili.com/video/BV1Ax411U7Xx?from=search&seid=4868815010429455110
代码参考：https://www.cnblogs.com/chengxiao/p/6194356.html

n代表待排序的元素个数
时间复杂度：最好情况O(nlogn)、最坏情况O(nlogn)、平均情况O(nlogn)
空间复杂度: O（n）
稳定性：稳定
属于外排序

#include<iostream>
#include<vector>

using namespace std;


void merge(vector<int>&input, int left, int mid, int right, vector<int>&temp){
        int i = left;
        int j = mid + 1;
        int t = 0;
        while(i <= mid && j <= right){
                if(input <= input) temp = input;
                else temp = input;
        }
        while(i <= mid) temp = input;
        while(j <= right) temp = input;
       
        //将temp中的元素全部拷贝到原数组中
        t = 0;
        while(left <= right) input = temp;
}


void sort(vector<int>&input, int left, int right, vector<int>&temp){
        if(left >= right) return;
        if(left < right){
                int mid = (right + left)/2;
                sort(input, left, mid, temp);
                sort(input, mid+1, right, temp);
                merge(input, left, mid, right, temp);
        }
}


int main(){
        vector<int> input = {1,3,5,2,6,21,234,12};
        int len = input.size();
        vector<int> temp(len, 0);
        sort(input, 0, len-1, temp);
        for(auto cha :input) cout << cha << " ";
        return 0;
}



七、快速排序

快速排序感觉看代码比看教程更清楚

n代表待排序的元素个数
时间复杂度：最好情况O(nlogn)、最坏情况O(n^2)、平均情况O(nlogn)
空间复杂度: O(nlogn)~O（n）
稳定性：不稳定
属于内排序

#include <iostream>
#include <vector>

using namespace std;


void quick_sort(int left, int right, vector<int>&input){
        if(right <= left) return;
        int i = left, j = right;
        int base = input;
        while(i < j){
                while(i < j && input >= base) j--;//这一句和下一句的顺序不能变
                while(i < j && input <= base)i++;
                if(i < j) swap(input, input);
               
        }
        swap(input, input);
        quick_sort(left, i-1, input);
        quick_sort(i+1, right, input);
       
}


int main(void){
        vector<int> input = {1, 3, 34, 54, 3,90, 34, 6, 2};
        quick_sort(0, input.size()-1, input);
        for(auto cha : input) cout << cha << " ";
        return 0;
}

八、计数排序（桶排序的一种）
视频参考：https://www.bilibili.com/video/BV1Wb41157ed/?spm_id_from=333.788.videocard.1

n代表待排序的元素个数， k代表数据中可能出现的不同数的个数
时间复杂度：最好情况O(n+k)、最坏情况O(n+k)、平均情况O(n+k)
空间复杂度: O(k)
稳定性：稳定
属于外排序

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int>&input){
        vector<int> res;
        map<int, int> store;
        for(int i = 0; i < input.size(); i++){
                store] ++;
        }
        int min = *min_element(input.begin(), input.end());
        int max = *max_element(input.begin(), input.end());
       
        for(int i = min; i<= max; i++){
                while(store.find(i) != store.end() && store != 0){
                        res.push_back(i);
                        store --;
                }
        }
        return res;
}
int main(){
        vector<int> input = {1, 20, 2, 7, 8, 14, 13, 15, 15, 2};
        vector<int> res = solution(input);
        for(auto cha : res) cout << cha << " ";
        return 0;
}


九、基数排序（桶排序的一种）
视频参考：https://www.bilibili.com/video/BV184411L79P?from=search&seid=14452742656427140512

n代表待排序的元素个数， k代表最高位数的长度。
时间复杂度：最好情况O(n*k)、最坏情况O(n*k)、平均情况O(n*k)
空间复杂度: O(n+k)
稳定性：稳定
属于外排序

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <string>

using namespace std;

void solution(vector<int>&input, int len){
        for(int i = 0; i < len; i++){
                map<int, vector<int>> count;
                int division = pow(10, i);
                for(int j = 0; j < input.size(); j++){
                        int num = input / division % 10;
                        count.push_back(input);
                }
                vector<int> temp;
                for(int m = 0; m < 10; m++){
                        if(count.find(m) != count.end()){
                                temp.insert(temp.end(), count.begin(), count.end());
                        }
                }
                input = temp;
        }
}
int main(){
        vector<int> input = {1, 20, 2, 7, 8, 14, 13, 15, 15, 2};
        int len = 2;
        solution(input, len);
        for(auto cha : input) cout << cha << " ";
        return 0;
}

糖逗 发表于 2020-5-8 14:22:32

待更新{:10_284:}

糖逗 发表于 2020-5-9 10:47:34

永恒的蓝色梦想 发表于 2020-5-8 14:22
点进来之前是点进来之后是仔细一看是

还在写{:10_266:}

糖逗 发表于 2020-5-14 14:59:26

完结撒花{:10_298:}{:10_298:}

糖逗 发表于 2020-7-2 16:58:30

C++中vector的insert参考链接：https://blog.csdn.net/yanbao4070/article/details/80760224

查看完整版本: C++实现9大排序算法