② 、希尔排序及算法落成,② 、希尔排序及算法已毕

上一篇总计了直接采取排序和堆排序,这一篇要总计的是插入排序中的直接插入排序和希尔排序,大家任重先生而道远从以下几点举行总括。

上一篇总计了直白接纳排序和堆排序,这一篇要总计的是插入排序中的间接插入排序和希尔排序,我们主要从以下几点进行总括。

① 、直接插入排序及算法完结

一 、直接插入排序及算法达成

贰 、希尔排序及算法完结

贰 、希尔排序及算法达成

叁 、直接插入排序PK希尔排序

三 、直接插入排序PK希尔排序

 

 

一 、直接插入排序及算法完毕

什么是直接插入排序呢?直接插入排序的核心理维是:每一遍从无序体系中取出第多个要素插入到曾经排好序的雷打不动系列中,从而得到一个新的,数量加1的有序种类。

betvictor1946,1、直接插入排序及算法完结

何以是直接插入排序呢?直接插入排序的核情绪想是:每一回从无序序列中取出第一个成分插入到曾经排好序的不变系列中,从而得到三个新的,数量加1的静止系列。

1-1、示意图

下边是直接插入排序的图镇痉明。

betvictor1946 1

 

1-1、示意图

上面是直接插入排序的图宁心明。

betvictor1946 2

 

1-2、代码

下面是直接插入排序的算法完毕代码。

InsertSort.java

