前言
本文代码链接：十大经典排序算法
提取码：2ok3
排序算法是《数据结构与算法》的重要组成部分，在项目实践中，很多时候都需要用到排序算法，而常见的经典排序算法也是很多公司程序员面试的重点。十大经典排序算法如下图所示。
时间复杂度和空间复杂度是衡量一个算法性能好坏的重要指标。而对于排序算法而言，稳定性也是重要指标之一。
教材上给了非常严谨且抽象的定义。
假设ki=kj(1<=i<=n,1<=j<=n,i≠j),且在排序前的序列中ri领先于rj，若果排序后ri仍然领先于rj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先于ri，则称所用的排序方法是不稳定的。
通俗地说，有时候在原序列中两个数值是相等的，如果排序后可以保证原来的相对位置不变，则称该算法是稳定的，若不能保证，则算法是不稳定的。
关于算法的时间复杂度，空间复杂度，稳定性，见下面表格。
1 冒泡排序
冒泡排序是一种交换排序，其基本思想是：两两比较相邻记录的关键字，如果相反则交换，直到没有反序的记录为止。
因较小的数字如同气泡一般慢慢浮到上面，故而得名冒泡排序。
1.1 最简单的排序算法
代码如下：
#include <stdio.h> #define MAXSIZE 10000 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void swap(sqList* L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } void Bubblesort0(sqList* L) { for (int i = 0; i < L->length; i++) { for (int j = i; j < L->length; j++) { if (L->r[i] > L->r[j]) swap(L, i, j); } } } int main() { sqList test = {{9,1,5,8,3,7,4,6,2}, 9}; Bubblesort0(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
以上是最简单的冒泡排序算法的实现，每次循环保证得到该范围内的最小值，排在前面，从而完成排序。如图所示：
然而还有改进的空间。是否可在每次循环的时候，比较更多的关键字呢？于是有了改进版的冒泡排序。
1.2 冒泡排序算法
通过以上的改进思路，可以得到一下的代码。
#include <stdio.h> #define MAXSIZE 10000 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void swap(sqList* L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } void Bubblesort1(sqList* L) { for (int i = 0; i < L->length; i++) { for (int j = L->length - 2; j >= i; j--) { if (L->r[j] > L->r[j+1]) swap(L, j, j + 1); } } } int main() { sqList test = {{9,1,5,8,3,7,4,6,2}, 9}; Bubblesort1(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
通过以上的改进，在每次循环时，可以比较相邻的关键字，从而变得更加高效。如下图所示：
从上图可以看出，一次循环就可以比较更多的数值。所以是个更好的方法。
1.3 冒泡排序算法优化
上面的例子虽然是正宗的冒泡排序算法，但是仍然有改进的空间，如果能在需要排序的数组有序的时候停止循环，肯定会更加高效，于是有了下面的代码。
#include <stdio.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void swap(sqList* L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } void Bubblesort2(sqList* L) { short flag = TRUE; for (int i = 0; i < L->length && flag; i++) { flag = FALSE; for (int j = L->length - 2; j >= i; j--) { if (L->r[j] > L->r[j + 1]) { swap(L, j, j + 1); flag = TRUE; } } } } int main() { sqList test = {{9,1,5,8,3,7,4,6,2}, 9}; Bubblesort2(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
这样一来就避免了无意义的循环，如果上次发现算法已经完成了排序，程序就不会进入循环，从而提前结束运行，完成排序任务。
1.4 冒泡排序算法总结
冒泡算法是最常用的算法之一，也是最简单的排序算法之一，但却不是最高效的，以下将介绍其他几种排序算法。
2 选择排序
选择排序的方法也非常好理解，但它并不像冒泡排序一样，遇到顺序不合适的就直接调换位置，而是记录下最小关键字的位置，待循环完毕后再将其与此次循环的第一个关键字的位置做调换，从而保证了每次循环都可以得到该范围内的最小值，故而得名选择排序。
2.1 选择排序的代码实现
具体的实现代码如下。
#include <stdio.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void swap(sqList* L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } void SelectSort(sqList *L) { int i, j, min; for (i = 0; i < L->length; i++) { min = i; for (j = i + 1; j < L->length; j++) { if (L->r[min] > L->r[j]) min = j; } if (i != min) swap(L, i, min); } } int main() { sqList test = {{9,1,5,8,3,7,4,6,2}, 9}; SelectSort(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
通俗地理解，就是不轻易“出手”，外部循环一次，最多调换一次，所以相比冒泡排序稍微高效一些。选择排序的过程如下图所示：
2.2 选择排序算法总结
虽然选择排序比冒泡排序高效一些，但仍然是n2的时间复杂度。
3 插入排序
插入排序又叫直接插入排序或者简单插入排序，这样称呼其实是为了与希尔排序进行区分，其实是同一种排序算法。
所谓插入排序，是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数值增1的有序表。
3.1 插入排序的代码实现
插入排序的具体代码如下所示。
注意在插入排序中有个辅助空间，所以数组的第一个元素值为0，排序后的值无效。
#include <stdio.h> #define MAXSIZE 10000 #define TRUE 1 #define FALSE 0 typedef struct { int r[MAXSIZE + 1]; int length; }sqList; void InsertSort(sqList *L) { int i, j; for (i = 2; i < L->length; i++) { if (L->r[i] < L->r[i - 1]) { L->r[0] = L->r[i]; for (j = i - 1; L->r[j] > L->r[0]; j--) L->r[j + 1] = L->r[j]; L->r[j + 1] = L->r[0]; } } } int main() { sqList test = {{0,9,1,5,8,3,7,4,6,2}, 10}; InsertSort(&test); for (int i = 0; i < test.length; i++) printf("%d\t", test.r[i]); return 0; }
插入排序的算法思想可简单理解为，首先确定需要排序的关键字，然后再放到整个数组的第一个位置，再将其放回原数组中，放回的时候进行排序，但只保证该位置及其前面关键字的相对位置没有问题。
如图所示：
从上图中可以看出，所谓的插入排序，是两两进行比较，若发现顺序相反，则将其放入辅助空间中，然后调整其他元素的位置，找到合适的位置插入，从而完成此次排序。
3.2 插入排序算法总结
与冒泡排序和选择排序算法不同的是，插入排序算法需要一个额外的空间来存储数据，但其性能比前两者要稍微好一些，平均比较和移动的次数约为（n2）/4。
