《糊涂算法》之八大排序

文章8 |   阅读 732 |   点赞0

《糊涂算法》之八大排序——选择排序

x33g5p2x  于2021-09-29 转载在 其他  
字(1.6k)|赞(0)|评价(0)|浏览(127)

📚 八大排序算法合集——两万字,8张动图,450行代码。大厂面试必备。

🌲 配套源码地址:《八大排序》源码,提取码:5ehp

哈喽,大家好,我是一条~

今天给大家带来《糊涂算法》专栏的第二期内容——排序算法的讲解。相信无论是初学者学习还是大厂面试,都少不了排序算法这关,即使没学过算法,对冒泡排序也不会陌生。

今天,一条就带大家彻底跨过**「排序算法」这道坎,保姆级教程建议收藏**。⭐️

准备

古语云:“兵马未动,粮草先行”。想跟着一条一块把「排序算法」弄明白的,建议先准备好以下代码模板。

📢 观看本教程需知道基本循环语法两数交换双指针等前置知识。

📚 建议先看完代码逐步分析后再尝试自己写。

  • 新建一个Java工程,本文全篇也基于Java语言实现代码。
  • 建立如下目录结构

  • MainTest测试类中编写测试模板。
/** * 测试类 * Author:一条 * Date:2021/09/23 */
public class MainTest {
    public static void main(String[] args) {
        //待排序序列
        int[] array={6,10,4,5,2,8};
        //调用不同排序算法
				// BubbleSort.sort(array);

        // 创建有100000个随机数据的数组
        int[] costArray=new int[100000];
        for (int i = 0; i < 100000; i++) {
            // 生成一个[0,100000) 的一个数
            costArray[i] = (int) (Math.random() * 100000);
        }

        Date start = new Date();
        //过长,先注释掉逐步打印
				//BubbleSort.sort(costArray);
        Date end = new Date();
        System.out.println("耗时:"+(end.getTime()-start.getTime())/1000+"s");
    }
}

该段代码内容主要有两个功能:

  • 调用不同的排序算法进行测试
  • 测试不同排序算法将10w个数排好序需要的时间。更加具象的理解时间复杂度的不同

选择排序

基本思想

选择排序和冒泡排序很像,是从乱序序列的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。

动图讲解

代码实现

public class SelectSort {
    public static int[] sort(int[] array) {
        System.out.println("选择排序开始----------");
        for (int i = 0; i < array.length; i++) {
          //每个值只需与他后面的值进行比较,所以从开始
            for (int j = i; j < array.length; j++) {
              //注意此处是哪两个值比较
                if (array[i]>array[j]){
                    int temp=array[i];
                    array[i]=array[j];
                    array[j]=temp;
                }
            }
            System.out.println(Arrays.toString(array));
        }
        return array;
    }
}

输出结果

逐步分析

  • 初始数组:[6,10,4,5,2,8]
  • 拿出610比较,不交换 - > j++
  • 62比较,交换 - > j++
  • 注意此时是拿2继续比较,都不交换,确定第一位(最小的数)为2 - > i++
  • 循环下去,依次找到第一小,第二小,……的数
  • 最终结果 - > [2, 4, 5, 6, 8, 10]

这时再回去看动图理解。

耗时测试

时间复杂度:O(n^2)

算法优化

上诉代码中使用交换的方式找到较小值,还可以通过移动的方式,即全部比较完只交换一次。

这种对空间的占有率会有些增益,但对时间的增益几乎没有,可忽略,亦不再演示。

点击查看更多排序算法

上一篇:插入排序
下一篇:冒泡排序

相关文章