1、插入排序
2、希尔排序
3、选择排序
4、冒泡排序
5、归并排序
6、快速排序
7、计数排序
8、基数排序

1、插入排序

算法原理

插入排序是最为直观的排序算法。它的原理就是对于已经被排序的序列构建一个有序数列，然后对于未处理的数据，在每次排序的时候对有序数列扫一遍，找到插入的位置，然后把这个位置之后的所有元素向后移一位，把这个位置空出来给当前元素。

实现步骤

1、将原数列中的第一个元素视为一个有序数列，视第二个元素至最后一个元素为未排序元素。
2、从头至尾扫描整个未排序数列，然后将扫描到的每个元素插入到有序序列中的适当位置。

算法代码

void insert_sort(int *num, int len) {
    for (int i = 1; i < len; ++i) {
        int temp = num[i];
        int j = i;
        while (j > 0 && num[j - 1] > temp) {
            num[j] = num[j - 1];
            --j;
        }
        num[j] = temp;
    }
}

性能分析

最好情况（原始记录按关键字有序排列）：$O(n)$
"比较"的次数：$\sum\limits_{i=2}^n 1 = n - 1$
"移动"的次数：$0$

最坏情况（原始记录按关键字逆序排列）：$O(n^2)$
"比较"的次数：$\sum\limits_{i = 2}^n {\left( {i + 1} \right)} = \frac{{\left( {n + 4} \right)\left( {n - 1} \right)}}{2}$
"移动"的次数：$\sum\limits_{i = 2}^n {\left( {i + 1} \right)} = \frac{{\left( {n + 4} \right)\left( {n - 1} \right)}}{2}$

结论：适用原始数基本有序或数据量不大的情况。

2、希尔排序

算法原理

