【Java】直接插入排序 & 希尔排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【Java】直接插入排序 & 希尔排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2274字，纯文字阅读大概需要4分钟。

内容图文

1 直接插入排序

1.1 基本思想

直接插入排序是一种简单的插入排序算法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。元素集合越接近有序，直接插入排序算法的时间效率越高。

1.2 算法步骤

当插入第i（i>=1）个元素时，前面的元素arr[0]，arr[1]，... arr[i-1]已经排好序，此时比较arr[i]和arr[i-1]，arr[i-2]，... arr[0]， 找到插入位置将arr[i]插入，原来位置上的元素顺序后移（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入相等元素的后面）。

1.3 图解

1.4 代码实现

1.4.1 直接插入排序

public static void StraightInsertSort(int[] arr, int size){
        /*一次处理一个数，循环size次
                  有序[0,i-1]
                  排序 [i]
                  无序[i+1,size-1]*/
        for(int i=0; i<size; i++) {
            int key = arr[i];
            int j = 0;
            //遍历有序区间  [0,i-1]
            for (j = i-1; j >= 0; j--) {
                if (key >= arr[j]) {
                    break;
                }
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = key;
        }
    }

1.4.2 利用二分查找实现插入排序

//利用二分查找实现插入排序
    public static void InsertSortBS(int[] arr,int size){
        for(int i=0;i<size;i++) {
            int left=0;
            int right=i-1;
            int key = arr[i];
            //[left,right] 左闭右闭
            while(left<=right){
                int mid = left+(right-left)/2;
                if(arr[mid]==key){
                    left = mid+1;
                }else if(arr[mid]<key){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
            //left是要插入的位置下标
            for(int j=i;j>left;j--){
                arr[j]=arr[j-1];
            }
            arr[left] = key;
        }
    }

2 希尔排序

2.1 基本思想

先将整个待排序的记录分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行直接插入排序。

2.2 算法步骤

1）将待排序序列依据组间隔（gap）划分为若干组，对每组分别进行插入排序。

2）初始时，gap=size/3+1（或 gap=size/2），此时增量最大，因此每个分组内数据项个数相对较少，利用插入排序即可。

3）至此，完成一次排序，更新组间隔gap=gap/3+1（或 gap=gap/2），每个分组内数据项个数相对增加，但已进行依次排序，所以数据基本有序，再进行插入排序。

4）重复步骤 3）直到组间隔为1时，所有数据项在同一组内进行插入排序。至此，排序完成。

组间隔（gap）：gap初始值为size  之后不断更新为gap=gap/3+1 或  gap=gap/2

当gap>1时都是预排序，目的是让数组更接近有序。当gap==1时，数组已接近有序，这样再进行排序会很快

2.3 图解

2.4 代码实现

public static void ShellSort(int[] arr,int size){
        int gap = size;
        while(true){
            gap=gap/3+1;
            for(int i=0; i<size; i++){
                int key=arr[i];
                int j;
                for(j=i-gap;j>=0;j-=gap){
                    if(key >= arr[j]){
                        break;
                    }
                    arr[j+gap] = arr[j];
                }
                arr[j+gap] = key;
            }
            if(gap==1) {
                break;
            }
        }
    }

内容总结

以上是互联网集市为您收集整理的【Java】直接插入排序 & 希尔排序全部内容，希望文章能够帮你解决【Java】直接插入排序 & 希尔排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---