专栏首页nnngu算法01 七大排序之:冒泡排序和快速排序

算法01 七大排序之:冒泡排序和快速排序

排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列;老师查看上课出勤情况时,会按学生学号顺序点名;高考录取时,会按成绩总分降序依次录取等。排序是数据处理中经常使用的一种重要的运算,它在我们的程序开发中承担着非常重要的角色。

排序分为以下四类共七种排序方法:

交换排序:

  ① 冒泡排序    ② 快速排序

选择排序:

  ③ 直接选择排序    ④ 堆排序

插入排序:

  ⑤ 直接插入排序    ⑥ 希尔排序

合并排序:

  ⑦ 合并排序

这篇文章主要总结的是交换排序(即冒泡排序和快速排序),交换排序的基本思想是:两两比较待排序元素,如果发现两个元素的次序相反时即进行交换,直到所有元素都没有反序时为止。我会从以下几个方面进行总结:

1、冒泡排序及算法实现

2、快速排序及算法实现

3、冒泡排序VS快速排序

1、冒泡排序及算法实现

什么是冒泡排序呢?冒泡排序是一种简单的排序方法,它的基本思想是:通过相邻两个元素之间的比较和交换,使较大的元素逐渐从前面移向后面(升序),就像水底下的气泡一样逐渐向上冒泡,所以被称为“冒泡”排序。冒泡排序的最坏时间复杂度为O(n2),平均时间复杂度为O(n2)

下面以一张图来展示冒泡排序的全过程,其中方括号内为下一轮要排序的元素,方括号后面的第一个元素为本轮排序浮出来的最大元素。

1-1、示意图

1-2、代码

冒泡排序算法的代码实现:

BubbleSort.java

public class BubbleSort {
    public static void main(String[] args) {
        int[] list = {36, 28, 45, 13, 67, 37, 18, 56};
        System.out.println("************冒泡排序************");
        System.out.println("排序前:");
        display(list);

        System.out.println("排序后:");
        bubbleSort(list);
        display(list);
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }

