12、数据结构与算法 - 实战:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)

前言

  • 上节的三个排序算法:冒泡、选择、插入,较为简单,好理解,使用比较、交换的思想。但也都是基础。
  • 这节的三个排序算法:希尔、快速【看注释比较容易理解思路】、归并,难理解,使用递归的思想。
  • 这三个是难点,但也是重点。加油

一、希尔排序

1.1 简单插入排序存在的问题

我们看简单的插入排序可能存在的问题.
数组arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是:
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}

结论: 当需要插入的数是较小的数时,后移的次数明显增多,对效率有影响.

1.2 基本介绍

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是 简单插入排序 经过改进之后的一个更高效的版本,也称为 缩小增量排序

1.3 思路分析

1.3.1希尔排序法基本思想

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

1.3.2希尔排序法示意图

 
 

1.4 代码实现

有一群小牛, 考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用

1、 希尔排序时,对有序序列在插入时采用**交换法,并测试排序速度,相对较慢(容易理解);
2、 希尔排序时,对有序序列在插入时采用
移动法**,并测试排序速度,相对较快(不易理解);

package com.feng.ch09_sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 希尔排序:
 *      对插入排序的 进一步优化
 * 使用到了 分组,并且缩小增量的 思想。
 *      第一次分组,gap(分组的次数)=【数组大小】/2,
 *      第二次分组,gap = (第一次分组次数)/2,
 *      第三次分组,gap = (上一次分组次数)/2,
 *
 * 有两种方式:
 * 第一种:交换式
 *      里面使用了冒泡排序的 交换思想
 *      效率低,容易理解  80000数据排序使用 14-19 S
 *
 * 第二种:移位式
 *      里面使用了 简单插入排序的 插入移位思想
 *      效率高,不易理解  8万数据: 1S , 80万数据:  1S, 800万数据:4S
 * */
public class S4_ShellSort {
   
     
    public static void main(String[] args) {
   
     
        int[] array = {
   
     8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("初始数组:");
        System.out.println(Arrays.toString(array));

        System.out.println();
        System.out.println("排序后");
//        deductionShellSortBychange(array);
        int[] ints = shellSortByChange(array); // 交换式
        System.out.println(Arrays.toString(ints));
        // 测试 80000 个数据排序 所用的时间
        System.out.println();
        System.out.println("测试 80000 个数据 采用希尔排序(交换式) 所用的时间:");
        testTime();   // 交互式:19S, 移位式:1S
    }

    /*
     * 测试一下 希尔排序的速度O(n^2), 给 80000 个数据,测试一下
     * */
    public static void testTime() {
   
     
        // 创建一个 80000个的随机的数组
        int array2[] = new int[80000];
        for (int i = 0; i < 80000; i++) {
   
     
            array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
        }
//        System.out.println(Arrays.toString(array2)); // 不在打印,耗费时间太长
        long start = System.currentTimeMillis();  //返回以毫秒为单位的当前时间
        System.out.println("long start:" + start);
        Date date = new Date(start); // 上面的也可以不要,但是我想测试
        System.out.println("date:" + date);
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
        System.out.println("排序前的时间是=" + format.format(date));

        shellSortByChange(array2); // 交互式
//        shellSortByMove(array2);   // 移位式

        System.out.println();
        long end = System.currentTimeMillis();
        Date date2 = new Date(end); // 上面的也可以不要,但是我想测试
        System.out.println("排序后的时间是=" + format.format(date2));
        System.out.println("共耗时" + (end - start) + "毫秒");
        System.out.println("毫秒转成秒为:" + ((end - start) / 1000) + "秒");
    }

    /*
     * 对交换式的希尔排序进行优化 -》》移位法
     * */
    public static int[] shellSortByMove(int[] array) {
   
     
        // 增量gap, 并逐步的缩小增量
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
   
      // 共分 3 组
            // 从第 gap 个元素,逐个对其所在的组进行直接插入排序
            for (int i = gap; i < array.length; i++) {
   
     
                // 这里使用了 前面学习的 直接插入排序
                int j = i;
                int temp = array[j];
                if (array[j] < array[j - gap]) {
   
     
                    while ((j - gap) >= 0 && temp < array[j - gap]) {
   
     
                        //移动
                        array[j] = array[j - gap];
                        j -= gap;
                    }
                    //当退出while后,就给temp找到插入的位置
                    array[j] = temp;
                }
            }
        }
        return array;
    }

