devbox
正经夜光杯
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构各大排序整理+动图演示+代码实现（Java）_java数据结构动态演示网址

作者：正经夜光杯 | 2024-07-16 16:20:13

赞

踩

java数据结构动态演示网址
  • 注：
    以下部分动图来源于：http://www.west999.com/info/html/chengxusheji/Javajishu/20190217/4612849.html
    以下两幅图来自马士兵老师的B站公开课视频：https://www.bilibili.com/video/av46648286

目录

  • 各大排序时间复杂度及稳定性
    在这里插入图片描述
  • 马老师的宋词+rap记忆法（大家可以点击 链接 直接观看，跳到8分钟看有惊喜，hahaha）
    在这里插入图片描述
一、冒泡排序

时间复杂度：O(n2) 　　稳定性：稳定

  • 基本思想:
    冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来；
    依次比较相邻两元素，若前一元素大于后一元素则交换之，直至最后一个元素即为最大；然后重新从首元素开始重复同样的操作，直至倒数第二个元素即为次大元素；
  • 直观表达，每一趟遍历，将一个最大的数移到序列末尾。
    在这里插入图片描述
  • 代码实现
    /**
 * @ClassName: BubbleSort
 * @Description: 冒泡排序
 * @Author: liuhao
 * @Date: 2019-10-20 08:42
 * @Version: 1.0
 **/
public class BubbleSort implements MySort {

