说起排序算法，可能大家会脱口而出：冒泡排序，选择排序。没错，这是我们最熟悉的两种排序算法，其实，排序算法远不止这些。而且，你之前写的冒泡、选择排序真的是最优的吗？

一、排序算法的分类

总的来说分为两大类，内部排序 和外部排序。

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;
            }
        }
}

后续会有文章介绍其他排序算法，敬请期待。