    /*
     * 交换式排序 整合
     * */
    public static int[] shellSortByChange(int[] array) {
   
     
        int temporary = 0;
        int count = 0;
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
   
       // 三次分组。
            for (int i = gap; i < array.length; i++) {
   
         // 有几组,循环遍历几次,也就比较几次。
                // 遍历各组中所有的元素(共 gap 组,每组有  个元素),步长为 gap
                // 这里使用了交换:也就是前面学习的 冒泡排序的思想
                for (int j = i - gap; j >= 0; j -= gap) {
   
     
                    if (array[j] > array[j + gap]) {
   
     
                        temporary = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temporary;
                    }
                }
            }
//            System.out.println("希尔排序第" + (++count) + "轮=" + Arrays.toString(array));
        }
        return array;
    }

    /*
     * 希尔排序:采用交换式
     * 使用逐步推导的方式
     * */
    public static int[] deductionShellSortBychange(int[] array) {
   
     
        // 临时变量,存放交换的数据
        int temporary = 0;

        /*
         * 希尔排序的第 1 轮排序
         * */
        System.out.println("第 1 轮排序");
        // 因为第 1 轮排序,是将 10 个数据分成了5组 ,所以要比较 5 次, i 从 5 开始
        for (int i = 5; i < array.length; i++) {
   
      // 共遍历 5 次,即 比较 5 次
            // 遍历各组中所有的元素(共 5 组,每组有2个元素),步长为 5
            for (int j = i - 5; j >= 0; j -= 5) {
   
       // 仅比较一次,走一次逻辑,就知道啦
                if (array[j] > array[j + 5]) {
   
     
                    temporary = array[j];
                    array[j] = array[j + 5];
                    array[j + 5] = temporary;
                }
            }
        }
        System.out.println(Arrays.toString(array));

        /*
         * 希尔排序的第 2 轮排序
         * */
        System.out.println("第 2 轮排序");
        // 因为第 1 轮排序,是将 10 个数据分成了  5/2 = 2组
        for (int i = 2; i < array.length; i++) {
   
     
            // 遍历各组中所有的元素(共 5 组,每组有2个元素),步长为 5
            for (int j = i - 2; j >= 0; j -= 2) {
   
     
                if (array[j] > array[j + 2]) {
   
     
                    temporary = array[j];
                    array[j] = array[j + 2];
                    array[j + 2] = temporary;
                }
            }
        }
        System.out.println(Arrays.toString(array));

        /*
         * 希尔排序的第 3 轮排序
         * */
        System.out.println("第 3 轮排序");
        // 因为第 3 轮排序,是将 10 个数据分成了  2/2 = 1组
        for (int i = 1; i < array.length; i++) {
   
     
            // 遍历各组中所有的元素(共 5 组,每组有2个元素),步长为 5
            for (int j = i - 1; j >= 0; j -= 1) {
   
     
                if (array[j] > array[j + 1]) {
   
     
                    temporary = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temporary;
                }
            }
        }
        System.out.println(Arrays.toString(array));

        return array;
    }
}

1.5 测试结果

 

二、快速排序

2.1 基本介绍

快速排序(Quicksort)是对冒泡排序的一种改进。
基本思想是 :通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再 按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行 ,以此达到整个数据变成有序序列

2.2 思路分析

1、 先把数组中的一个数当做基准数,一般会把数组中最左边的数当做基准数;
2、 然后从两边进行检索,先从右边往左检索比基准数小的,再从左边往右检索比基准数大的
3、 如果检索到了,就停下,交换这两个元素然后继续检索;
4、 如果这两个索引指针相遇了,就退出循环
5、 将基准数与这两个索引遇到的数字进行对换;
6、 基准数在这里就归位了,左边的数字都比基准数小,右边的数字都比基准数大;
7、 然后使用递归进行排序

2.3 代码实现

package com.feng.ch09_sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 快速排序:
 *       对冒泡排序的优化
 *
 * 时间复杂度:O(nlog2n)
 * 速度测试 : 8万数据: 1S不到, 80万数据: 1S 不到, 800万数据:1S不到 ,速度超级快
 * */
public class S5_QuickSort {
   
     

