面试题积累篇-简单算法（四）

向右看齐 2022-07-13 04:16 139阅读 0赞

**今天是平安夜，但是还是来看一下插入排序吧：主要是希尔排序和直接 插入排序。**

**直接插入排序思想：就是将前面的数据看做是有序的，我们将待排序的数插入到前面有序数列的正确位置，一般我们选择第一个数当做是有序的。**

**具体算法实现如下：**

package com.yang.algorithm.test;
    
    public class MergeSort {
        public static void main(String[] args) {
            int[] array = {1, 45, 20, 31, 78, 456, 123, 25, 32};
            System.out.println("排序之前：");
            for (int a : array) {
                System.out.print(a + " ");
            }
            insertSort(array);
            System.out.println("\n" + "排序之后：");
            for (int a : array) {
                System.out.print(a + " ");
            }
        }
    
        public static void insertSort(int[] array) {
            //假定第一个数有序，所以从第二个数开始排序，i从一开始 
            for (int i = 1; i < array.length; i++) {
                // 待插入元素也就是
                array[1] int temp = array[i];
                int j;
                for (j = i - 1; j >= 0; j--) {
                    // 将大于temp的往后移动一位 
                    if (array[j] > temp) {
                        array[j + 1] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + 1] = temp;
            }
        }
    }

**结果如下：**

**![Center][]**

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

**具体实现如下：**

package com.yang.algorithm.test;
    
    public class MergeSort {
        public static void main(String[] args) {
            int[] array = {1, 45, 20, 31, 78, 456, 123, 25, 32};
            System.out.println("排序之前：");
            for (int a : array) {
                System.out.print(a + " ");
            }
            shellSort(array);
            System.out.println("\n" + "排序之后：");
            for (int a : array) {
                System.out.print(a + " ");
            }
        }
    
        public static void shellSort(int[] array) {
            // 希尔排序 
            int d = array.length;
            while (true) {
                d = d / 2;
                // 分组 
                for (int x = 0; x < d; x++) {
                    // 对每组使用直接插入排序，d=1的时候其实就是直接插入排序的代码。 
                    for (int i = x + d; i < array.length; i = i + d) {
                        int temp = array[i];
                        int j;
                        for (j = i - d; j >= 0 && array[j] > temp; j = j - d) {
                            array[j + d] = array[j];
                        }
                        array[j + d] = temp;
                    }
                }
                if (d == 1) {
                    break;
                }
            }
        }
    }

**结果如下：**

**![Center][]**

[Center]: /images/20220713/d6bfe1ff65954035b4b9b58964c63aa5.png