首页 > 编程语言 > 详细

[排序]直接插入排序、希尔排序

时间:2019-06-20 01:26:43      阅读:57      评论:0      收藏:0      [点我收藏+]

标签:复杂   慢慢   原来   static   --   stat   str   初始   改进   

直接插入排序

适合原本基本有序的序列。
时间复杂度O(n^2)。

代码

public class Main {
    public static void main(String args[]) {
        int[] arr= {3,5,1};
        insertSort(arr);
        for(int num:arr) {
            System.out.print(num);
        }
    }
    
    public static void insertSort(int[] arr) {
        for(int i=1;i<arr.length;++i) {
            for(int j=i-1;j>=0&&arr[j]>arr[j+1];--j) {
                swap(arr,j,j+1);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {//
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

希尔排序

  • 设置初始增量,增量慢慢变为原来的1/2,保证增量条约对应的一组组数内部有序,采用直接插入排序。
  • 是改进的插入排序,就是为了使数组基本有序:指小的基本在前面,中的基本在中间,大的基本在后面。(区分于局部有序)。这样可以大大减少交换次数。
  • 时间复杂度与增量的选取有关,平均O(nlogn)。

代码

public class Main {
    public static void main(String args[]) {
        int[] arr= {3,5,1};
        shellSort(arr);
        for(int num:arr) {
            System.out.print(num);
        }
    }
    
    public static void shellSort(int arr[]) {
        int len = arr.length;
        for(int gap=len/2; gap>=1; gap=gap/2){                  
            for(int i=gap+1; i<len; i++){
                for(int j=i-gap; j>=0&&arr[j]>arr[j+gap]; j=j-gap){        
                    swap(arr,j,j+gap);
                }
            }
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

[排序]直接插入排序、希尔排序

标签:复杂   慢慢   原来   static   --   stat   str   初始   改进   

原文:https://www.cnblogs.com/coding-gaga/p/11055949.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号