排序算法-------插入排序（直接插入排序和希尔排序）

目录

排序算法-------插入排序（直接插入排序和希尔排序）

1、直接插入排序

2、希尔排序

1、直接插入排序

        插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

1.1  算法思路

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

1.2 算法动态图解

1.3 算法分析

1.4 算法实现

**
 * 直接插入排序算法
 */
public class InsertSort {
    public void sort(int[] nums){
        if(nums == null || nums.length == 0){
            return;
        }
        int cur;
        for(int i = 0; i < nums.length -1; ++i){
            cur = nums[i +1];   //标记当前插入的数字
            int preIndex = i;   //标记可以插入的下标范围
            while(nums[preIndex] > cur){
                nums[preIndex + 1] = nums[preIndex];
                preIndex--;
            }
            nums[preIndex + 1] = cur;
        }
    }
    public static void main(String args[]){
        int[] nums = new int[]{5,69,54,21,5,36,7,84};
        InsertSort insertSort = new InsertSort();
        insertSort.sort(nums);
        for(int num : nums){
            System.out.print(num + "   ");
        }
    }
}

     运行结果：

5   5   7   21   36   54   69   84

2、希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

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

2.1 算法思路

设置一个增量，然后按照这个增量对元素进行分组，设数组长度为length，那么增量就设置为length/2,length/4.....1。然后对每个分组进行插入排序，直到增量为1，那么排序结束。例如：

2.2 算法分析

2.3 算法实现

/**
 * 希尔排序实现
 */
public class XierSort {
    public static void sort(int[] nums){
        if(nums == null || nums.length == 0)
            return;

        int len = nums.length / 2;
        int cur;
        while (len > 0){
            for(int i = len; i < nums.length; ++i){
                cur = nums[i];
                int temp = i - len;
                while (temp >= 0 && nums[temp] > cur){
                    nums[temp + len] = nums[temp];
                    temp -= len;
                }
                nums[temp + len] = cur;
            }
            len /= 2;
        }
    }
    public static void main(String args[]){
        int[] nums = new int[]{5,69,54,21,5,36,7,84};
        XierSort.sort(nums);
        for(int num : nums){
            System.out.print(num + "   ");
        }
    }
}

       运行结果：

5   5   7   21   36   54   69   84

参考：

https://www.cnblogs.com/guoyaohua/p/8600214.html

最后

以上就是糟糕书本为你收集整理的排序算法-------插入排序（直接插入排序和希尔排序）排序算法-------插入排序（直接插入排序和希尔排序）的全部内容，希望文章能够帮你解决排序算法-------插入排序（直接插入排序和希尔排序）排序算法-------插入排序（直接插入排序和希尔排序）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。