说起排序算法，可能大家会脱口而出：冒泡排序，选择排序。没错，这是我们最熟悉的两种排序算法，其实，排序算法远不止这些。而且，你之前写的冒泡、选择排序真的是最优的吗？
一、排序算法的分类
总的来说分为两大类，内部排序 和外部排序。
1、内部排序：
就是将需要排序的数据都加载到内存中，然后进行排序。内部排序又分为以下几类：
- 插入排序：包括直接插入排序和希尔排序；
- 选择排序：包括简单选择排序和堆排序；
- 交换排序：包括冒泡排序和快速排序；
- 归并排序
- 计数排序：非比较排序
- 桶排序：非比较排序
- 基数排序：桶排序的扩展
2、外部排序：
内部排序有个问题，加入现在要排序的数据有10亿个，服务器内存加载不了那么多的数据，那就得用外部排序了。外部排序就是先加载一部分，排完了再加载另外一部分，然后再合并。
欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。
二、常见的时间复杂度
时间复杂度从低到高依次有：
- 常数阶：O(1)
- 对数阶：O(logn)
- 线性阶：O(n)
- 线性对数阶：O(nlogn)
- 平方阶：O(n^2)
- 立方阶：O(n^3)
- k次方阶：O(n^k)
- 指数阶：O(2^n)
接下来，就先看看大家最熟悉的冒泡排序和选择排序。为了避免篇幅过长，其他六种排序中的每一种都会用一篇单独的文章来介绍。
三、冒泡排序
时间复杂度为O(n^2)。
1、排序思想：
从前往后遍历待排序的序列，依次比较相邻元素的值，如果逆序，就交换位置。
2、案例：
假入现有一个待排序列：3, 9, -1, 10, 20，现要用冒泡排序算法将其从小到大排列，过程如下：
(1). 第一趟：
- 比较3和9，发现3比9小且3在前面，所以不改变位置，结果是
3, 9, -1, 10, 20，同时两个指针都后移一位； - 比较9和-1，交换它们的位置，结果是
3, -1, 9, 10, 20，同时两个指针都后移一位； - 比较9和10，不发生交换，结果是
3, -1, 9, 10, 20，同时两个指针都后移一位； - 比较10和20，不发生交换，结果是
3, -1, 9, 10, 20，同时两个指针都后移一位；
一趟排序结束后，最大的数就排到最后去了。
(2). 第二趟：
经过第一趟，其实最后面那个数就是最大了，第二趟要做的就是在前面的四个数中找到最大的，放在倒数第二个的位置。
- 比较3和-1，交换位置，结果是
-1, 3, 9, 10, 20，同时两个指针都后移一位； - 比较3和9，不发生交换，结果是
-1, 3, 9, 10, 20，同时两个指针都后移一位； - 比较9和10，不发生交换，结果是
-1, 3, 9, 10, 20，同时两个指针都后移一位；
经过第二趟，就将第二大的数排到了倒数第二位。
(3). 第三趟：
- 比较-1和3，不发生交换，结果是
-1, 3, 9, 10, 20，同时两个指针都后移一位； - 比较3和9，不发生交换，结果是
-1, 3, 9, 10, 20，同时两个指针都后移一位；
经过这一趟，就将9排到了倒数第三位。
(4). 第四趟：
- 比较-1和3，不发生交换，结果是
-1, 3, 9, 10, 20，同时两个指针都后移一位；
经过这趟，排序就结束了。
通过这个案例可以发现，总共需要进行元素个数减一次排序，并且每次比较的个数都在减少。而且，上面第二趟交换了3和-1的位置后，其实整个数组就已经是有序的了，后面的步骤都不用执行了。
3、代码实现：
public void sort(int[] arr) {
// 外层控制控制要排序几趟
int temp = 0;
for(int i=0; i<arr.length-1; i++) {
boolean flag = false; // 如果某一趟中没有一个元素发生交换，说明已经有序了，flag用来标识某一趟中是否发生过交换
// 比较arr[j]和arr[j+1]的大小，如逆序，则交换。
for(int j=0; j<arr.length-1-i; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
if (!flag) {
break;
}
}
}
四、选择排序
时间复杂度也是O(n^2)，但是经测试，选择排序速度会比冒泡排序更快。
1、排序思想：
第一趟，用arr[0]依次跟其他元素比较，如果比arr[0]更小，那就认为该数最小，记住其下标，让其他元素跟该数比较，若又更小，那些又记住新的更小的那个数的下标……第一趟完成后，就找到了最小的数，并让它与arr[0]交换位置；
第二趟，用arr[1]跟其他元素比较，重复第一趟的步骤……
2、代码实现：
public static void sort(int[] arr) {
// 外层循环控制第几趟比较
for(int i=0; i<arr.length-1; i++) {
int minNum = arr[i]; // 假定当前元素是最小的
int minNumIndex = i; // 最小值的下标
for(int j=i+1; j<arr.length; j++) {
if (arr[j] < minNum) {
// 如果arr[j]比之前认为的最小值还小，就把它当成新的最小值，并且记住下标
minNum = arr[j];
minNumIndex = j;
}
}
// 一轮下来，交换arr[i]和最小值的位置
// 如果最小值索引minIndex就等于i，那就不用交换
if (minNumIndex != i) {
arr[minNumIndex] = arr[i];
arr[i] = minNum;
}
}
}
后续会有文章介绍其他排序算法，敬请期待。