    public static void main(String[] args) {
   
     
        int[] array = {
   
     -9, 78, 0, 23, -567, 70, -1, 900, 4561};
        System.out.println("初始数组:");
        System.out.println(Arrays.toString(array));

        System.out.println();
        System.out.println("排序后:");
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));

        // 测试 80000 个数据排序 所用的时间
        System.out.println();
        System.out.println("测试 80000 个数据 采用快速排序(交换式) 所用的时间:");
        testTime();   // 8万数据: 1S不到, 80万数据: 1S 不到, 800万数据:2-3
    }

    /*
     * 测试一下 快速排序的速度, 给 80000 个数据,测试一下
     * */
    public static void testTime() {
   
     
        // 创建一个 80000个的随机的数组
        int array2[] = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
   
     
            array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
        }
//        System.out.println(Arrays.toString(array2)); // 不在打印,耗费时间太长
        long start = System.currentTimeMillis();  //返回以毫秒为单位的当前时间
        System.out.println("long start:" + start);
        Date date = new Date(start); // 上面的也可以不要,但是我想测试
        System.out.println("date:" + date);
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
        System.out.println("排序前的时间是=" + format.format(date));

        quickSort(array2, 0, array2.length - 1);   // 移位式

        System.out.println();
        long end = System.currentTimeMillis();
        Date date2 = new Date(end); // 上面的也可以不要,但是我想测试
        System.out.println("排序后的时间是=" + format.format(date2));
        System.out.println("共耗时" + (end - start) + "毫秒");
        System.out.println("毫秒转成秒为:" + ((end - start) / 1000) + "秒");
    }

    /*
     * 快速排序方法:通俗异同,直接看注释即可
     *
     * @param array 需要排序的数组
     * @param left  最左边的下标,也是索引
     * @param right 最右边的下标,也是索引
     * */
    public static void quickSort(int[] array, int left, int right) {
   
     
        // 进行判断,如果左边索引比右边索引要大,是不合法的,直接使用return 结束这个方法
        if (right < left) {
   
     
            return;
        }

        // 定义变量保存基准数,这里的基准数用最左边的数来代替。
        int base = array[left];
        // 定义变量 i ,指向最左边
        int i = left;
        // 定义变量 j, 指向最右边
        int j = right;

        // 当 i 和 j 不相遇的时候,就在循环中进行检索。
        while (i != j) {
   
     
            // 先 由j 从右往左检索比基准数小的,如果检索到比基准数小的就停下
            // 如果检索比基准数大的或者相等的,就继续检索
            while (array[j] >= base && i<j) {
   
     
                j--; // j 从右往左移动
            }
            // i 从左往右检索。找比基准数 大的,
            while (array[i] <= base && i<j) {
   
     
                i++;// i 从左往右移动
            }

            // 如果代码走到这儿,i 和 j 都停下了,。然后交换 i 和 j 位置的元素
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        /*
        * 如果上面的 while 循环条件不成立了,会跳出这个循环,往下执行。
        * 如果这个条件不成立 说明 i 和 j 相遇了,也就是相等
        * 如果 i 和 j 相遇了,就交换基准数这个元素 和相遇位置的元素。
        * 把 相遇位置的元素 赋值 给基准数这个位置的元素
        * */
        array[left] = array[i];
        // 把基准数赋值给相遇位置的元素
        array[i] = base;

        // 基准数在这里就归位了,左边的数字都比基准数小,右边的数字都比基准数大。
        // 对基准数的 左边进行排序
        quickSort(array, left, i-1);

        // 排右边
        quickSort(array, j+1, right);
    }
}

2.4 测试结果

 

三、归并排序

3.1 基本介绍

