【Java面试题】Java基础——排序算法

这篇具有很好参考价值的文章主要介绍了【Java面试题】Java基础——排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

十大排序算法总览

【Java面试题】Java基础——排序算法,Java面试,排序算法,java,算法,面试题

冒泡排序★★★

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。

它重复的遍历过要排序的数列,一次比较相邻的两个元素,如果他们的顺序错误就把他们交换过来

这个算法的名字由来是因为越大的元素会经由交换慢慢"浮"到最后面。

当然,大家可以按照从大到小的方式进行排列。

算法步骤
  1. 相邻的元素两两比较,大的放右边,小的放左边
  2. 第一轮比较完毕之后,最大值就已经确定,第二轮可以少循环一次,后面以此类推
  3. 如果数组中有n个数据,总共我们只要执行n-1轮的代码就可以
动图演示

【Java面试题】Java基础——排序算法,Java面试,排序算法,java,算法,面试题

代码示例
package com.iflytek.day18;

public class A01_BubbleDemo {
    public static void main(String[] args) {
        /*
            冒泡排序:
            核心思想:
            1,相邻的元素两两比较,大的放右边,小的放左边。
            2,第一轮比较完毕之后,最大值就已经确定,第二轮可以少循环一次,后面以此类推。
            3,如果数组中有n个数据,总共我们只要执行n-1轮的代码就可以。
        */


        //1.定义数组
        int[] arr = {2, 4, 5, 3, 1};

        //2.利用冒泡排序将数组中的数据变成 1 2 3 4 5

        //外循环:表示我要执行多少轮。 如果有n个数据,那么执行n - 1 轮
        for (int i = 0; i < arr.length - 1; i++) {
            //内循环:每一轮中我如何比较数据并找到当前的最大值
            //-1:为了防止索引越界
            //-i:提高效率,每一轮执行的次数应该比上一轮少一次。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //i 依次表示数组中的每一个索引:0 1 2 3 4
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        printArr(arr);

    }

    private static void printArr(int[] arr) {
        //3.遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

选择排序

算法步骤
  1. 从0索引开始,跟后面的元素一一比较
  2. 小的放前面,大的放后面
  3. 第一次循环结束后,最小的数据已经确定
  4. 第二次循环从1索引开始以此类推
  5. 第三轮循环从2索引开始以此类推
  6. 第四轮循环从3索引开始以此类推。
动图演示

【Java面试题】Java基础——排序算法,Java面试,排序算法,java,算法,面试题

public class A02_SelectionDemo {
    public static void main(String[] args) {

        /*
            选择排序:
                1,从0索引开始,跟后面的元素一一比较。
                2,小的放前面,大的放后面。
                3,第一次循环结束后,最小的数据已经确定。
                4,第二次循环从1索引开始以此类推。

         */


        //1.定义数组
        int[] arr = {2, 4, 5, 3, 1};


        //2.利用选择排序让数组变成 1 2 3 4 5
       /* //第一轮:
        //从0索引开始,跟后面的元素一一比较。
        for (int i = 0 + 1; i < arr.length; i++) {
            //拿着0索引跟后面的数据进行比较
            if(arr[0] > arr[i]){
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
            }
        }*/

        //最终代码:
        //外循环:几轮
        //i:表示这一轮中,我拿着哪个索引上的数据跟后面的数据进行比较并交换
        for (int i = 0; i < arr.length -1; i++) {
            //内循环:每一轮我要干什么事情?
            //拿着i跟i后面的数据进行比较交换
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }


        printArr(arr);


    }
    private static void printArr(int[] arr) {
        //3.遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过创建有序序列和无序序列,然后再遍历无序序列得到里面每一个数字,把每一个数字插入到有序序列中正确的位置。

插入排序在插入的时候,有优化算法,在遍历有序序列找正确位置时,可以采取二分查找。

算法步骤

将0索引的元素到N索引的元素看做是有序的,把N+1索引的元素到最后一个当成是无序的。

遍历无序的数据,将遍历到的元素插入有序序列中适当的位置,如遇到相同数据,插在后面。

N的范围:0~最大索引

动图演示

【Java面试题】Java基础——排序算法,Java面试,排序算法,java,算法,面试题

package com.iflytek.day18;


public class A03_InsertDemo {
    public static void main(String[] args) {
        /*
            插入排序:
                将0索引的元素到N索引的元素看做是有序的,把N+1索引的元素到最后一个当成是无序的。
                遍历无序的数据,将遍历到的元素插入有序序列中适当的位置,如遇到相同数据,插在后面。
                N的范围:0~最大索引

        */
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        //1.找到无序的哪一组数组是从哪个索引开始的。  2
        int startIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > arr[i + 1]){
                startIndex = i + 1;
                break;
            }
        }

        //2.遍历从startIndex开始到最后一个元素,依次得到无序的哪一组数据中的每一个元素
        for (int i = startIndex; i < arr.length; i++) {
            //问题:如何把遍历到的数据,插入到前面有序的这一组当中

            //记录当前要插入数据的索引
            int j = i;

            while(j > 0 && arr[j] < arr[j - 1]){
                //交换位置
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }

        }
        printArr(arr);
    }

    private static void printArr(int[] arr) {
        //3.遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。

快速排序又是一种分而治之思想在排序算法上的典型应用。

快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!

它是处理大数据最快的排序算法之一了。

算法步骤
  1. 从数列中挑出一个元素,一般都是左边第一个数字,称为 “基准数”;
  2. 创建两个指针,一个从前往后走,一个从后往前走。
  3. 先执行后面的指针,找出第一个比基准数小的数字
  4. 再执行前面的指针,找出第一个比基准数大的数字
  5. 交换两个指针指向的数字
  6. 直到两个指针相遇
  7. 将基准数跟指针指向位置的数字交换位置,称之为:基准数归位。
  8. 第一轮结束之后,基准数左边的数字都是比基准数小的,基准数右边的数字都是比基准数大的。
  9. 把基准数左边看做一个序列,把基准数右边看做一个序列,按照刚刚的规则递归排序
动图演示

【Java面试题】Java基础——排序算法,Java面试,排序算法,java,算法,面试题

package com.iflytek.day18;

import java.util.Arrays;

public class A05_QuickSortDemo {
   public static void main(String[] args) {
       System.out.println(Integer.MAX_VALUE);
       System.out.println(Integer.MIN_VALUE);
     /*
       快速排序:
           第一轮:以0索引的数字为基准数,确定基准数在数组中正确的位置。
           比基准数小的全部在左边,比基准数大的全部在右边。
           后面以此类推。
     */

       int[] arr = {1,1, 6, 2, 7, 9, 3, 4, 5, 1,10, 8};


       //int[] arr = new int[1000000];

      /* Random r = new Random();
       for (int i = 0; i < arr.length; i++) {
           arr[i] = r.nextInt();
       }*/


       long start = System.currentTimeMillis();
       quickSort(arr, 0, arr.length - 1);
       long end = System.currentTimeMillis();

       System.out.println(end - start);//149

       System.out.println(Arrays.toString(arr));
       //课堂练习:
       //我们可以利用相同的办法去测试一下,选择排序,冒泡排序以及插入排序运行的效率
       //得到一个结论:快速排序真的非常快。

      /* for (int i = 0; i < arr.length; i++) {
           System.out.print(arr[i] + " ");
       }*/

   }


   /*
    *   参数一:我们要排序的数组
    *   参数二:要排序数组的起始索引
    *   参数三:要排序数组的结束索引
    * */
   public static void quickSort(int[] arr, int i, int j) {
       //定义两个变量记录要查找的范围
       int start = i;
       int end = j;

       if(start > end){
           //递归的出口
           return;
       }



       //记录基准数
       int baseNumber = arr[i];
       //利用循环找到要交换的数字
       while(start != end){
           //利用end,从后往前开始找,找比基准数小的数字
           //int[] arr = {1, 6, 2, 7, 9, 3, 4, 5, 10, 8};
           while(true){
               if(end <= start || arr[end] < baseNumber){
                   break;
               }
               end--;
           }
           System.out.println(end);
           //利用start,从前往后找,找比基准数大的数字
           while(true){
               if(end <= start || arr[start] > baseNumber){
                   break;
               }
               start++;
           }



           //把end和start指向的元素进行交换
           int temp = arr[start];
           arr[start] = arr[end];
           arr[end] = temp;
       }

       //当start和end指向了同一个元素的时候,那么上面的循环就会结束
       //表示已经找到了基准数在数组中应存入的位置
       //基准数归位
       //就是拿着这个范围中的第一个数字,跟start指向的元素进行交换
       int temp = arr[i];
       arr[i] = arr[start];
       arr[start] = temp;

       //确定6左边的范围,重复刚刚所做的事情
       quickSort(arr,i,start - 1);
       //确定6右边的范围,重复刚刚所做的事情
       quickSort(arr,start + 1,j);

   }
}

参考资料

常用十大排序算法
六大排序算法:插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序
AcWing 785. 十大排序算法总结

相关链接

6.数组、排序和查找|Java学习笔记
【算法基础】1.2 归并排序
【算法基础】1.1 快速排序
【Java】自定义排序文章来源地址https://www.toymoban.com/news/detail-520206.html

到了这里,关于【Java面试题】Java基础——排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java 与排序算法(1):冒泡排序

    冒泡排序(Bubble Sort)是一种简单的排序算法,它的基本思想是通过不断交换相邻两个元素的位置,使得较大的元素逐渐往后移动,直到最后一个元素为止。冒泡排序的时间复杂度为 O ( n 2 ) O(n^2) O ( n 2 ) ,空间复杂度为 O ( 1 ) O(1) O ( 1 ) ,是一种稳定的排序算法。 其实现过程

    2024年02月11日
    浏览(43)
  • Java玩转《啊哈算法》排序之桶排序

    过去心不可得,现在心不可得,未来心不可得 大家好!本人最近看了下《啊哈算法》,写的确实不错,生动形象又有趣( 我没收钱,确实如此 )。 但对我来说,稍显遗憾的是,书籍代码是c语言,而不是本人常用的Java。 那就弥补遗憾,说干就干,把这本书的示例语言用ja

    2024年01月25日
    浏览(43)
  • 归并排序算法(Java实现)

    也称 合并排序算法 ,是将两个或两个以上的有序数据序列合并成一个新的有序数据序列。该算法采用分治法(Divide and Conquer)的思想,将待排序的序列分成若干个子序列,分别对子序列进行排序,然后将有序的子序列合并成一个大的有序序列 注:将几个有序队列合并成一个

    2024年01月17日
    浏览(37)
  • 十大排序算法(Java实现)

    复杂度和稳定性表格一览 排序算法 平均时间 最好时间 最坏时间 空间 稳定性 冒泡 O ( n 2 ) O(n^2) O ( n 2 ) O ( n ) O(n) O ( n ) O ( n 2 ) O(n^2) O ( n 2 ) O ( 1 ) O(1) O ( 1 ) 稳定 选择 O ( n 2 ) O(n^2) O ( n 2 ) O ( n 2 ) O(n^2) O ( n 2 ) O ( n 2 ) O(n^2) O ( n 2 ) O ( 1 ) O(1) O ( 1 ) 不稳定 插入 O ( n 2 ) O(n^2) O (

    2024年02月12日
    浏览(48)
  • 算法-归并排序-JAVA

    下面是Java实现归并排序的示例代码: 在归并排序中,首先进行递归地将数组划分为更小的子数组,然后进行合并操作。在合并操作中,将两个有序的子数组合并成一个有序的数组。 上述代码实现了归并排序的主要逻辑。 mergeSort 方法用于调用归并排序的入口,它接受待排序

    2024年02月15日
    浏览(40)
  • (四)Java算法:冒泡排序

       冒泡排序 (Bubble Sort),是一种计算机科学领域的较简单的排序算法。它的工作原理是:它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果不是指定顺序(比如从小达到)就把他们交换过来。走访元素的工作是重复地进行,直到没有相邻元素需要交换,也

    2024年02月04日
    浏览(87)
  • Java | 数组排序算法

    冒泡排序的基本思想是对比相邻的元素值,如果满足条件就交换元素值,把较小的元素移到数组前面,把较大的元素移到数组后面(也就是交换两个元素的位置),这样较小的元素就像气泡一样从底部升到顶部。 直接选择排序的基本思想是将指定排序位置与其他数组元素分别

    2024年02月15日
    浏览(27)
  • Java常见的排序算法

    排序分为内部排序和外部排序(外部存储) 常见的七大排序, 这些都是内部排序 。 1、插入排序:每次将一个待排序的记录,按其 的大小插入到前面已排序好的记录序列 中的适当位置,直到全部记录插入完成为止。 稳定排序算法 一个排序算法的稳定性与不稳定性是

    2024年02月11日
    浏览(39)
  • 快速排序【Java算法】

    快速排序是一种比较高效的排序算法,采用 “分而治之” 的思想,通过多次比较和交换来实现排序,在一趟排序中把将要排序的数据分成两个独立的部分,对这两部分进行排序使得其中一部分所有数据比另一部分都要小,然后继续递归排序这两部分,最终实现所有数据有序

    2024年02月14日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包