    @Override
    public int[] sort(int[] srcArr) {
        //如果小于等于一个元素就不用排序了
        if (srcArr.length < 2)
            return srcArr;
            
        // 定义排序后的数组，复制输入数组
        int[] arr = Arrays.copyOf(srcArr, srcArr.length);
        
        // 排序
        for (int i = 0; i < arr.length; i++) {
            // 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了
            boolean flag = false;
            // 此处可能会疑问j<length-i-1，因为冒泡是把每轮循环中较大的数放到后面，后面已经有序不需要在进行比较
            for (int j = 0; j < arr.length - i - 1; j++) {
                // 前面元素大虚后面元素，借助临时变量交换位置
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            // 没有数据交换，数组已经有序，退出排序
            if (!flag)
                break;
        }
        return arr;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
二、选择排序

时间复杂度：O(n2) 　　稳定性：不稳定

参考文章：https://blog.csdn.net/changhangshi/article/details/82740541

  • 工作原理：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
    在这里插入图片描述
  • 代码实现
    /**
 * @ClassName: SelectSort
 * @Description: 选择排序
 * @Author: liuhao
 * @Date: 2019-10-19 22:00
 * @Version: 1.0
 **/
public class SelectSort implements MySort {

    @Override
    public int[] sort(int[] srcArr) {
        int[] arr = Arrays.copyOf(srcArr, srcArr.length);

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            // 找出最小值得元素下标
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int tmp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = tmp;
        }
        return arr;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
三、快速排序**

时间复杂度：O(n log n) 　　稳定性：不稳定

快速排序,说白了就是给基准数据找其正确索引位置的过程，选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成

  • 算法流程：
    1．先从数列中取出一个数作为基准数。
    2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
    3．再对左右区间重复第二步，直到各区间只有一个数。
    在这里插入图片描述
  • 代码实现
    /**
 * @ClassName: QuickSort
 * @Description: 快速排序
 * @Author: liuhao
 * @Date: 2019-10-19 20:31
 * @Version: 1.0
 * 参考1: https://blog.csdn.net/nrsc272420199/article/details/82587933
 * 参考2: https://www.runoob.com/w3cnote/quick-sort.html
 **/
public class QuickSort implements MySort {
    @Override
    public int[] sort(int[] srcArr) {
        // 定义排序后的数组，复制输入数组
        int[] arr = Arrays.copyOf(srcArr, srcArr.length);
        quickSort(arr, 0, arr.length-1);
        return arr;
    }


    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getIndex(arr, low, high);
            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }
    }

    private static int getIndex(int[] arr, int low, int high) {
        // 基准数据
        int tmp = arr[low];
        while (low < high) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            // 如果队尾元素小于tmp了,需要将其赋值给low
            if (low < high) {
                arr[low] = arr[high];
                low++;
            }
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            if (low < high) {
                arr[high] = arr[low];
                high--;
            }
        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
        arr[low] = tmp;
        return low; // 返回tmp的正确位置
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
四、插入排序**

时间复杂度：O(n2) 　　稳定性：稳定

  • 插入算法把要排序的数组分成两部分：一部分为已排序部分，初始时只包含数组的第一个元素（默认有序），一部分就是未排序部分。
  • 基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序，直到待排序数据元素全部插入完为止。
    在这里插入图片描述
  • 代码实现
    /**
 * @ClassName: InsertSort
 * @Description: 插入排序
 * @Author: liuhao
 * @Date: 2019-10-21 10:22
 * @Version: 1.0
 **/
public class InsertSort implements MySort {

    @Override
    public int[] sort(int[] srcArr) {
        int[] arr = Arrays.copyOf(srcArr, srcArr.length);

        int i,j;
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (i = 1; i < arr.length; i++) {
            int temp = arr[i];

            // 移动有序数部分的元素，为新加入元素腾位置
            for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
                // 将比当前元素小的元素向右移一位
                arr[j + 1] = arr[j];
            }
//            // 或者使用while循环
//            j = i - 1;
//            while (j >= 0 && arr[j] > temp) {
//                arr[j + 1] = arr[j];
//                j--;
//            }
            arr[j+1] = temp;
        }
        return arr;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
五、归并排序**

时间复杂度：O(n log n) 　　稳定性：稳定

  • 归并排序，是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列，归并排序的比较次数小于快速排序的比较次数，移动次数一般多于快速排序的移动次数。
  • 归并排序原理
    先将无序序列中间折半，分成左右两份子序列，再分解，直到每个子序列中只剩一个元素。再依次把所有的序列进行归并（整成序列元素顺序使之有序），直到序列数为1
    在这里插入图片描述 在这里插入图片描述
    在这里插入图片描述
  • 代码实现
    /**
 * @ClassName: MergeSort
 * @Description: 归并排序
 * @Author: liuhao
 * @Date: 2019-10-21 17:15
 * @Version: 1.0
 **/
public class MergeSort implements MySort {

    @Override
    public int[] sort(int[] srcArr) {
        if (srcArr.length < 2) {
            return srcArr;
        }

        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(srcArr, srcArr.length);

        // 或者直接int middle = arr.length / 2;
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    private int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
六、堆排序**

时间复杂度：O(n log n) 　　稳定性：不稳定

参考网址：https://blog.csdn.net/qq_36186690/article/details/82505569

  • 基本思想：
    堆排序的思想借助于二叉堆中的最大堆得以实现。首先，将待排序数列抽象为二叉树，并构造出最大堆；然后，依次将最大元素（即根节点元素）与待排序数列的最后一个元素交换（即二叉树最深层最右边的叶子结点元素）；每次遍历，刷新最后一个元素的位置（自减1），直至其与首元素相交，即完成排序。
  • 核心步骤：
    1. 构建堆（大堆/小堆）
      从最后一个非终端结点开始，向前进行调整，保证当前结点及其子树符合堆特性；
    2. 输出有序序列
      交换堆顶与末尾叶子结点，堆顶输出到数组的有序序列末尾，而不参与堆的调整。从交换后的堆顶开始调整，以确保当前结点及其子树符合堆特性。
      在这里插入图片描述
  • 代码实现
    /**
 * @ClassName: HeapSort
 * @Description: 堆排序
 * @Author: liuhao
 * @Date: 2019-10-21 19:46
 * @Version: 1.0
 * <p>
 * 参考：https://blog.csdn.net/qq_36186690/article/details/82505569
 * 最后一个非叶子节点索引值：arr.length/2-1
 * 非叶子节点左子节点索引值：index*2+1
 * 非叶子节点右子节点索引值：index*2+2
 **/
public class HeapSort implements MySort {

    @Override
    public int[] sort(int[] srcArr) {
        int[] arr = Arrays.copyOf(srcArr, srcArr.length);
        //1.构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr, 0, j);//重新对堆进行调整
        }
        return arr;
    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     *
     * @param arr
     * @param i      非叶子节点所在数组中的位置
     * @param length
     */
    public void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];//先取出当前元素i
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始
            if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     */
    public void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
七、桶排序

时间复杂度：O(n + k) 　　稳定性：稳定

参考1：https://www.cnblogs.com/bqwzx/p/11029264.html
参考2：https://www.jianshu.com/p/204ed43aec0c
参考3：https://blog.csdn.net/day_and_night_2017/article/details/96475788

  • 计数排序介绍：
    首先，找出待排序列中得最大元素max，申请内存大小为max + 1的桶（数组）并初始化为0；然后，遍历排序数列，并依次将每个元素作为下标的桶元素值自增1；最后，遍历桶元素，并依次将值非0的元素下标值载入排序数列（桶元素>1表明有值大小相等的元素，此时依次将他们载入排序数列），遍历完成，排序数列便为有序数列。
  • 桶排序原理：
    ​ 桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。
  • 算法流程：
    1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；
    2. 遍历待排序集合，将每一个元素移动到对应的桶中；
    3. 对每一个桶中元素进行排序，并移动到已排序集合中。
      在这里插入图片描述
  • 代码实现
    /**
 * @ClassName: BucketSort
 * @Description: 桶排序
 * @Author: liuhao
 * @Date: 2019-10-22 17:43
 * @Version: 1.0
 * 参考1：https://www.cnblogs.com/bqwzx/p/11029264.html
 * 参考2：https://www.jianshu.com/p/204ed43aec0c
 * 参考3：https://blog.csdn.net/day_and_night_2017/article/details/96475788
 **/
public class BucketSort implements MySort {

    // 使用插入排序对桶排序
    private InsertSort insertSort = new InsertSort();

    @Override
    public int[] sort(int[] srcArr) {
        if (srcArr.length < 2) {
            return srcArr;
        }

        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(srcArr, srcArr.length);

        // 定义桶的大小
        int bucketSize = 5;

        //找出最大元素与最小元素
        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        //根据最大值与最小值，将不同大小的数分配到不同的桶中
        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            //计算该元素所属范围，放置到对应的桶里面
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     */
    private static int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
八、基数排序

时间复杂度：O(n * k) 　　稳定性：稳定

  • 原理：
    ​ 桶排序的改进版，桶的大小固定为10，每次将排序得到每一位的序列，下一次排序又在上一次排序的基础上进行，所以序列就变得有序了，即部分有序–>整体有序。
  • 算法流程：
    将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列
    基数排序法会使用到桶，顾名思义，通过将要比较的位（个位、十位、百位…），将要排序的元素分配到0~9个桶中，借以达到排序的作用，在某些时候，基数排序法的效率高于其它的比较性排序法。
    radixSort.gif
  • 代码实现
    /**
 * @ClassName: RadixSort
 * @Description: 基数排序
 * @Author: liuhao
 * @Date: 2019-10-22 16:01
 * @Version: 1.0
 * 参考连接：https://blog.csdn.net/nrsc272420199/article/details/82691596
 * 参考连接2：https://www.runoob.com/w3cnote/radix-sort.html
 **/
public class RadixSort implements MySort {

    @Override
    public int[] sort(int[] srcArr) {
        if (srcArr.length < 2) {
            return srcArr;
        }

        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(srcArr, srcArr.length);

        // 查找数组中的最大值
        int max = arr[0];
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 计算最大值的位数
        int maxDigit = 0;
        while (max > 0) {
            max /= 10;
            maxDigit++;
        }

        int length = arr.length;
        int divisor = 1;// 定义每一轮的除数，1,10,100...
        // 定义了10个桶，为了防止每一位都一样所以将每个桶的长度设为最大,与原数组大小相同
        int[][] bucket = new int[10][length];
        int[] count = new int[10];// 统计每个桶中实际存放的元素个数

        int digit;// 获取元素中对应位上的数字，即装入那个桶
        for (int i = 1; i <= maxDigit; i++) {// 经过maxDigit+1次装通操作，排序完成
            for (int temp : arr) {// 计算入桶
                digit = (temp / divisor) % 10;
                bucket[digit][count[digit]++] = temp;
            }
            int k = 0;// 被排序数组的下标
            for (int b = 0; b < 10; b++) {// 从0到9号桶按照顺序取出
                if (count[b] == 0)// 如果这个桶中没有元素放入，那么跳过
                    continue;
                for (int w = 0; w < count[b]; w++) {
                    arr[k++] = bucket[b][w];
                }
                count[b] = 0;// 桶中的元素已经全部取出，计数器归零
            }
            divisor *= 10;
        }

        return arr;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
九、希尔排序

时间复杂度：O(n1.3) 　　稳定性：不稳定

https://blog.csdn.net/qq_39207948/article/details/80006224

  • 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

  • 直接插入排序，它对于已经基本有序的数据进行排序，效率会很高，而如果对于最初的数据是倒序排列的，则每次比较都需要移动数据，导致算法效率降低。

  • 基本思想：
    为了减少数据的移动次数，在初始序列较大时取较大的步长，通常取序列长度的一半，此时只有两个元素比较，交换一次；之后步长依次减半直至步长为1，即为插入排序，由于此时序列已接近有序，故插入元素时数据移动的次数会相对较少，效率得到了提高。

  • 在希尔排序中首先要解决的是怎样划分序列，对于子序列的构成不是简单地分段，而是采取将相隔某个增量的数据组成一个序列。一般选择增量的规则是：取上一个增量的一半作为此次子序列划分的增量，一般初始值元素的总数量 n / 2。
    在这里插入图片描述

  • 代码实现
    /**
 * @ClassName: ShellSort
 * @Description: 希尔排序
 * @Author: liuhao
 * @Date: 2019-10-22 18:45
 * @Version: 1.0
 * 参考（大致了解一下）：https://blog.csdn.net/qq_39207948/article/details/80006224
 * 参考（详细参考）：https://blog.51cto.com/13733462/2114341
 **/
public class ShellSort implements MySort {

    @Override
    public int[] sort(int[] srcArr) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(srcArr, srcArr.length);

        int gap = arr.length / 2;

        while (gap > 0) {
            for (int i = step; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - step;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = tmp;
            }
            gap = (int) Math.floor(gap / 2);
        }

        return arr;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/835196
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号