Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 1614|回复: 0

[算法学习]弄懂选择排序和希尔排序

[复制链接]
  • TA的每日心情
    开心
    2021-3-12 23:18
  • 签到天数: 2 天

    [LV.1]初来乍到

    发表于 2014-12-7 00:07:13 | 显示全部楼层 |阅读模式
    一、直接插入排序
       我们把数组分为已排序和未排序两部分,把未排序的元素一次一个插入到已排序部分的合适位置上。
    已排序部分逐渐增大,直到整个数组变成有序的。
    下面通过一个例子来说明这个排序流程:待排序列: 49, 38 , 65 , 97, 76 , 13, 27 ,49 插入49: 49  插入38: 38, 49  插入65: 38, 49, 65  插入97: 38, 49, 65, 97  插入76: 38, 49, 65, 76, 97  插入13: 13, 38, 49, 65, 76, 97  插入27: 13, 27, 38, 49, 65, 76, 97  插入49: 13, 27, 38, 49, 49, 65, 76, 97
      二、希尔排序
        基本思想:希尔排序把n个元素按一定的间隔分成几组,然后按组为单位进行插入排序。 。     将待排记录序列以一定的增量间隔h 分割成多个子序列,对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长h ,对于每一个步长h 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体插入排序。

       因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组步长h下每个子序列的规模都不大,用直接插入排序效率都较高。 尽管在随后的步长h递减分组中子序列越来越大,但由于整个序列的有序性也越来越明显,则排序效率依然较高。这种改进抓住了直接插入排序的两点本质,大大提高了它的时间效率。

    希尔算法的本质是缩小增量排序,是对直接插入排序算法的改进。
       
    程序的增量序列常采用的表达式:
    (1)h=3*h+1。(h=1,4,13,40,121,364...)
    (2)h=2^k-1。(h=1,3,7,15,31,63...

    例:待排序列:5,9,1,4,8,2,6,3,7


    1. import java.util.Arrays;   
    2. import java.util.Random;   
    3. public class SortTest{  
    4. /**  
    5.      * 交换数组中的两个元素的位置  
    6.      * @param array 待交换的数组  
    7.      * @param i 第一个元素  
    8.      * @param j 第二个元素  
    9.      */  
    10.     private void swap(int[] array, int i, int j) {   
    11.         if (i != j) {//只有不是同一位置时才需交换   
    12.             int  tmp = array[i];   
    13.             array[i] = array[j];   
    14.             array[j] = tmp;   
    15.         }   
    16.     }   
    17.   
    18.     /**  
    19.      * 数组元素后移  
    20.      * @param array 待移动的数组  
    21.      * @param startIndex 从哪个开始移  
    22.      * @param endIndex 到哪个元素止  
    23.      */  
    24.     private  void move(int[] array, int startIndex, int endIndex) {   
    25.         for (int i = endIndex; i >= startIndex; i--) {   
    26.             array[i + 1] = array[i];   
    27.         }   
    28.     }   
    29.   
    30.     /**  
    31.      * 以指定的步长将数组元素后移,步长指定每个元素间的间隔  
    32.      * @param array 待排序数组  
    33.      * @param startIndex 从哪里开始移  
    34.      * @param endIndex 到哪个元素止  
    35.      * @param step 步长  
    36.      */  
    37.     private void move(int[] array, int startIndex, int endIndex, int step) {   
    38.         for (int i = endIndex; i >= startIndex; i -= step) {   
    39.             array[i + step] = array[i];   
    40.         }   
    41.     }   
    42.    //生成随机数组   
    43.     @SuppressWarnings("unchecked")   
    44.     public   int[] randomArray() {   
    45.         Random r = new Random(System.currentTimeMillis());   
    46.         int[] a = new int[r.nextInt(30)];   
    47.         for (int i = 0; i < a.length; i++) {   
    48.             a[i] = r.nextInt(100);   
    49.         }   
    50.         return  a;   
    51.     }   
    52.    
    53.     /**  
    54.      *         插入排序算法的实现,对数组中指定的元素进行排序  
    55.      * @param array 待排序的数组  
    56.      * @param from 从哪里开始排序  
    57.      * @param end 排到哪里  
    58.      * @param c 比较器  
    59.      */  
    60.     public void insertSort(int[] array) {  //升序排列
    61.   
    62.         /*  
    63.          * 第一层循环:对待插入(排序)的元素进行循环  
    64.          * 从待排序数组断的第二个元素开始循环,到最后一个元素(包括)止  
    65.          */  
    66.         for (int i =1; i < array.length; i++) {   
    67.             /*  
    68.              * 第二层循环:对有序数组进行循环,且从有序数组最第一个元素开始向后循环  
    69.              * 找到第一个大于待插入的元素  
    70.              * 有序数组初始元素只有一个,且为源数组的第一个元素,一个元素数组总是有序的  
    71.              */  
    72.             for (int j = 0; j < i; j++) {   
    73.                 int insertedElem = array[i];//待插入到有序数组的元素   
    74.                 //从有序数组中最一个元素开始查找第一个大于待插入的元素   
    75.                 if (array[j]>insertedElem) {   
    76.                     //找到插入点后,从插入点开始向后所有元素后移一位   
    77.                     move(array, j, i - 1);   
    78.                     //将待排序元素插入到有序数组中   
    79.                     array[j] = insertedElem;   
    80.                     break;   
    81.                 }   
    82.             }   
    83.         }   
    84.      }
    85.    /**  
    86.      * 希尔排序算法的实现,对数组中指定的元素进行排序  
    87.      * @param array 待排序的数组  
    88.      */  
    89.     public void shelltSort(int[] array) {   //升序排列
    90.         //初始步长,实质为每轮的分组数   
    91.         int step = initStep(array.length);   
    92.   
    93.         //第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值   
    94.         for (; step >= 1; step = (step + 1) / 2 - 1) {   
    95.             //对每轮里的每个分组进行循环   
    96.             for (int groupIndex = 0; groupIndex < step; groupIndex++) {   
    97.   
    98.                 //对每组进行直接插入排序   
    99.                 insertSort(array, groupIndex, step);   
    100.             }   
    101.         }   
    102.     }   
    103.   /**  
    104.      * 直接插入排序实现  
    105.      * @param array 待排序数组  
    106.      * @param groupIndex 对每轮的哪一组进行排序  
    107.      * @param step 步长  
    108.      * @param end 整个数组要排哪个元素止  
    109.      * @param c 比较器  
    110.      */  
    111.     private void insertSort(int[] array, int groupIndex, int step) {   
    112.         int startIndex = groupIndex;//从哪里开始排序   
    113.         int endIndex = startIndex;//排到哪里   
    114.         /*  
    115.          * 排到哪里需要计算得到,从开始排序元素开始,以step步长,可求得下元素是否在数组范围内,  
    116.          * 如果在数组范围内,则继续循环,直到索引超现数组范围  
    117.          */  
    118.        while ((endIndex + step) <= array.length-1) {   
    119.             endIndex += step;   
    120.         }   
    121.   
    122.         // i为每小组里的第二个元素开始   
    123.         for (int i = groupIndex + step; i <= endIndex; i += step) {   
    124.             for (int j = groupIndex; j < i; j += step) {   
    125.                 int insertedElem = array[i];   
    126.                 //从有序数组中最一个元素开始查找第一个大于待插入的元素   
    127.                 if (array[j]>insertedElem) {   
    128.                     //找到插入点后,从插入点开始向后所有元素后移step位   
    129.                     move(array, j, i - step, step);   
    130.                     array[j] = insertedElem;   
    131.                     break;   
    132.                 }   
    133.             }   
    134.         }   
    135.     }   
    136.     private static int initStep(int len) {   //从最小步长1推导出最长初始步长值
    137.         /*  
    138.          * 初始值设置为步长公式中的最小步长,从最小步长推导出最长初始步长值,即按照以下公式来推:  
    139.          * 1,3,7,15,...,2^(k-1)-1,2^k-1  
    140.          * 如果数组长度小于等于4时,步长为1,即长度小于等于4的数组不且分组,此时直接退化为直接插  
    141.          * 入排序  
    142.          */  
    143.         int step = 1;   
    144.   
    145.         //试探下一个步长是否满足条件,如果满足条件,则步长置为下一步长   
    146.         while ((step + 1) * 2 - 1 < len - 1) {   
    147.             step = (step + 1) * 2 - 1;   
    148.         }   
    149.   
    150.         System.out.println("初始步长 : " + step);   
    151.         return step;   
    152.     }   
    153.       /**  
    154.        * 测试  
    155.      * @param args  
    156.      */  
    157.     public static void main(String[] args) {   
    158.         int[] intArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 };  
    159.         System.out.println("源 : " + Arrays.toString(intArr));   
    160.         SortTest test=new SortTest();   
    161.         //test.insertSort(intArr);
    162.        test.shelltSort(intArr);
    163.        System.out.println("升 : " + Arrays.toString(intArr));   
    164.       
    165.      
    166.      }
    167.     }   
    复制代码
    运行结果:
    D:java>java SortTest
    源 : [5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7]
    初始步长 : 7
    升 : [0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9]


       
         
         
          
          

            
          

            
          
         
       

      


    源码下载:http://file.javaxxz.com/2014/12/7/000712968.zip
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2024-3-29 20:19 , Processed in 0.314419 second(s), 38 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表