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

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

所有代码实现根据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;
}