public class InsertSort {
    public static void main(String[] args) {
        int[] list = {90, 10, 20, 50, 70, 40, 80, 60, 30, 52};
        System.out.println("************直接插入排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        insertSort(list);
        display(list);
    }

    /**
     * 直接插入排序算法
     */
    public static void insertSort(int[] list) {
        // 从无序序列中取出第一个元素 (注意无序序列是从第二个元素开始的)
        for (int i = 1; i < list.length; i++) {
            int temp = list[i];
            int j;
            // 遍历有序序列
            // 如果有序序列中的元素比临时元素大,则将有序序列中比临时元素大的元素依次后移
            for (j = i - 1; j >= 0 && list[j] > temp; j--) {
                list[j + 1] = list[j];
            }
            // 将临时元素插入到腾出的位置中
            list[j + 1] = temp;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

 

测试结果:

betvictor1946 3

 

1-2、代码

下边是直接插入排序的算法完结代码。

InsertSort.java

public class InsertSort {
    public static void main(String[] args) {
        int[] list = {90, 10, 20, 50, 70, 40, 80, 60, 30, 52};
        System.out.println("************直接插入排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        insertSort(list);
        display(list);
    }

    /**
     * 直接插入排序算法
     */
    public static void insertSort(int[] list) {
        // 从无序序列中取出第一个元素 (注意无序序列是从第二个元素开始的)
        for (int i = 1; i < list.length; i++) {
            int temp = list[i];
            int j;
            // 遍历有序序列
            // 如果有序序列中的元素比临时元素大,则将有序序列中比临时元素大的元素依次后移
            for (j = i - 1; j >= 0 && list[j] > temp; j--) {
                list[j + 1] = list[j];
            }
            // 将临时元素插入到腾出的位置中
            list[j + 1] = temp;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

 

测试结果:

betvictor1946 4

 

二 、希尔排序及算法完成

 希尔排序是直接插入排序的一种更飞快的句酌字斟版本,又称之为“减弱增量排序”。

贰 、希尔排序及算法达成

 希尔排序是直接插入排序的一种更高速的改良版本,又称为“减少增量排序”。

2-1、示意图

 betvictor1946 5

 

2-1、示意图

 betvictor1946 6

 

2-2、代码

ShellSort.java 

public class ShellSort {
    public static void main(String[] args) {
        int[] list = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("************希尔排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        shellSort(list);
        display(list);
    }

    /**
     * 希尔排序算法
     */
    public static void shellSort(int[] list) {
        // 取增量
        int gap = list.length / 2;

        while (gap >= 1) {
            // 无序序列
            for (int i = gap; i < list.length; i++) {
                int temp = list[i];
                int j;

                // 有序序列
                for (j = i - gap; j >= 0 && list[j] > temp; j = j - gap) {
                    list[j + gap] = list[j];
                }
                list[j + gap] = temp;
            }

            // 缩小增量
            gap = gap / 2;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

 

测试结果:

betvictor1946 7

 

2-2、代码

ShellSort.java 

public class ShellSort {
    public static void main(String[] args) {
        int[] list = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("************希尔排序************");
        System.out.println("排序前:");
        display(list);
        System.out.println("");

        System.out.println("排序后:");
        shellSort(list);
        display(list);
    }

    /**
     * 希尔排序算法
     */
    public static void shellSort(int[] list) {
        // 取增量
        int gap = list.length / 2;

        while (gap >= 1) {
            // 无序序列
            for (int i = gap; i < list.length; i++) {
                int temp = list[i];
                int j;

                // 有序序列
                for (j = i - gap; j >= 0 && list[j] > temp; j = j - gap) {
                    list[j + gap] = list[j];
                }
                list[j + gap] = temp;
            }

            // 缩小增量
            gap = gap / 2;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

 

测试结果:

betvictor1946 8

 

三 、直接插入排序PK希尔排序

既然希尔排序是间接插入排序的革新版,大家就来测试一下希尔排序是不是真正比直接插入排序更快? 

代码:

InsertSortPkShellSort.java

public class InsertSortPkShellSort {
    public static void main(String[] args) {
        testInsertSort();
        testShellSort();
    }

    /**
     * 测试直接插入排序耗费的时间
     */
    public static void testInsertSort() {
        int[] list = new int[10000];
        for (int i = 0; i < 10000; i++) {
            list[i] = (int) (Math.random() * 100000);
        }

        // 直接插入排序
        long start = System.currentTimeMillis();
        InsertSort.insertSort(list);
        long end = System.currentTimeMillis();
        System.out.println("直接插入排序耗费的时间:" + (end - start));
        display(list);
    }

    /**
     * 测试希尔排序耗费的时间
     */
    public static void testShellSort() {
        int[] list = new int[10000];
        for (int i = 0; i < 10000; i++) {
            list[i] = (int) (Math.random() * 100000);
        }

        // 希尔排序
        long start = System.currentTimeMillis();
        ShellSort.shellSort(list);
        long end = System.currentTimeMillis();
        System.out.println("希尔排序耗费的时间:" + (end - start));
        display(list);
    }

    /**
     * 遍历打印前10个数
     */
    public static void display(int[] list) {
        System.out.println("********排序之后的前10个数start********");
        if (list != null && list.length > 0) {
            for (int i = 0; i < 10; i++) {
                System.out.print(list[i] + " ");
            }
            System.out.println("");
        }
        System.out.println("********排序之后的前10个数end**********");
        System.out.println("");
    }
}

 

测试结果:

betvictor1946 9

从测试结果可以见见,希尔排序比直接插入排序更快。

 

 

欢迎转发,但请保留小说原来出处

正文地址:http://www.cnblogs.com/nnngu/p/8283977.html 

 

叁 、直接插入排序PK希尔排序

既然希尔排序是直接插入排序的革新版,我们就来测试一下希尔排序是还是不是真正比直接插入排序更快? 

代码:

InsertSortPkShellSort.java

public class InsertSortPkShellSort {
    public static void main(String[] args) {
        testInsertSort();
        testShellSort();
    }

    /**
     * 测试直接插入排序耗费的时间
     */
    public static void testInsertSort() {
        int[] list = new int[10000];
        for (int i = 0; i < 10000; i++) {
            list[i] = (int) (Math.random() * 100000);
        }

        // 直接插入排序
        long start = System.currentTimeMillis();
        InsertSort.insertSort(list);
        long end = System.currentTimeMillis();
        System.out.println("直接插入排序耗费的时间:" + (end - start));
        display(list);
    }

    /**
     * 测试希尔排序耗费的时间
     */
    public static void testShellSort() {
        int[] list = new int[10000];
        for (int i = 0; i < 10000; i++) {
            list[i] = (int) (Math.random() * 100000);
        }

        // 希尔排序
        long start = System.currentTimeMillis();
        ShellSort.shellSort(list);
        long end = System.currentTimeMillis();
        System.out.println("希尔排序耗费的时间:" + (end - start));
        display(list);
    }

    /**
     * 遍历打印前10个数
     */
    public static void display(int[] list) {
        System.out.println("********排序之后的前10个数start********");
        if (list != null && list.length > 0) {
            for (int i = 0; i < 10; i++) {
                System.out.print(list[i] + " ");
            }
            System.out.println("");
        }
        System.out.println("********排序之后的前10个数end**********");
        System.out.println("");
    }
}

 

测试结果:

betvictor1946 10

从测试结果可以见见,希尔排序比直接插入排序更快。

 

 

迎接转发,但请保留小说原来出处

本文地址:http://www.cnblogs.com/nnngu/p/8283977.html