十大排序（C++代码实现）

淩亂°似流年 2021-11-22 11:12 327阅读 0赞

十大排序的算法复杂度及稳定性如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70][]

所有代码实现根据[https://www.bilibili.com/video/av41042841][https_www.bilibili.com_video_av41042841]动画演示来实现，其实堆排序参考百度百科，所有代码均已简单测试。

#include<iostream>
    #include<vector>
    #include<list>
    using namespace std;
    // 冒泡排序
    void bubble(int arr[], int len){
        for (int i = 0; i < len - 1; i++)
            if(arr[i]>arr[i+1])swap(arr[i],arr[i+1]);
    }
    void bubbleSort(int arr[], int len){
        for (int i = len ; i > 1; i--)
            bubble(arr, i);
    }
    
    // 选择排序
    int findMaxIndex(int arr[], int len){
        int max = arr[0], index = 0;
        for (int i = 1; i < len; i++){
            if(arr[i]>max){
                max = arr[i];
                index = i;
            }
        }
        return index;
    }
    void selectSort(int arr[], int len){
        for (int i = len ; i > 1; i--){
            int maxIndex = findMaxIndex(arr, i);
            swap(arr[i - 1], arr[maxIndex]);
        } 
    }
    
    // 插入排序
    void insertSort(int arr[], int len){
        int t_i = 0;// 找到第一个不是升序的索引 如 3 6 7 4 找到4的索引
        while (t_i < len && arr[t_i]<arr[t_i + 1])t_i++;
        t_i ++;
        if(t_i >= len) return;
        for (int i = t_i; i < len; i++)
        {
            int t = i;
            while (t > 0 && arr[t - 1] > arr[t])
            {
                swap(arr[t], arr[t - 1]);
                t--;
            }
        }
    }
    
    // 计数排序
    void calCountSort(int arr[], int len){
        int max = arr[0], min = arr[0];
    
        for (int i = 1; i< len; i++){
            if(arr[i] > max) max = arr[i];
            if(arr[i] < min) min = arr[i];
        }
    
        int t_len = max - min;
        int *temp = new int[t_len + 1];
        for (int i = 0; i < t_len + 1; i++)
            temp[i] = 0;
        
        for (int i = 0; i < len; i++)
            temp[arr[i] - min]++;
        
        int newIndex = 0;
        for (int i = 0; i <= t_len; i++)
            while (temp[i]--)
                arr[newIndex++]= i + min;
        
        delete[] temp;
        temp = 0;
        
    }
    
    // 基数排序
    void radixSort(int arr[], int len){
        //  index:当前的基数（个、十、百...） max: 数组中最大的数
        int index = 1, max = arr[0];
        for (int i = 1; i < len; i++)
            if(arr[i] > max)max = arr[i];
        
        vector<vector<int>> radix(10,vector<int>());
        while(index < max){
            for (int i = 0; i < len; i++)
            {
                int t = arr[i] / index;// 开始先对个位求基数，随后到百位千位...
                int yushu = t % 10;//基数就是桶的索引
                radix[yushu].push_back(arr[i]);
            }
            // 每次都对所有数据合并
            int newIndex = 0;
            for (int i = 0; i < radix.size(); i++)
            {
                for(auto x : radix[i])
                    arr[newIndex++] = x;
                radix[i].clear();
            }
            index *= 10;//基数向前增加
        }
        radix.clear();
    }
    
    // 快速排序
    int partial(int arr[], int l, int r){
        // 以右边为基准, index记录基准的索引，最后和l交换
        int p = arr[r], index = r;
        while (l < r)
        {
            while (l<r&&arr[l] <= p)l++;
            while (l<r&&arr[r] >= p)r--;
            swap(arr[l], arr[r]);
        }
        swap(arr[index], arr[l]);  
        return l;
    }
    void quickSort(int arr[], int l, int r){
        if(l >= r)return;
        int p = partial(arr, l, r);
        quickSort(arr, l, p - 1);
        quickSort(arr, p + 1, r);
    }
    
    //桶排序
    void bucketSort(int arr[], int len){
        
        int max = arr[0], min = arr[0];
        for (int i = 1; i < len; i++){
            if(max<arr[i])max = arr[i];
            if(min>arr[i])min = arr[i];
        }
        // 桶的个数 = max /10 - min/10 + 1
        int bucketSize = max /10 - min/10 + 1;
        vector<list<int>> buckets(bucketSize + 1, list<int>());   
        int range = (max - 2 + 1) / bucketSize;//每个桶容纳的数
    
        for (int i = 0; i < len; i++)
        {
            int index = (arr[i] - min) / range;// 得到待插入桶的索引
            if(!buckets[index].size())// 如果桶内没有数据 直接插入
                buckets[index].insert(buckets[index].begin(), arr[i]);
            else{// 如果桶有数据 找到合适的插入位置 插入
                auto begin = buckets[index].begin();
                while (*begin < arr[i] && begin != buckets[index].end())begin++;
                buckets[index].insert(begin, arr[i]);
            }
        }
        // 把所有桶内的数据提取出来放到原数组
        int newIndex = 0; 
        for (int i = 0; i < buckets.size(); i++)
            for(auto x : buckets[i])
                arr[newIndex++] = x;
        //清空所有桶数据
        buckets.clear();
    }
    
    // 希尔排序
    void shellSort(int arr[], int len){
        int gap = len / 2;
        while (gap)
        {
            for (int i = gap; i < len; i++)
            {
                int j = i,t = arr[j];
                while (j - gap >= 0 && arr[j - gap] > t)
                {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = t;    
            }
            gap /= 2;
        }
    }
    
    // 归并排序
    // 合并两个有序数组
    void merge(int arr[], int temp[], int l, int m, int r){
        int i = l, j = m + 1, k = l;
        while (i <= m && j <= r)
        {
            if(arr[i] < arr[j])
                temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }
        while (i <= m)
            temp[k++] = arr[i++];
        while (j <= r)
            temp[k++] = arr[j++];
        for (i = l; i <= r; i++)
            arr[i] = temp[i];
    }
    void mergeSort(int arr[], int temp[], int l, int r){
        if(l >= r)return;
        int mid = l + (r - l) / 2;
        mergeSort(arr, temp, l, mid);
        mergeSort(arr, temp, mid + 1, r);
        merge(arr, temp, l, mid, r);
    }
    
    // 堆排序
    void maxHeapify(int arr[], int start, int end) 
    {
        //cout<<start<<": ";
        //建立父节点指标和子节点指标
        int dad = start;// dad:4
        // son 和 son + 1 分别是两个子结点
        int son = dad * 2 + 1;// son:9
        while (son <= end)  //若子节点指标在范围内才做比较
        {    
            if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
                son++;
            if (arr[dad] > arr[son]){ //如果父节点大於子节点代表调整完毕，直接跳出函数
                // cout<<"return"<<endl;
                return;
            }
            else  //否则交换父子内容再继续子节点和孙节点比较
            {
                swap(arr[dad], arr[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
        
        // for (int i = 0; i < 10; i++)
        // {
        //     cout<<arr[i]<<" ";
        // }
        // cout<<endl;
    }
     
    void heapSort(int arr[], int len) 
    {
        //初始化，i从最後一个父节点开始调整
        for (int i = len / 2 - 1; i >= 0; i--)// 4 3 2 1 0
            maxHeapify(arr, i, len - 1);// maxHeapify(arr, 4, 9)
        //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
        for (int i = len - 1; i > 0; i--) 
        {
            swap(arr[0], arr[i]);
            maxHeapify(arr, 0, i - 1);
        }
    }
    int main(){
        int arr[10] = {588, 392, 898, 115, 306, 62, 909, 902, 789, 234};
        int temp[10] = {0};
        mergeSort(arr, temp, 0, 9);
        for (int i = 0; i < 10; i++)
        {
            cout<<arr[i]<<" ";
        }
        system("pause");
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70]: /images/20211122/0f2f2ffd83604cd6a3e4bd24c577138d.png
[https_www.bilibili.com_video_av41042841]: https://www.bilibili.com/video/av41042841