在讲排序之前，我们先列出各种排序的时空复杂度表等等。

冒泡排序

这种过于常见的方法就直接贴代码了

void bubbleSort(vector<int>& arr){
        for(int i = 0; i < arr.size() - 1; i++){
            for(int j = 0; j < arr.size() - 1; j++){
                if(arr[j] > arr[j + 1]){
                    swap(arr[j], arr[j + 1]);
                }
            }
        }
    }

选择排序

void selectionSort(vector<int>& arr){
        for(int i = 0; i < arr.size() - 1; i++){
            int min = i;
            for(int j = i + 1; j < arr.size(); j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
                swap(arr[i], arr[min]);
            }
        }
    }

插入排序

void insertionSort(vector<int>& arr){
        for(int i = 1; i < arr.size(); i++){
            int key = arr[i], j = i - 1;
            while(j >= 0 && key < arr[j]){
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

希尔排序

思路：基于插入排序的一种高效改进，首先我们需要知道插入排序对于几乎排好的数据时的效率较高，但是每次只能移动数据一位是效率极低的。基于这个特性，希尔排序先将序列分成若干个子序列直接进行插入排序，待整个序列基本有序时再全体进行插入排序。

void shellSort(vector<int>& arr){
        int h = 1;
        //可以自定义间隔序列
        while(h < arr.size() / 3){
            h = 3 * h + 1;
        }
        while(h >= 1){
            for(int i = h; i < arr.size(); i++){
                for(int j = i; j >= h && arr[j] < arr[j - h]; j -=h){
                    swap(arr[j], arr[j - h]);
                }
            }
            h /=3;
        }
    }

归并排序

思路：归并排序是对于分治法的典型应用，分而治之的思想一般都可以用自上而下的递归实现。首先申请一个空间存放合并后的序列，设定两个指针指向序列两个序列的起始位置，比较大小，放入空间中，重复步骤直到某指针到达尾端，然后直接合并剩余序列。

void merge(vector<int>& arr, int front, int mid ,int end){
        vector<int> LeftSubArray(arr.begin() + front, arr.begin() + mid + 1);
        vector<int> RightSubArray(arr.begin() + mid + 1, arr.begin() + end + 1);
        int idxLeft = 0, idxRight = 0;
        LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
        RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
        for (int i = front; i <= end; i++) {
            if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
                arr[i] = LeftSubArray[idxLeft];
                idxLeft++;
            } else {
                arr[i] = RightSubArray[idxRight];
                idxRight++;
            }
        }
    }
    void mergeSort(vector<int>& arr, int front, int end){
        if(front >= end){
            return;
        }
        int mid = (front + end) / 2;
        mergeSort(arr, front, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, front, mid, end);
    }

快速排序

思路：快速排序同样运用到了分治法的策略，而且在绝大多数情况下优于归并排序（除顺序性较强的数列），首先挑选一个序列中的一个基准点，将大于它的放在后面，小于它的放在前面，然后不断的递归重复即可。

int parititionl(vector<int>& arr, int low, int high){
        int pivot = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= pivot) {
            --high;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot) {
            ++low;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }
    void quickSort(vector<int>& arr, int low, int high){
        if(low < high){
            int pivot = parititionl(arr, low, high);
            quickSort(arr, low, pivot -1);
            quickSort(arr, pivot + 1, high);
        }
    }

堆排序

思路：堆是一种利用数组实现的近二叉树结构，分为两种

大顶堆：每个节点的值都大于等于其子节点的值

小顶堆：每个节点的值都小于等于其子节点的值

堆排序就是先创建一个堆，然后把堆首和堆尾互换，把堆的尺寸缩小直到为1

void maxHeapify(vector<int>& arr, int start, int end) {
        //建立父子节点
        int dad = start;
        int son = dad * 2 + 1;
        while (son <= end) { // 子节点必须在数组范围内
            if (son + 1 <= end && arr[son] < arr[son + 1]) // 比较节点大小选择大的
                son++;
            if (arr[dad] > arr[son]) // 如果父节点大于子节点则代表调整完毕
                return;
            else { // 否则交换父子节点
                swap(arr[dad], arr[son]);
                dad = son;
                son = dad * 2 + 1;
            }
    }
}

    void heapSort(vector<int>& arr, int len) {
        // 初始化，i从最后一个父节点开始
        for (int i = len / 2 - 1; i >= 0; i--)
            maxHeapify(arr, i, len - 1);
        // 将第一个元素和已经排好的前一位交换，重新调整
        for (int i = len - 1; i > 0; i--) {
            swap(arr[0], arr[i]);
            maxHeapify(arr, 0, i - 1);
        }
    }

计数排序

思路：记录每个值出现的次数，开辟一个空间，按照顺序填充空间即可

vector<int> countingSort(vector<int>& arr){
        int counter[10001] = {0};
        for(int num: arr){
            counter[num]++;
        }
        vector<int> res;
        for(int i = 0; i < 10001; i++){
            while(counter[i]-- > 0){
                res.push_back(i);
            }
        }
        return res;
    }

桶排序

思路：桶排序也是对于分治法的应用之一，将数组分配到若干个桶里面，然后在桶里面执行排序，最后依次取出合并得到一个有序数组。其中最为关键的就是桶的区间如何设计，越接近桶里面平均只有一个数字，算法的时间复杂度就越低。

void Bucket_sort(double a[],size_t n)
{
    double **p = new double *[10];//p数组存放十个double指针，分为10个桶
    for (int i=0; i < 10; ++i)
    {
        p[i] = new double[100];//每个指针都指向一块10个double的数组，每个桶都可以包含100个元素
    }
 
    int count[10] = {0};//元素全为0的数组
    for (int i = 0; i < n; ++i)
    {
        double temp = a[i];
        int flag = (int)(temp*10);//判断每个元素属于哪个桶
        p[flag][count[flag]] = temp;//将每个元素放入到对应的桶中，从0开始
        int j = count[flag]++;//将对应桶的计数加1
 
        //在本桶之中与之前的元素做比较，比较替换（插入排序）
        for (;j > 0 && temp < p[flag][j-1];--j)
        {
            p[flag][j] = p[flag][j-1];
        }
        p[flag][j] = temp;
    }
 
    //元素全部放完之后，需要进行重新链接的过程
    int k = 0;
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < count[i]; ++j)//桶中元素的个数count[i]
        {
            a[k++] = p[i][j];
        }
    }
 
    //申请内存的释放
    for (int i = 0 ; i<10 ;i++)  
    {  
        delete p[i];  
        p[i] =NULL;  
    }  
    delete []p;  
    p = NULL;  
}  
 
