java进阶- 经典排序(插入排序、冒泡排序、快排(分划交换排序)、直接选择排序、堆排序、合并排序)

简介: 版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/79205834 业余时间学习java,回顾回顾经典算法。
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/79205834

业余时间学习java,回顾回顾经典算法。


插入排序

插入排序的基本思想是:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。 —— [ 百度百科 ]

代码

 /**
  * 插入排序
  */
 public void insertSort(int[] array) {
        System.out.println("-----Start 插入排序-----");
        System.out.println(Arrays.toString(array));
        for (int i = 0; i < array.length; i++) {
            int j = i - 1;
            int temp = array[i];
            while (j > -1 && temp < array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            if (temp == array[i]) {
                continue;
            }
            array[j + 1] = temp;
        }
        System.out.println(Arrays.toString(array));
        System.out.println("-----End 插入排序-----");
    }

运行结果

        -----Start 插入排序-----
        [14, 21, 12, 5, 7]
        [5, 7, 12, 14, 21]
        -----End 插入排序-----

冒泡排序

冒泡排序算法的运作如下:(从后往前)
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 —— [ 百度百科 ]

代码

  /**
     * 冒泡排序(Bubble Sort)
     */
    public void bubbleSort(int[] array) {

        System.out.println("-----Start 冒泡排序-----");
        System.out.println(Arrays.toString(array));

        int temp = 0;
        for (int i = array.length - 1; i > 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (array[j + 1] < array[j]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }

        System.out.println(Arrays.toString(array));
        System.out.println("-----End 冒泡排序-----");
    }

运行结果

        -----Start 冒泡排序-----
        [5, 7, 12, 14, 21]
        [5, 7, 12, 14, 21]
        -----End 冒泡排序-----

快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 —— [ 百度百科 ]

代码

    private int count = 0;
    /**
     * 快速排序(Bubble Sort)
     * @param array
     * @param l
     * @param r
     */
    public void quickSort(int[] array, int l, int r) {
        if (l < r)
        {
            int i = l, j = r, x = array[l];
            while (i < j)
            {
                // 从右向左找第一个小于x的数
                while(i < j && array[j] >= x)
                    j--;
                if(i < j)
                    array[i++] = array[j];

                // 从左向右找第一个大于等于x的数
                while(i < j && array[i] < x)
                    i++;
                if(i < j)
                    array[j--] = array[i];
            }
            array[i] = x;
            count ++;
            System.out.println("-----第"+count+"次快速排序-----");
            System.out.println(Arrays.toString(array));
            // 递归调用
            quickSort(array, l, i - 1);
            quickSort(array, i + 1, r);
        }
    }

运行结果

        int[] outOrder = {14, 21, 12, 5, 7,9,55,77,33,12,65,6};

        运行结果:
        -----第1次快速排序-----
        [6, 12, 12, 5, 7, 9, 14, 77, 33, 55, 65, 21]
        -----第2次快速排序-----
        [5, 6, 12, 12, 7, 9, 14, 77, 33, 55, 65, 21]
        -----第3次快速排序-----
        [5, 6, 9, 7, 12, 12, 14, 77, 33, 55, 65, 21]
        -----第4次快速排序-----
        [5, 6, 7, 9, 12, 12, 14, 77, 33, 55, 65, 21]
        -----第5次快速排序-----
        [5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77]
        -----第6次快速排序-----
        [5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77]
        -----第7次快速排序-----
        [5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77]
        -----第8次快速排序-----
        [5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77]

        Process finished with exit code 0
目录
相关文章
|
2月前
|
搜索推荐 Java 索引
|
2月前
|
Java API
|
2月前
|
存储 Java
Java中ArrayList 元素的排序
本文提供了Java中根据`ArrayList`元素的某个属性进行排序的示例代码,包括实现`Comparable`接口和重载`compareTo`方法,然后使用`Collections.sort`方法进行排序。
|
2月前
|
存储 Java API
【Java高手必备】揭秘!如何优雅地对List进行排序?掌握这几种技巧,让你的代码瞬间高大上!
【8月更文挑战第23天】本文深入探讨了Java中对List集合进行排序的各种方法,包括使用Collections.sort()、自定义Comparator以及Java 8的Stream API。通过示例代码展示了不同情况下如何选择合适的方法:从简单的整数排序到自定义类对象的排序,再到利用Comparator指定特殊排序规则,最后介绍了Stream API在排序操作中的简洁应用。理解这些技术的区别与应用场景有助于提高编程效率。
23 4
|
2月前
|
存储 Java
|
2月前
|
搜索推荐 算法 Java
堆排序实战:轻松实现高效排序,附详细Java代码
嗨,大家好!我是小米,一名热爱技术分享的程序员。今天要带大家了解堆排序——一种基于二叉堆的数据结构,具有O(n log n)时间复杂度的选择排序算法。堆排序分为构建大顶堆和排序两个阶段:先建堆使根节点为最大值,再通过交换根节点与末尾节点并调整堆来逐步排序。它稳定高效,空间复杂度仅O(1),适合对稳定性要求高的场合。虽然不如快速排序快,但在避免递归和节省空间方面有优势。一起动手实现吧!如果有任何疑问,欢迎留言交流!
59 2
|
2月前
|
搜索推荐 Java
|
2月前
|
存储 Java
|
2月前
|
存储 搜索推荐 Java
|
2月前
|
Java
"Java排序大揭秘:Comparable与Comparator,究竟有何神秘区别?掌握它们,告别排序难题!"
【8月更文挑战第19天】Java提供Comparable与Comparator两种排序机制。Comparable位于`java.lang`包,定义了`compareTo()`方法以实现类的自然排序;Comparator位于`java.util`包,通过`compare()`方法提供外部定制排序。实现Comparable固定了排序策略,适用于类自带排序逻辑;使用Comparator则可在不改动类的前提下灵活定义多种排序规则,适合多样化的排序需求。选择合适机制可优化排序效率并增强代码灵活性。
10 0
下一篇
无影云桌面