您好,欢迎来到站长目录(28sn.com)!


[数据结构]选择排序算法和希尔排序算法详解

来源:网络整理 浏览:158次 时间:2020-11-29

选择排序算法是经典算法之一,你可以想象你在打牌,每次拿到的一张牌就是待排序的一张,你需要每一次跟之前的牌进行比较,然后将这张牌插入到合适的位置。那么选择排序也是一样,将整个数组看成两个部分,有序部分和无序部分。现在需要将无序部分的数字跟有序部分进行比较,插入到正确的位置

下列代码是插入排序的内层循环:

while (insertIndex >= 0 && insertVal < arr[insertIndex]) {    arr[insertIndex + 1] = arr[insertIndex];    insertIndex--;}

while循环中判断用来控制当前数字是否比有序部分前一个数字小,和必须要满足有序部分的前一个索引是大于0的否则就会出现越界。循环里面进行数值的赋值。意义在于当判断成立之后,则代表当前数字是比有序部分的数字小,那么需要进行移位,即把前一个数字赋值给后一个数字,然后再将下标前移。下面放完整代码:

public static void insertSort(int[] arr) {    for (int i = 1; i < arr.length; i++) {        //需要进行插入操作的数        int insertVal = arr[i];        int insertIndex = i - 1;        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {            arr[insertIndex + 1] = arr[insertIndex];            insertIndex--;        }        arr[insertIndex + 1] = insertVal;    }}

最后来测试一下本算法在处理10w条数据的处理时间

public static void main(String[] args) {    int[] arr = new int[100000];    for (int i = 0; i < arr.length; i++) {        arr[i] = (int) (Math.random() * 8000000);    }    // System.out.println(Arrays.toString(arr));    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");    String start = sdf.format(new Date());    System.out.println(start);    insertSort(arr);    String end = sdf.format(new Date());    System.out.println(end);}

最终的运行结果为:
[数据结构]选择排序算法和希尔排序算法详解
但是选择排序算法是可以进行优化的,举个例子

{2,3,4,5,6,7,8,9,1} 像现在这组数据,如果按照传统的插入排序,最后一位数字进行判断和移位时会出现大量移位。那么为了解决这个问题就需要设置一个步长,利用步长将数组分为多个小数组进行插入排序。这样就可以将这个问题进行简化。

具体代码如下:

public static void shellSort(int[] arr) {    for (int step = arr.length / 2; step > 0; step /= 2) {        for (int i = step; i < arr.length; i++) {            int j = i;            int value = arr[i];            if (arr[j] < arr[j - step]) {                while (j - step >= 0 && value < arr[j - step]) {                    arr[j] = arr[j - step];                    j -= step;                }                arr[j] = value;            }        }    }}

代码中第一层循环是控制步长循环,这样就可以将数组分为若干个小数组,在步长为1时这时的数组就变成了一个基本有序的数组,这样再对这个数组进行排序效率明显就提升了许多。

最后来测试一下本算法在处理10w条数据的处理时间

public static void main(String[] args) {    int[] arr = new int[100000];    for (int i = 0; i < arr.length; i++) {        arr[i] = (int) (Math.random() * 8000000);    }    // System.out.println(Arrays.toString(arr));    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");    String start = sdf.format(new Date());    System.out.println(start);    shellSort(arr);    String end = sdf.format(new Date());    System.out.println(end);}

最终的运行结果为:
[数据结构]选择排序算法和希尔排序算法详解
可以很明显得看出这个算法的效率还是很高的。

推荐站点

  • 我爱发烧音乐我爱发烧音乐

    我爱发烧音乐囊括了从流行音乐到古典音乐多个类型的音乐作品,专栏推荐最新的音乐,提供音乐排名榜单!可供免费线上收听音乐,歌曲流畅,音效极佳! 网站提供的钢琴以及二胡专栏,可供收听者,陶冶情操,改善心情,是难得的轻音乐典藏!

    www.520fs.com
  • 世纪音乐网世纪音乐网

    世纪音乐网是专业的在线音乐试听MP3下载网站。歌曲总计30余万首,收录了网上最新歌曲和流行音乐,DJ舞曲,非主流音乐,经典老歌,劲舞团歌曲,搞笑歌曲,儿童歌曲,英文歌曲等。是您上网听歌的最佳网站。

    www.ssjj.com
  • 怒江大峡谷网怒江大峡谷网

    怒江大峡谷网内容包括:新闻、要闻、怒江报、视频、文化、民俗、人文、音乐、政务、公告、政策等地方信息。

    www.nujiang.cn
  • 杭州网杭州网

      杭州网是杭州地区唯一的新闻门户网站,由中共杭州市委宣传部、杭州日报报业集团和杭州广播电视集团共同组建的杭州网络传媒有限公司运营。

    www.hangzhou.com.cn
  • 深圳在线深圳在线

      深圳在线 www.szol.net是深圳本地最大、最早的地方生活资讯网站之一,网站名“深圳在线www.szol.net”由南方报业传媒集团编辑委员会总编辑、南方日报社总编辑、南方都市报总编辑、南方书画院名誉院长王春芙亲笔题名,深圳在线www.szol.net团队与深圳热线www.szonline.net、奥一网www.oeeee.com都源于全国最早成立于1996年的知名网络公司——深圳万用网。

    www.szol.net

鄂公网安备 42062502000001号