概要
排序的稳定性
假设Ki=Kj(1<=i<=n,1<=j<=n,i!=j),且在排序前的序列中Ki领先于Kj(即i<j)。
如果，如果排序后Ki扔领先于Kj，则称所用的排序方法是稳定的。
反之，若可能使得排序后的序列中Kj领先于Ki，则称所用的排序方法是不稳定的。
排序算法分类
-
内排序：所有的排序操作都在内存中进行。
-
外排序：要记录的数据太多，不能都存放在内存中，整个排序操作需要进行内存和外存（硬盘）的多次交换；
排序算法比较
注：
-
归并排序可以通过手摇算法将空间复杂度降到O（1），但是时间复杂度会提高。
-
基数排序时间复杂度为O（N*M），其中N为数据个数，M为数据位数。
辅助记忆
- 时间复杂度记忆
- 冒泡、选择、直接插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(\(n^2\)）（一遍找元素O(n)，一遍找位置O(n)）
- 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）
- 稳定性记忆-“快希选堆”（快牺牲稳定性）
- 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。
影响排序算法性能的要素
- 时间性能：主要比较移动的操作
- 辅助空间：是否借助外存储
- 算法的复杂度：算法本身的复杂度
数组交换
/**
交换数组元素
*/
void swap(int array[], int i, int j) {
array[i] = array[i] + array[j];
array[j] = array[i] - array[j];
array[i] = array[i] - array[j];
}
冒泡排序
冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。
代码实现
/**
冒泡排序
*/
void bubble_sort(int array[], int n) {
for (int i = 0; i < n; i++) {
bool flag = true; //设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。
for (int j = 0; j > n - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
flag = false;
}
}
if (false) {
break;
}
}
}
根据上面这种冒泡实现，若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成；若是倒序，比较次数为 n-1+n-2+…+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(\(n^2\))。
选择排序
简单选择排序是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，简单选择排序是不稳定排序。
在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小，交换是个比较耗时的操作。其实我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量min，每一次比较仅存储较小元素的数组下标，当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。代码实现很简单，一起来看下。
代码实现
void selectSort(int array[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (array[j] > array[min]) {
min = j;
}
}
if (min != i) {
swap(array, i, min);
}
}
}
插入排序
直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
代码实现
void insertSort(int array[], int n) {
for (int i = 1; i < n; i++) {
int j = i;
while (j > 0 && array[j - 1] > array[j]) {
swap(array, j - 1, j);
j--;
}
}
}
插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(\(n^2\))。但是在数组元素随机排列的情况下，插入排序还是要优于冒泡和选择两种排序的。
快速排序
快速排序（Quick sort）是对冒泡排序的一种改进，采用的是分治的思想。快速排序简单的说就是选择一个基准（一般选第一个数），将比基准大的数放在一边，小的数放到另一边。对这个数的两边再递归上述方法。
快速排序优化方案
代码实现
// 第一种
void QuickSort_1(int array[], int left, int right) {
if (left > right) {
return;
}
int tempLeft = left;
int tempRight = right;
int value = array[left];
while (tempLeft != tempRight) {
while (array[tempRight] > value && tempRight > tempLeft) {
tempRight--;
}
while (array[tempLeft] <= value && tempRight > tempLeft) {
tempLeft++;
}
if (tempLeft < tempRight) {
swap(array, tempLeft, tempRight);
}
}
array[left] = array[tempLeft];
array[tempLeft] = value;
QuickSort_1(array, left, tempLeft - 1);
QuickSort_1(array, tempRight + 1, right);
}
// 第二种
void QuickSort_2(int array[], int left, int right) {
if (left > right) {
return;
}
int tempLeft = left;
int tempRight = right;
int value = array[left];
while (tempLeft != tempRight) {
while (array[tempRight] >= value && tempRight > tempLeft) {
tempRight--;
}
if (tempRight > tempLeft) {
array[tempLeft] = array[tempRight];
}
while (array[tempLeft] <= value && tempRight > tempLeft) {
tempLeft++;
}
if (tempRight > tempLeft) {
array[tempRight] = array[tempLeft];
}
}
array[tempLeft] = value;
QuickSort_2(array, left, tempLeft - 1);
QuickSort_2(array, tempRight + 1, right);
}
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
void HeapSort(int array[], int n) {
//1.构建大顶堆
for (int i = n / 2 - 1; i >= 0; i--) {
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(array, i, n);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for (int i = n - 1; i > 0; i--) {
swap(array, 0, i);
adjustHeap(array, 0, i);
}
}
/**
自上而下寻找最大值
*/
void adjustHeap(int array[], int i, int lenth) {
int temp = array[i];
for (int k = 2 * i + 1; k < lenth; k = 2 * k + 1) {
if (k + 1 < lenth && array[k] < array[k + 1]) {
k++;
}
if (temp < array[k]) {
array[i] = array[k];
i = k;
}
else {
break;
}
}
array[i] = temp;
}
希尔排序
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(\(n^2\))的第一批算法之一。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
代码实现
void shellSort(int array[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int j = i;
while (j >= gap && array[j] < array[j - gap]) {
swap(array, j, j - gap);
j -= gap;
}
}
}
}
归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
代码实现
void mergeSort(int array[], int n) {
int temp[n];
merge_sort(array, 0, n - 1, temp);
}
void merge_sort(int array[], int left, int right, int temp[]) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(array, left, mid, temp);
merge_sort(array, mid + 1, right, temp);
merge_merge(array, left, mid, right, temp);
}
}
void merge_merge(int array[], int left, int mid, int right, int temp[]) {
int i = left;
int j = mid + 1;
int t =0;
while (i <= mid && j <= right) {
if (array[i] < array[j]) {
temp[t++] = array[i++];
}
else {
temp[t++] = array[j++];
}
}
while (i <= mid) {
temp[t++] = array[i++];
}
while (j <= right) {
temp[t++] = array[j++];
}
t = 0;
while(left <= right){
array[left++] = temp[t++];
}
}
桶排序
桶排序是计数排序的变种，把计数排序中相邻的m个”小桶”放到一个”大桶”中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。
计数排序
基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
计数排序是以牺牲空间换取时间的算法。
执行步骤
(1)找出待排序的数组中最大和最小的元素
(2)统计数组中每个值为i的元素出现的次数，存入数组C的第i项
(3)对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
(4)反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
代码实现
#define NUM_RANGE (100) //预定义数据范围上限，即K的值
void counting_sort(int *ini_arr, int *sorted_arr, int n) { //所需空间为 2*n+k
int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE);
int i, j, k;
//初始化统计数组元素为值为零
for(k = 0; k < NUM_RANGE; k++) {
count_arr[k] = 0;
}
//统计数组中，每个元素出现的次数
for(i = 0; i < n; i++) {
count_arr[ini_arr[i]]++;
}
//统计数组计数，每项存前N项和，这实质为排序过程
for(k = 1; k < NUM_RANGE; k++) {
count_arr[k] += count_arr[k-1];
}
//将计数排序结果转化为数组元素的真实排序结果
for(j = n - 1; j >= 0; j--) {
int elem = ini_arr[j]; //取待排序元素
int index = count_arr[elem] - 1; //待排序元素在有序数组中的序号
sorted_arr[index] = elem; //将待排序元素存入结果数组中
count_arr[elem]--; //修正排序结果，其实是针对算得元素的修正
}
}
基数排序
基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。
基数排序是基于数据位数的一种排序算法。 时间复杂度O(N*最大位数)。 空间复杂度O(N)。
- 分类
- LSD（Least significant digit）—— 从低位向高位排
- MSD（Most significance digit）—— 从高位向低位排
执行步骤
(1)遍历序列找出最大的数(为的是确定最大的数是几位数)；
(2)开辟一个与数组大小相同的临时数组temp；
(3)用一个count数组统计原数组中某一位(从低位向高位统计)相同的数据出现的次数；
(4)用一个start数组计算新数组中某一位(从最低位向最高位计算)相同数据出现的起始位置；
(5)将桶中数据从小到大用temp数组收集起来；
(6)重复(3)(4)(5)直到所有位都被统计并计算过，用temp收集起来；
(7)将temp数组拷回到原数组中；
代码实现
/**
获取最大位数
*/
int getMaxDigit(int array[], int n) {
int base = 10;
int digit = 1;
for (int i = 0; i < n; i++) {
while (array[i] > base) {
digit++;
base *= 10;
}
}
return digit;
}
void radixSort_LSD(int array[], int n) {
int digit = getMaxDigit(array, n);
int base = 1;
int temp[n];
while (digit--) {
// 循环获取个位、十位等相同数字的个数
int count[10] = {0};
for (int i = 0; i < n; i++) {
int index = array[i] / base % 10;
count[index]++;
}
// 获取每一位在新数组的新的起始位置
int start[10] = {0};
for (int i = 1; i < 10; i++) {
start[i] = count[i - 1] + start[i - 1];
}
// 初始化
memset(temp, 0, n * sizeof(int));
// 填充新数组
for (int i = 0; i < n; i++) {
int index = array[i] / base % 10;
temp[start[index]++] = array[i];
}
// 将temp数据copy到array
memcpy(array, temp, n * sizeof(int));
base *= 10;
}
}
