数组排序
数组排序有很多种方法，但是每种排序方法的稳定性和时间复杂度不尽相同，这也导致了程序运行效率的不同。排序问题属于算法的一部分，如何写出高效的排序算法呢？这一篇内容主要说十个常见的排序方法：
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 归并排序
- 堆排序
- 希尔排序
- 桶排序
- 基数排序
- 计数排序
还有两个比较有用的东西：
- 二分法（查找）
- 时间复杂度
时间复杂度
用时间复杂度可以粗略的估计代码执行时间。注意，是粗略的估计，时间复杂度并不是精确的算出了代码执行的时间，人为的去精算是很难做到的，只是通过一种比较简单的方式去估算。
为什么要估计代码执行时间呢？
学习数据结构和算法就是为了解决“快”和“省”的问题，也就是如何让你的代码在运行时效率更高。一个好的算法可以使你的程序运行的更快，而效率不高的算法可能会使机器卡顿甚至出故障。因此高效率的代码在开发中是很重要的！而时间复杂度就是衡量代码执行效率的一种手段。
时间复杂度表示方法
我们用大 O （不是零，是字母O）来表示时间复杂度。比如下面代码：
void fn(int n){
int sum = 0;
for(int i = 0;i < n;i ++){
sum += i;
}
}
在上面代码中，我们假设每行代码执行的时间都是一样的，时间记作 t，那么上面的函数中的第二行需要一个 t 的时间，第三行和第四行分别需要 n 个 t 的时间，那么这段代码总的执行时间为 (2n + 1)*t。
排序分类
本篇只说内部排序。
-
根据重复关键字的排序情况可分为 稳定排序 和 不稳定排序。所谓稳定是指排序后重复关键字记录的相对次序保持不变（这在后面会详细去说）。
-
根据排序原则，可分为：插入排序、交换排序、选择排序、计数排序、归并排序。
插入排序一般有：- 直接插入排序
- 2路插入排序
- 希尔排序
交换排序有：
- 冒泡排序
- 快速排序
选择排序有：
- 简单选择排序
- 堆排序
- 树形选择排序
-
根据时间复杂度划分，可分为：简单排序（时间复杂度为 n^2）、先进排序（时间复杂度为：nlog(n)）、基数排序（时间复杂度为：d*n）。
简单排序一般有：- 直接插入排序
- 直接选择排序
- 冒泡排序
- 快速排序
先 进排序一般有：
- 堆排序
- 归并排序
冒泡排序
冒泡排序原理很简单。冒泡排序就像站队排高低个一样，在站队排个时，会比较自己与旁边两个人的身高，假如高的往右去，而矮的往左去，当与身边两人中其一交换后，接着再与新的旁边的人比较。冒泡排序的大概流程如下：
加如有一数组：{5,3,1,6,4,2}
5 3 1 6 4 2
|（开始冒泡排序）
3 5 1 6 4 2
3 1 5 6 4 2
3 1 5 4 6 2
3 1 5 4 2 6 （第一趟排完）
|（开始第二趟）
1 3 5 4 2 6
1 3 4 5 2 6
1 3 4 2 5 6 （第二趟排完）
通过上面的一些过程你会发现，在第一趟排完后，最大的数（6）排到了最右边，第二趟排完后除了 6 之外最大的数 5 排到了 6 的后面。冒泡排序是从右往左排好顺序的（右面的大数先排好逐渐往左排，就像冒泡一样，其实更像一个石头投河里，慢慢沉到水底（越重的石头越先到水底））。
这是怎么做到的呢？
冒泡排序也是利用比较交换排序的方式。从左侧第一个数开始与它右边第一个数相比较，若它大于它右边的数则交换，不大于则这一趟不再看这个数了，转而看它右边的那个数与再右边的那个数的大小关系，即：
right < left ---> 交换
right >= left ---> 不交换 ---> 右移数据在比较
再看以上过程（第二趟）：
1 3 5 4 2 6
1 3 4 5 2 6
1 3 4 2 5 6 （第二趟排完）
步骤详解：
- 1 与 3 比 ---> 3 大（
right > left），不交换（就不再看 1 了，转向3 和其后面的数进行比较）。 - 3 与 5 比 ---> 5 大（
right > left），和上一步一样。 - 5 与 4 比 ---> 5 大（
right < left），得交换（并且交换之后 5 接着与后面的数再比）。 - 然后 5 跟 2 比，交换，第二趟排完。
完整程序：
int main(){
int arr[] = {5,7,3,1,4,6,8,2};
int len = sizeof(arr)/sizeof(int);
// 这是为了获取数组长度
int i,j,temp;
for(i = 0;i < len - 1;i ++){
// 最外层循环是排序趟数
for(j = 0;j < len - 1 - i;j ++){
// 里层冒泡操作
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for(int i = 0;i < len;i ++){
printf("%d\t",arr[i]);
}
return 0;
}
选择排序
选择排序也是比较交换排序方式。与冒泡排序不同的是：选择排序在排序时是这么干的：
每次从待排序的数组元素中选出最小的（或最大的）的一个元素，存放在序列的起始位置，然后再从剩余的为排序的元素中继续找最小（或最大）的元素放到已排序序列的末尾。
要做到每一趟都找到待排序元素中最小的元素，这需要借助数组索引。可以从数组的一端开始，把那一端的首元素与其后面的元素作比较，满足条件后总是保留小的元素索引。
完整代码：
int main(){
int arr[] = {5,3,2,6,4,1,8,7};
int len = sizeof(arr)/sizeof(int);
int i,j,index,temp;
for(i = 0;i < len - 1;i ++){
// 外圈循环趟数
index = i;
for(j = i + 1;j < len;j ++){
// 里圈为了找最小元素
if(arr[index] > arr[j]){
// 条件满足后，把 index 指向小的数
index = j;
}
}
// 交换法把小的数移到最左边
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
for(i = 0;i < len;i ++){
printf("%d\t",arr[i]);
}
return 0;
}
下面描述的是第一趟：（只有左边大于右边时index才改变）
5 3 2 6 4 1 8 7 (index == 0;j == 1;i == 0)
|（第一趟）
5 > 3 ---> index == 1; j ++;(j == 2)
3 > 2 ---> index == 2; j ++;(j == 3)
2 < 6 ---> index == 2; j ++;(j == 4)
2 < 4 ---> index == 2; j ++;(j == 5)
2 > 1 ---> index == 5; j ++;(j == 6)
1 < 8 ---> index == 5; j ++;(j == 7)
1 < 7 ---> index == 5; j ++;(j == 8)
|（交换）
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp; // 第一趟走完
1 3 2 6 4 5 8 7
↑ ↑
/* 第二趟时就不看最左边的 1 了。一共走 7 趟（因为在走第七趟时，其（j == 6）后面代排的元素就剩一个了，再一比就排好了（要么交换要么不动））*/
通过上面示例你会发现：选择排序一趟走完会把待排序元素中的最小的元素找出来放在最左端。因此这个数组的七趟排序，毫无疑问会是：
1 ...1 2 ...1 2 3 ...1 2 3 4 ...1 2 3 4 5 ...1 2 3 4 5 6 ...1 2 3 4 5 6 7 8