    /**
     * 冒泡排序算法
     */
    public static void bubbleSort(int[] list) {
        int temp;
        // 做多少轮排序(最多length-1轮)
        for (int i = 0; i < list.length - 1; i++) {
            // 每一轮比较多少个
            for (int j = 0; j < list.length - 1 - i; j++) {
                if (list[j] > list[j + 1]) {
                    // 交换次序
                    temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
    }
}

测试结果:

2、快速排序及算法实现 

快速排序(Quick Sort) 是对冒泡排序的一种改进方法,在冒泡排序中,进行元素的比较和交换是在相邻元素之间进行的,元素每次交换只能移动一个位置,所以比较次数和移动次数较多,效率相对较低。而在快速排序中,元素的比较和交换是从两端向中间进行的,较大的元素一轮就能够交换到后面的位置,而较小的元素一轮就能交换到前面的位置,元素每次移动的距离较远,所以比较次数和移动次数较少,速度较快,故称为“快速排序”。

快速排序的基本思想是:通过一轮排序将待排序元素分割成独立的两部分, 其中一部分的所有元素均比另一部分的所有元素小,然后分别对这两部分的元素继续进行快速排序,以此达到整个序列变成有序序列。快速排序的最坏时间复杂度为O(n2),平均时间复杂度为O(n*log2n)   

2-1、示意图

2-2、代码

快速排序算法的代码实现:

QuickSort.java 

public class QuickSort {
    public static void main(String[] args) {
        int[] list = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        System.out.println("************快速排序************");
        System.out.println("排序前:");
        display(list);

        System.out.println("排序后:");
        quickSort(list, 0, list.length - 1);
        display(list);
    }

    /**
     * 快速排序算法
     */
    public static void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割数组,找到分割点
            int point = partition(list, left, right);

            // 递归调用,对左子数组进行快速排序
            quickSort(list, left, point - 1);
            // 递归调用,对右子数组进行快速排序
            quickSort(list, point + 1, right);
        }
    }

    /**
     * 分割数组,找到分割点
     */
    public static int partition(int[] list, int left, int right) {
        // 用数组的第一个元素作为基准数
        int first = list[left];
        while (left < right) {
            while (left < right && list[right] >= first) {
                right--;
            }
            // 交换
            swap(list, left, right);

            while (left < right && list[left] <= first) {
                left++;
            }
            // 交换
            swap(list, left, right);
        }
        // 返回分割点所在的位置
        return left;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int left, int right) {
        int temp;
        if (list != null && list.length > 0) {
            temp = list[left];
            list[left] = list[right];
            list[right] = temp;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

测试结果:

3、冒泡排序VS快速排序

代码如下:

BubbleVsQuick.java 

public class BubbleVsQuick {

    public static void main(String[] args) {
        testQuick();
        testBubble();
    }

    /**
     * 测试快速排序耗费的时间
     */
    public static void testQuick() {
        int[] list = new int[10000];
        for (int i = 0; i < 10000; i++) {
            list[i] = (int) (Math.random() * 100000);
        }

        // 快速排序
        long start = System.currentTimeMillis();
        QuickSort.quickSort(list, 0, list.length - 1);
        long end = System.currentTimeMillis();
        System.out.println("快速排序耗费的时间:" + (end - start));
        display(list);
    }

    /**
     * 测试冒泡排序耗费的时间
     */
    public static void testBubble() {
        int[] list = new int[10000];
        for (int i = 0; i < 10000; i++) {
            list[i] = (int) (Math.random() * 100000);
        }

        // 冒泡排序
        long start = System.currentTimeMillis();
        BubbleSort.bubbleSort(list);
        long end = System.currentTimeMillis();
        System.out.println("冒泡排序耗费的时间:" + (end - start));
        display(list);
    }

    /**
     * 遍历打印前10个数
     */
    public static void display(int[] list) {
        System.out.println("********排序之后的前10个数start********");
        if (list != null && list.length > 0) {
            for (int i = 0; i < 10; i++) {
                System.out.print(list[i] + " ");
            }
            System.out.println("");
        }
        System.out.println("********排序之后的前10个数end**********");
        System.out.println("");
    }
}

测试结果:

可见,快速排序的速度比冒泡排序更快。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法03 七大排序之:直接插入排序和希尔排序

    上一篇总结了直接选择排序和堆排序,这一篇要总结的是插入排序中的直接插入排序和希尔排序,我们主要从以下几点进行总结。 1、直接插入排序及算法实现 2、希尔排序及算...

    nnngu
  • 算法04 七大排序之:归并排序

    上一篇总结了直接插入排序和希尔排序,这一篇要总结的是归并排序,这也是七大排序的最后一种排序算法。 首先来看一下归并排序(Merge Sort) 的基本原理。它的...

    nnngu
  • 算法02 七大排序之:直接选择排序和堆排序

    上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。 1、直接选择排序及算法实现 2、...

    nnngu
  • 排序一 冒泡排序

    要点 冒泡排序是一种交换排序。 什么是交换排序呢? 交换排序:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止。 算法思想 它...

    静默虚空
  • 算法03 七大排序之:直接插入排序和希尔排序

    上一篇总结了直接选择排序和堆排序,这一篇要总结的是插入排序中的直接插入排序和希尔排序,我们主要从以下几点进行总结。 1、直接插入排序及算法实现 2、希尔排序及算...

    nnngu
  • 常用排序算法总结(1)

    朱晓霞
  • 排序算法:快速排序

    快速排序(Quicksort)是对冒泡排序的一种改进。 在实际中最常用的一种排序算法,速度快,效率高。

    谙忆
  • 八种排序算法

    来源:juejin.im/post/5cb6b8f551882532c334bcf2

    Java团长
  • 一种O(n)的排序——计数排序引发的围观风波

    计算机课上,老师给一串数字6 1 6 9 9 1 4 2 1 5 8 8,问道:这一串数字,你们写个程序给我看,要求效率较高。学不出来的别下课了。

    bigsai
  • 面试时写不出排序算法?看这篇就够了

    作者:静默虚空 juejin.im/post/5cb6b8f551882532c334bcf2

    好好学java

扫码关注云+社区

领取腾讯云代金券