您好,欢迎来到网暖!

当前位置:网暖 » 站长资讯 » 建站基础 » 网络技术 » 文章详细 订阅RssFeed

排序扯淡:冒泡、选择、插入(Java)

来源:网络整理 浏览:210次 时间:2022-11-22

算法的本质

        最近一直在想,算法的本质到底是什么,为什么有时云里雾里,有时却了然可见,深深思考了下,算法本质就是一个解决问题的思想,计算机的世界里需要的就是抽象的思想,有了抽象思想,你就有了高度,原谅我突然的。

冒泡、选择、插入排序的本质

        常见的平均时间复度为O(n²)的冒泡,选择,插入排序算法的本质是什么,说白了就是一个交换位置思想,以及什么时候交换位置,怎么交换位置。先贴一下交换位置的代码,一会要用:

public static void swap(int[] arr,int i,int j) {
   arr[i] = arr[i] + arr[j];
   arr[j] = arr[i] - arr[j];
   arr[i] = arr[i] - arr[j];
}

简单的把一个数组的两个位置的值交换一下,数组也传进来了,交换有效。

冒泡排序

        冒泡排序,就是最大的数字或最小的数字经过比较大小并交换位置后从数组中冒出来,冒到数组最左端或最右端。

        假如有一个数组:8,9,6,7,5,我们将他们冒一个泡泡,按照我们的抽象思想,开启循环,然后冒泡。第一次冒泡只要把9冒出到数组最右端,9已经是最大的泡泡了。第二次冒泡,可以直接忽略9了,只要把8冒出到数组的最右端(这里是指忽略9的情况),直到循环结束。贴一段言简意赅的代码:

public static void sort(int[] arr) {
   int length = arr.length;
   for(int i=length-1;i>0;i--) {
     for(int j=0;j<i;j++) {
       if(arr[j]>arr[j+1]) {
         swap(arr,j,j+1);
       }
     }
   }
}

        我们需要两次循环依次把最大的数从数组中冒出去,如果左边的数值大于相邻的右边的数值,就将两个位置的数值进行交换。

选择排序

        选择排序可以看作是一个冒泡排序的变种,选择排序先从数组中选择一个基准值作为最小值或最大值,然后再和剩下的数组元素逐一比较,循环找到最小的数组下标,然后交换最小值与基准位置的数值。

        还是数组:8,9,6,7,5,基准值默认选择外部循环的第一个元素,第一次选择8为基准值,这里的基准值被当作最小值对待,内部循环剩下的数组元素,经过一轮比较,不断调整最小值的下标,找到最小数值的元素下标,然后将最小值与基准值交换。贴一段言简意赅的代码,貌似和冒泡排序变化不大:

public static void sort(int[] arr) {
   int length = arr.length;
   int minIndex;
   boolean swapFlag;
   for(int i=0;i<length;i++) {
     minIndex = i;
     swapFlag = false;
     for(int j=i+1;j<length;j++) {
       if(arr[j]<arr[minIndex]) {
         minIndex = j;
         swapFlag = true;
       }
     }
     if(swapFlag) {
       swap(arr,i,minIndex);
     }
   }
 }

        选择排序每次记录下最小元素数值下标,然后与基准值交换位置,如果基准值已经是最小值,就不会再进行交换操作,交换次数明显小于冒泡排序,数据集较大时,选择排序要优于冒泡排序。

插入排序

        插入排序同样可以看作是冒泡排序的一个变种,插入排序同样选择一个基准值,一般外部循环循环的当前下标元素为基准值,插入排序就是要将基准值左边的子数组排好序,在内部循环内,从数组下标0开始到基准下标比较大小并交换位置,直到把基准位置左边子数组排好序,最终外部循环结束。

        还是数组:8,9,6,7,5,第一次选择下标1即元素9作为基准下标,然后从数组起始下标开始到基准下标开始比较对应元素数值大小,8小于9不需要交换位置,第二次选择6为基准下标,再次从数组起始下标到基准下标比较数值大小,6和8交换位置,9和8交换位置,数组变为:6,8,9,7,5。说是插入排序,其实还是保证局部排序,然后不断用外部元素与已排序子数组循环比较,将外部元素交换到排序子数组中。

public static void sort(int[] arr) {
   int length = arr.length;
   int baseIndex;
   for(int i=1;i<length;i++) {
     baseIndex = i;
     for(int j=0;j<i;j++) {
       if(arr[j]>arr[baseIndex]) {
         swap(arr,j,baseIndex);
       }
     }
   }
 }

简单排序总结

        以上三种排序算法是最简单排序,平均时间复杂度均为O(n²),因为都需要两次循环,只是交换规则略不相同,实现方式都是先将数组局部排序然后直到数组全部排序。


推荐站点

  • 腾讯腾讯

    腾讯网(www.QQ.com)是中国浏览量最大的中文门户网站,是腾讯公司推出的集新闻信息、互动社区、娱乐产品和基础服务为一体的大型综合门户网站。腾讯网服务于全球华人用户,致力成为最具传播力和互动性,权威、主流、时尚的互联网媒体平台。通过强大的实时新闻和全面深入的信息资讯服务,为中国数以亿计的互联网用户提供富有创意的网上新生活。

    www.qq.com
  • 搜狐搜狐

    搜狐网是全球最大的中文门户网站,为用户提供24小时不间断的最新资讯,及搜索、邮件等网络服务。内容包括全球热点事件、突发新闻、时事评论、热播影视剧、体育赛事、行业动态、生活服务信息,以及论坛、博客、微博、我的搜狐等互动空间。

    www.sohu.com
  • 网易网易

    网易是中国领先的互联网技术公司,为用户提供免费邮箱、游戏、搜索引擎服务,开设新闻、娱乐、体育等30多个内容频道,及博客、视频、论坛等互动交流,网聚人的力量。

    www.163.com
  • 新浪新浪

    新浪网为全球用户24小时提供全面及时的中文资讯,内容覆盖国内外突发新闻事件、体坛赛事、娱乐时尚、产业资讯、实用信息等,设有新闻、体育、娱乐、财经、科技、房产、汽车等30多个内容频道,同时开设博客、视频、论坛等自由互动交流空间。

    www.sina.com.cn
  • 百度一下百度一下

    百度一下,你就知道

    www.baidu.com