归并排序(MERGE-SORT)是利用 归并 的思想实现的排序方法,该算法采用经典的**分治**(divide-and-conquer)策略(分治法将问题 (divide)成一些小的问题然后递归求解,而 (conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

3.2 思路分析

说明:
可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程。

 

3.3 代码实现

package com.feng.ch09_sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 归并排序
 *
 * 速度测试: 8万数据: 117Ms, 80万数据: 395Ms, 800万数据:2-3S
 * */
public class S6_MergetSort {
   
     

    public static void main(String[] args) {
   
     
        int[] array = {
   
     8, 4, 5, 7, 1, 3, 6, 2};  // 8-> merge 7次, 80000-> merge 80000-1=7999次

        int[] temp = new int[array.length];
        System.out.println("原始数组:");
        System.out.println(Arrays.toString(array));

        System.out.println();
        System.out.println("排序后:");
        mergetSort(array,0, array.length-1, temp);
        System.out.println(Arrays.toString(array));

        // 测试 80000 个数据排序 所用的时间
        System.out.println();
        System.out.println("测试 80000 个数据 采用归并排序(交换式) 所用的时间:");
        testTime();   // 8万数据: 1S不到, 80万数据: 1S 不到, 800万数据:2-3
    }

    /*
     * 测试一下 归并排序的速度, 给 80000 个数据,测试一下
     * */
    public static void testTime() {
   
     
        // 创建一个 80000个的随机的数组
        int array2[] = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
   
     
            array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
        }
//        System.out.println(Arrays.toString(array2)); // 不在打印,耗费时间太长
        long start = System.currentTimeMillis();  //返回以毫秒为单位的当前时间
        System.out.println("long start:" + start);
        Date date = new Date(start); // 上面的也可以不要,但是我想测试
        System.out.println("date:" + date);
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
        System.out.println("排序前的时间是=" + format.format(date));

        int[] temp = new int[array2.length];
        mergetSort(array2,0, array2.length-1, temp);   // 移位式

        System.out.println();
        long end = System.currentTimeMillis();
        Date date2 = new Date(end); // 上面的也可以不要,但是我想测试
        System.out.println("排序后的时间是=" + format.format(date2));
        System.out.println("共耗时" + (end - start) + "毫秒");
        System.out.println("毫秒转成秒为:" + ((end - start) / 1000) + "秒");
    }
    /*
     * 分 + 合的方法
     * */
    public static void mergetSort(int[] array, int left, int right, int[] temp) {
   
     
        if (left < right) {
   
     // 数据校验
            int mid = (left + right) / 2; // 中间索引
            // 向左递归 分解
            mergetSort(array, left, mid, temp);
            // 向右递归 分解
            mergetSort(array, mid + 1, right, temp);
            // 以上为分解
            // 以下这一句为合并
            merge(array, left, mid, right, temp);

        }
    }
    /*
     * 合并的方法
     *
     * @param array 排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     * */
    public static void merge(int[] array, int left, int mid, int right, int[] temp) {
   
     
//        System.out.println("XXXX");
        int i = left; // 初始化 i, 左边有序序列的初始索引
        int j = mid + 1; // 初始化j, 右边有序序列的初始索引
        int t = 0; // 指向 temp 数组的 当前索引。

        // (一)
        // 先把左右两边(有序)的数据按照规则填充到 temp数组
        // 直到 左右两边的有序序列,有一边处理完毕为止
        while (i <= mid && j <= right) {
   
     
            /*
             * 如果 左边的有序序列 的当前元素,小于等于右边有序序列的 当前元素
             * 既然左边的当前元素,填充到 temp 数组
             * 然后 t++, i++
             * */
            if (array[i] <= array[j]) {
   
     
                temp[t] = array[i];
                t += 1;
                i += 1;
            } else {
   
     
                // 如果 右边的有序序列的当前元素 小于 左边有序序列的当前元素,则将右边的当前元素填充到 temp数组,然后 t++, j++
                temp[t] = array[j];
                t += 1;
                j += 1;
            }
        }

        /*
         * (二)
         * 当代码走到这里,说明 左边 或者 右边 ,已经有一方 有剩余的。
         * 把有 剩余数据 的一边的数据 依次全部填充到 temp
         * */
        // 左边 有序序列还有剩余的元素,就全部填充到 temp
        while (i <= mid) {
   
     
            temp[t] = array[i];
            t++;
            i++;
        }
        // 右边 有序序列还有剩余的元素,就全部填充到 temp
        while (j <= right) {
   
     
            temp[t] = array[j];
            t++;
            j++;
        }

        /*
         * (三)
         * 将 temp 数组的元素拷贝到 array
         * 注意,并不是每次都拷贝所有
         * */
        t = 0;
        int tempLeft = left;//
        // 第一次 合并: tempLeft = 0, right = 1, // tempLeft = 2, right = 3 // tempLeft = 0, right = 3
        // 最后一次,tempLeft = 0  right = 7
//        System.out.println("tempLeft=" + tempLeft + ",right=" + right);
        while (tempLeft <= right) {
   
     
            array[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }

    }
}

3.4 测试结果