void Bucket_sort(vector<double>::iterator begin,vector<double>::iterator end)
{
    double **p = new double*[10];//分10个桶
    for (int i = 0; i < 10; ++i)
    {
        p[i] = new double[end-begin];//每个桶至多存放end-begin个元素
    }
    auto iter1 = begin;
 
    int count[10] = {0};//桶内元素计数
    for (iter1; iter1 != end; ++iter1)
    {
        double temp = *iter1;//保存当前值
        int flag = (int)(temp*10);//确定桶序号
    
        p[flag][count[flag]] = temp;
        int j = count[flag]++;//桶内元素计数加一
 
        for (j;j >0 && temp < p[flag][j-1]; --j)
        {
            p[flag][j] = p[flag][j-1];
        }
        p[flag][j] = temp;//将本值插入桶中的适当位置
    }
 
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < count[i]; ++j)
        {
            *begin++ = p[i][j];
        }
    }
 
    for (int i = 0; i < 10; ++i)
    {
        delete p[i];
        p[i] = NULL;
    }
    delete []p;
    p = NULL;
}
 
 
//随机初始化数组[0,1)
void Initial_array(double a[],size_t n)
{
    for (size_t i = 0; i < n; ++i)
    {
        //rand()的返回值应该是[0, RAND_MAX]，最小可能为0，最大可能为RAND_MAX。
        //rand()/(RAND_MAX+0.0)和rand()/(RAND_MAX+1.0)
        //当rand()返回0，前者为0，后者为0
        //当rand()返回RAND_MAX，前者为1，后者为非常接近1的一个小数。
        a[i] = rand()/double(RAND_MAX+1);
    }

基数排序

思路：将整数按位切割然后进行比较。也利用了桶的概念，根据键值的每位数字来分配桶。

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];              ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}