自己综合了一些大佬的代码，做个笔记。
其实就是复习一下。。。

#include <iostream>

using namespace std;
int cnt = 0; 
int range = 20;

// 冒泡排序 O(n^2) 稳定

void bubbleSort(int a[], int n)
{
    for(int i = n - 1; i > 0; i--)
    {
        bool flag = true;
        for(int j = 0; j < i; j++)
        {
            if(a[j] > a[j+1]) 
            {
                swap(a[j], a[j+1]);                                             // 从前到后遍历，依次冒泡最大的数 
                flag = false;
            }                                               
        }
        if(flag)
             break;
    }
}

// 梳排序(冒泡优化) O(nlog(n)) 

void combSort(int a[],int l,int r)
{
    float factor = 1.3;
    int g = r - l + 1;
    int n = r + 1;
    bool flag = true;
    while( g > 1 || flag )
    {
        g = ( g > 1 ) ? g / factor : g;                                         // 确定梳长g,由旧g/factor确定 
        flag = false;
        int i = 0;
        while( i + g < n )                                                      // flag为false且g=1直接跳出循环
        {
            if(a[i] > a[g+i])
            {
                swap(a[i], a[g+i]);
                flag = true;
            }
            i = i + 1;
        }
    }
}

// 快速排序 O(nlogn)

void quickSort(int a[], int l, int r)
{
   if(l>=r) return;                                                             // 输入错误 

   int i = l, j = r, tmp = a[l];                                                // 取值 

   while(i < j)
   {
        while(i < j && a[j] >= tmp)                                             // j下标移动直到右端数值比基准小 
            j--;
        while(i < j && a[i] <= tmp)                                             // i下标移动直到左端数值比基准大 
            i++;
        if(i < j) 
            swap(a[i],a[j]); 
   }
   a[l] = a[i];                                                                 // 基准与a[i]交换，归位 
   a[i] = tmp;
   quickSort(a,l,i-1);                                                          // a[i]已归位 
   quickSort(a,i+1,r);
}

// 快速排序(优化) O(nlogn)

void quickSort_pro(int a[], int l, int r)
{
   if(l>=r) return;                                                             // 输入错误 

   int i = l-1, j = r+1, tmp = a[l];                                            // 取值 

   while(i < j)
   {
        do i++; 
           while(tmp>a[i]);                                                     // i下标移动直到左端数值比基准大 
        do j--; 
            while(tmp<a[j]);                                                    // j下标移动直到右端数值比基准小 
        if(i < j) 
            swap(a[i],a[j]); 
   }
   quickSort(a,l,j);                                                            // a[j]未归位，继续代入排序 
   quickSort(a,j+1,r);
}

// 插入排序 O(n^2) 稳定

void insertSort(int a[], int n)
{
    for(int i = 1; i < n; i++)
    {
        int tmp = a[i], j;
        for(j = i; j > 0 && tmp < a[j-1]; j--)                                  // 从第二位开始向后遍历，倒序与之前比较，大值后移，停止时插入 
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

// 折半插入排序 O(n^2) 

void insertSort_pro(int a[], int n)
{
    int i, j, low, high, mid, temp;
    for(i = 1; i < n; i++)
    {
        temp = a[i];
        low = 0;
        high = i - 1;

        while(low <= high)                                                      // 从前往后，逐次二分查找a[i]位置 
        {
            mid = (low + high) >> 1;
            if(temp < a[mid])
                high = mid - 1;
            else low = mid + 1;
        }

        for(j = i ; j >= low ; j--)                                             // low后的元素后移 
            a[j] = a[j - 1];    
        a[low] = temp;
    }
}

// 选择排序 O(n^2)

void selectSort(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(a[i] > a[j]) 
                swap(a[i], a[j]);                                               // 从前到后遍历，依次与后值比较，大于便交换 
        }
    }
}

// 归并排序 O(nlogn) 稳定

void mergeSort(int a[], int l, int r)
{
    if(l >= r) return;

    int tmp[r+1];
    int mid = l + r >> 1;
    mergeSort(a,l,mid), mergeSort(a,mid+1,r);
    int i = l , j = mid + 1, k = 0;                                             // a,j分别为两个区间的起点 

    for(k = l; k <= r; k++)
    {
        if(j > r || (i <= mid && a[i] <= a[j]) )                                // 右区间已遍历完成 或 左区间未遍历完成且a[i]<=a[j]    
            tmp[k] = a[i++];                                                    // 获得左区间数值 
        else                                                                    // 右区间未遍历完成 且 左区间遍历完成或a[i]>a[j] 
        {    
            cnt += mid - i + 1;                                                 // 统计逆序对 
            tmp[k] = a[j++];
        }    
    } 

    for( k = l; k <= r; k++)
      a[k] = tmp[k];                                                            // 赋值原数组 
}