1959年Shell发明，第一个突破O(n^2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序，希尔排序的核心在于间隔序列的设定。

实现步骤

1、选择一个增量序列$t(t_i > t_j\, , i < j)$
2、按照增量序列元素个数进行多次排序
3、每次排序根据对应的增量$t_i$将待排序的数列分成若干个长度为$m$的子表，分别对各子表直接进行插入排序。当增量因子为$1$的时候，整个序列作为一个表来处理，表长度就是整个序列的长度。

算法代码

void shell_sort(int num[], int len) {
    int i, j, k, group, temp;
    for (group = len / 2; group > 0; group /= 2) {
        // 对每个分组进行插入排序
        for (i = 0; i < group; ++i) {
            for (j = i + group; j < len; j += group) {
                if (num[j - group] > num[j]) {
                    temp = num[j];
                    k = j - group;
                    while (k >= 0 && num[k] > temp) {
                        num[k + group] = num[k];
                        k -= group;
                    }
                    num[k + group] = temp;
                }
            }
        } 
    }
} 

希尔排序的分析较为复杂，因为它的时间是所取“增量”序列的函数，这涉及到一些数学上尚未解决的难题。增量序列有各种取法，但需注意：应使增量序列中的值没有除$1$以外的公因子，并且最后一个增量值必须等于$1$。

3、选择排序

算法原理

选择排序也是一种相当直观的排序算法，实现原理也就是每次找到未排序序列中的最大值或者最小值放进有序序列中。

实现步骤

1、首先在未排序序列中找到最小（大）元素，存放到排序序列的初始位置。
2、再从剩余未排序的元素中找到最小（大）元素，放在排序序列的末尾。
3、重复步骤2直到所有元素被排序完毕。

算法代码

void select_sort(int num[], int len) {
    for (int i = 0; i < len - 1; ++i) {
        int j = i;
        for (int k = i + 1; k < len; ++k) {
            if (num[k] < num[j]) j = k;
        }

        if (j != i) {
            int temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }
}

4、冒泡排序

算法原理

冒泡排序也是一种简单直观的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

实现步骤

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻的元素做同样的工作，从开始的第一对到末尾的最后一对。这步做完后，末尾的元素会是最大的数。
3、针对所有的元素进行以上步骤，除了最后一个。
4、持续对每次越来越少的元素重复上面的步骤，直到没有任何任何一对数字需要比较。

算法代码

void bubble_sort(int num[], int len) {
    bool exchange;
    for (int i = 0; i < len - 1; ++i) {
        if (num[j] > num[j + 1]) {
            int temp = num[j];
            num[j] = num[j + 1];
            num[j + 1] = temp;
            exchange = true;
        }
    }
    if (!exchange) return;
}

5、归并排序

算法原理

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

实现步骤

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一个位置；
4、重复步骤3直到某一指针达到序列尾；
5、将另一序列剩下的所有元素直接复制到合并序列尾。

算法代码

// first和end为num第一个元素和最后一个元素的索引 
void merge_sort(int num[], int first, int end) {
    if (first < end) {
        int mid = (first + end) / 2;
        merge_sort(num, first, mid);
        merge_sort(num, mid + 1, end);
        merge(num, first, mid, end);
    }
}

void merge(int num[], int first, int mid, int end) {
    int n1 = mid - first + 1, n2 = end - mid;
    int *L = new int[n1], *R = new int[n2];
    for (int i = 0; i < n1; ++i) {
        L[i] = num[first + i];
    }
    for (int i = 0; i < n2; ++i) {
        R[i] = num[mid + i + 1];
    }
    int i = 0, j = 0, k = first;
    while (i < n1 && j < n2) {
        if (L[i] < R[j]) num[k++] = L[i++];
        else num[k++] = R[j++];
    }
    while (i < n1) num[k++] = L[i++];
    while (j < n2) num[k++] = R[j++];
    delete [] L;
    delete [] R;
}

6、快速排序

算法原理

快速排序是由东尼$·$霍尔所发展的一种排序算法，在平均状况下，排序 $n$个项目要$Ο(nlogn)$次比较。在最坏状况下则需要$Ο(n^2)$次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn) 算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法策略来把一个串行分为两个子串行。

实现步骤

1、从数列中挑出一个元素，作为基准；
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放在基准后面（相同的数可以任一边），在这个分区退出之后，该基准就处于数列的中间位置，这个称为分区操作；
3、递归地把小于基准值元素的子数列和大于子数列基准值的子数列排序。递归的最底部情形，是数列的大小是$0$或$1$，也就是所有元素都已经被排好序了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代中，它至少把一个元素摆到它最后的位置去。

算法代码

int partition(int num[], int left, int right) {
    int x = num[right];
    int i = left;
    int j = left - 1;
    for (; i < right; ++i) {
        if (num[i] < x) {
            ++j;
            if (j != i) swap(num[j], num[i]); 
        }
    }
    swap(num[j + 1], num[right]);
    return j + 1; // 返回分割点　 
}

void quick_sort(int num[], int left, int right) {
    if (left < right) {
        int index = partition(num, left, right);
        quick_sort(num, left, index - 1);
        quick_sort(num, index + 1, right);
    }
}

7、计数排序

算法原理

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

实现步骤

1、找出待排序的数组中最大和最小的元素；
2、统计数组中每个值为$i$的元素的出现次数，存入数组$C$的第$i$项；
3、对所有的计数累加（从$C$中的第一个元素开始，每一项和前一项相加）；
4、反向填充目标数组：将每个元素$i$放在新数组的第$C(i)$项，每放一个元素就将$C(i)$减去$1$。

算法代码

// k为待排序数组的最大值+1
void counting_sort(int num[], int len, int k) {
    int *count = new int[k + 1];
    int *tmp = new int[len];

    for (int i = 0; i < k; ++i) count[i] = 0;

    for (int i = 0; i < len; ++i) count[num[i]]++;

    for (int i = 1; i < k; ++i) count[i] += count[i - 1];

    int index;
    for (int i = 0; i < len; ++i) {
        index = count[num[i]];
        tmp[index - 1] = num[i];
        count[num[i]]--;
    }

    for (int i = 0; i < len; ++i) num[i] = tmp[i];
}

OI-Wiki上的简化版本：

const int N = 100010;
const int W = 100010;

int n, w, a[N], cnt[W], b[N];

void counting_sort() {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}

8、基数排序

算法原理

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

实现步骤

1、取得数组中的最大数获得位数；
2、从最低位开始对每个位组成$radix$数组；
3、对$radix$数组进行计数排序（利用了计数排序小范围数的特点）

算法代码

int max_bit(int num[], int len) {
    int bit = 1;
    int radix = 10;
    for (int i = 0; i < len; ++i) {
        while (num[i] >= radix) {
            radix *= 10;
            bit++;
        }
    }
}

void radix_sort(int num[], int len) {
    int bitCount = max_bit(num, len);
    int *tmp = new int[len]; 
    int *count = new int[10]; // 计数器
    int radix = 1;
    for (int i = 0; i < bitCount; ++i) { // 进行bitCount次排序 
        for (int j = 0; j < 10; ++j) count[j] = 0;
        for (int j = 0; j < len; ++j) {
            int k = (num[j] / radix) % 10;
            count[k]++;
        }
        for (int j = 1; j < 10; ++j) { // 将tmp中的位置一次分配给每个桶 
            count[j] = count[j] + count[j - 1];
        }
        for (int j = len - 1; j >= 0; --j) { // 将所有桶中记录收集到tmp中 
            int k = (num[j] / radix) % 10;
            tmp[count[k] - 1] = num[j];
            count[k]--;
        }
        for (int j = 0; j < len; ++j) { // 复制临时数组的内容到num 
            num[j] = tmp[j];
        }
        radix *= 10;
    } 
    delete [] tmp;
    delete [] count;
}

一些练习题：

1、 明明的随机数
2、 奖学金
3、 区间
4、 宇宙总统