2023-09-22  阅读(164)
原文作者:李林超 原文地址: https://www.lilinchao.com/archives/536.html

一、简单插入排序存在的问题

我们看简单的插入排序可能存在的问题.

数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是:

{2,3,4,5,6,6}

{2,3,4,5,5,6}

{2,3,4,4,5,6}

{2,3,3,4,5,6}

{2,2,3,4,5,6}

{1,2,3,4,5,6}

结论 : 当需要插入的数是较小的数时,后移的次数明显增多,对效率有影响.

二、希尔排序法介绍

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种 插入排序 ,它是简单插入排序经过改进之后的一个 更高效的版本 ,也称为缩小增量排序。

三、希尔排序法基本思想

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量的逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止

四、希尔排序法的示意图

202309222130388641.png

五、希尔排序法应用实例

有一群小牛,考试成绩分别是{8,9,1,7,2,3,5,4,6,0}请从小到大排序,请分别使用

(1)希尔排序时,对有序序列在插入时采用交换法,并测试排序速度。

(2)希尔排序时,对有序序列在插入时采用移动法,并测试排序速度。

代码实现

    public class ShellSort {
        public static void main(String[] args) {
            int[] arr = {8,9,1,7,2,3,5,4,6,0};
    //        shellSort(arr);
            shellSort2(arr);
        }
    
        public static void shellSort(int[] arr){
            int temp=0;
            int count=0;
            //根据前面的逐步分析,使用循环处理
            for(int gap=arr.length/2;gap>0;gap/=2){
                for(int i=gap;i<arr.length;i++){
                    //遍历各组中所有的元素(共gap组,每组有)
                    for(int j=i-gap;j>=0;j-=gap){
                        //如果当前元素大于加上步长后的那个元素,说明交换
                        if(arr[j]>arr[j+gap]){
                            temp=arr[j];
                            arr[j]=arr[j+gap];
                            arr[j+gap]=temp;
                        }
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    
        //对交换式的希尔排序进行优化->移位法
        public static void shellSort2(int[] arr){
            //增量gap,并逐步的缩小增量
            for(int gap=arr.length/2;gap>0;gap/=2){
                //从第gap个元素,逐个对其所在的组进行直接插入排序
                for(int i=gap;i<arr.length;i++){
                    int j=i;
                    int temp=arr[j];
                    if(arr[j]<arr[j-gap]){
                        while(j-gap >=0 && temp < arr[j-gap]){
                            //移动
                            arr[j]=arr[j-gap];
                            j-=gap;
                        }
                        //当退出while后,就给temp找到插入的位置
                        arr[j]=temp;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }

全部代码

    public class BubbleSort2{
    
        public static void main(String[] args) {
    //		int arr[] = {3, 9, -1, 10, 20};
    //
    //		System.out.println("排序前");
    //		System.out.println(Arrays.toString(arr));
    
            //为了容量理解,我们把冒泡排序的演变过程,给大家展示
    
            //测试一下冒泡排序的速度O(n^2), 给80000个数据,测试
            //创建要给80000个的随机的数组
            int[] arr = new int[80000];
            for(int i =0; i < 80000;i++) {
                arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
            }
    
            Date data1 = new Date();
            SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
            String date1Str = simpleDateFormat.format(data1);
            System.out.println("排序前的时间是=" + date1Str);
    
            //测试冒泡排序
            bubbleSort(arr);
    
            Date data2 = new Date();
            String date2Str = simpleDateFormat.format(data2);
            System.out.println("排序后的时间是=" + date2Str);
    
            //System.out.println("排序后");
            //System.out.println(Arrays.toString(arr));
    
    
    		/*
    
    		// 第二趟排序,就是将第二大的数排在倒数第二位
    
    		for (int j = 0; j < arr.length - 1 - 1 ; j++) {
    			// 如果前面的数比后面的数大,则交换
    			if (arr[j] > arr[j + 1]) {
    				temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    		}
    
    		System.out.println("第二趟排序后的数组");
    		System.out.println(Arrays.toString(arr));
    
    
    		// 第三趟排序,就是将第三大的数排在倒数第三位
    
    		for (int j = 0; j < arr.length - 1 - 2; j++) {
    			// 如果前面的数比后面的数大,则交换
    			if (arr[j] > arr[j + 1]) {
    				temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    		}
    
    		System.out.println("第三趟排序后的数组");
    		System.out.println(Arrays.toString(arr));
    
    		// 第四趟排序,就是将第4大的数排在倒数第4位
    
    		for (int j = 0; j < arr.length - 1 - 3; j++) {
    			// 如果前面的数比后面的数大,则交换
    			if (arr[j] > arr[j + 1]) {
    				temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    		}
    
    		System.out.println("第四趟排序后的数组");
    		System.out.println(Arrays.toString(arr)); */
    
        }
    
        // 将前面额冒泡排序算法,封装成一个方法
        public static void bubbleSort(int[] arr) {
            // 冒泡排序 的时间复杂度 O(n^2), 自己写出
            int temp = 0; // 临时变量
            boolean flag = false; // 标识变量,表示是否进行过交换
            for (int i = 0; i < arr.length - 1; i++) {
    
                for (int j = 0; j < arr.length - 1 - i; j++) {
                    // 如果前面的数比后面的数大,则交换
                    if (arr[j] > arr[j + 1]) {
                        flag = true;
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                //System.out.println("第" + (i + 1) + "趟排序后的数组");
                //System.out.println(Arrays.toString(arr));
    
                if (!flag) { // 在一趟排序中,一次交换都没有发生过
                    break;
                } else {
                    flag = false; // 重置flag!!!, 进行下次判断
                }
            }
        }
    
    }
阅读全文
  • 点赞