// 堆排序 O(nlogn)

void adjust_heap(int a[], int x, int n)
{
    int l = x * 2 + 1;                                                          // 左孩子结点 
    int r = x * 2 + 2;                                                          // 右孩子结点 
    int max = x;                                                                // 临时变量 

    if(l < n && a[l] > a[max])                                                  // 左孩子大于叶子结点 
        max = l;
    if(r < n && a[r] > a[max])                                                  // 右孩子大于叶子结点 
        max = r;

    if(max != x)
    {
        swap(a[x], a[max]);                                                     // 调整 
        adjust_heap(a, max, n);
    }
}

void heapSort(int a[], int n)
{
    for(int i = n/2-1; i >= 0; i--)                                             // 非叶子结点最大序号值 
        adjust_heap(a, i, n);

    for(int i = n-1; i > 0; i--)
    {
        swap(a[0], a[i]);                                                       // 每次将剩余元素中的最大者放到最后面--排序 
        adjust_heap(a, 0, i);                                                   // 重新调整堆顶为大顶堆
    }
}

// 计数排序 o(n+k) 

void countSort(int a[], int n)
{
    int cnt[range]={0};
    for(int i = 0; i < n; i++) 
        cnt[a[i]]++;                                                            // 计数a[i]中数值出现次数于cnt[a[i]] 

    for(int i = 1, k = 0; i <= n; i++)
    {
        while(cnt[i]--)
            a[k++]=i;                                                           // 将cnt中统计数据逐个赋值给a[k] 
    }
}

// 基数排序 O(n*k) 

int maxbit(int a[], int n) 
{
    int d = 1;                                                                  // 保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(a[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}

void radixSort(int a[], int n) 
{
    int d = maxbit(a, n);
    int tmp[n];
    int count[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 = (a[j] / radix) % 10;                                            // 统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j];                                 // 将tmp中的位置依次分配给每个桶,count中的数字为之前所有个数之和 
        for(j = n - 1; j >= 0; j--)                                             // 将所有桶中记录依次收集到tmp中
        {
            k = (a[j] / radix) % 10;                                            // 求单个数位k 
            tmp[count[k] - 1] = a[j];                                           // a中数值据count数组分配给tmp 
            count[k]--;
        }
        for(j = 0; j < n; j++)                                                  // 将临时数组的内容复制到data中
            a[j] = tmp[j];
        radix = radix * 10;
    }
}

// 希尔排序(选择法) O(nlogn) 

void shellSort_se(int a[], int n)
{
    for(int gap = n / 2; gap > 0; gap /= 2)
    {
        for(int i = gap; i < n; ++i)                                            // 从第gap个元素，逐个对其所在组进行排序操作
        {
            int j = i;
            while(j >= gap && a[j] < a[j - gap])
            {
                swap(a[j], a[j - gap]);                                         // 交换数值 
                j -= gap;
            }
        }
    }
}

// 希尔排序(插入法) O(nlogn) 

void shellSort_in(int a[], int n)
{
    for(int gap = n / 2; gap > 0; gap /= 2)
    {
        for(int i = gap; i < n; i++)
        {
            int j = i;
            int temp = a[i];
            if(a[j] < a[j - gap])
            {
                while(j - gap >= 0 && temp < a[j - gap])
                {
                    a[j] = a[j - gap];                                          // 元素后移 
                    j -= gap;
                }
                a[j] = temp;
            }
        }
    }
}

int main()
{
    int a[] = {3, 2, 1, 5, 3, 10, 3, 7, 6, 7, 9, 8, 1};
    int n = sizeof(a)/sizeof(int);
//    bubbleSort(a, n); 
//  combSort(a, 0, n-1);
//    quickSort(a, 0, n-1);
//    quickSort_pro(a, 0, n-1);
//    insertSort(a, n);
//  insertSort_pro(a, n);
//  shellSort_in(a, n);
//    selectSort(a, n);
//  shellSort_se(a, n);
//    heapSort(a, n);
//  countSort(a, n);
//  radixSort(a, n);
//    mergeSort(a, 0, n-1);
//  cout << cnt << endl;
    for(int i = 0; i < n; i++) 
        cout << a[i] << ' ';
    cout << endl;
}