你对排序算法了解多少

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

一、排序算法的分类

总的来说分为两大类,内部排序外部排序

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

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

下一篇
举报

扫码关注云+社区

领取腾讯云代金券