• 深入浅出排序算法之希尔排序


    目录

    1. 原理

    2. 代码实现

    3. 性能分析


    1. 原理

    希尔排序又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。

    (1)希尔排序是对直接插入排序的优化。
    (2)当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

     

    2. 代码实现

    1. //希尔排序
    2. public static void shellSort(int[] array){
    3. int gap = array.length;
    4. while(gap > 1){
    5. shell(array,gap);
    6. gap /= 2;//增量是多少都可以,随便小伙伴们写
    7. }
    8. shell(array,1);
    9. }
    10. //有增量的直接插入排序
    11. //不是一组希尔排序全部排完,是间隔性的,可能是第一组先插一个,第二组再插一个,第一组再插……
    12. private static void shell(int[] array,int gap){
    13. for(int i = gap;i < array.length;i++){
    14. int tmp = array[i];
    15. int j = i - gap;
    16. for(;j >= 0;j -= gap){
    17. if(array[j] > array[j+gap]){
    18. array[j + gap] = array[j];
    19. }
    20. else{
    21. break;
    22. }
    23. }
    24. array[j + gap] = tmp;
    25. }
    26. }
    27. public static void main(String[] args) {
    28. int[] arr = {3,1,2,4,5};
    29. Sort.shellSort(arr);
    30. for (int x : arr) {
    31. System.out.print(x + " ");
    32. }
    33. }

    3. 性能分析

    时间复杂度空间复杂度
    最好平均最坏
    O(N)O(N^1.3)O(N^2)O(1)
    数据有序难以构造出来
    1. public static void main(String[] args) {
    2. int[] arr2 = new int[10000];
    3. Test.createArray2(arr2);
    4. long s2 = System.currentTimeMillis();
    5. Sort.insertSort(arr2);
    6. long e2 = System.currentTimeMillis();
    7. System.out.println("直接插入排序的数组逆序的情况:"+(e2 - s2));
    8. int[] arr1 = new int[10000];
    9. Test.createArray2(arr1);
    10. long s1 = System.currentTimeMillis();
    11. Sort.shellSort(arr2);
    12. long e1 = System.currentTimeMillis();
    13. System.out.println("希尔排序的数组逆序的情况:"+(e1 - s1));
    14. }

    稳定性:不稳定。

    由于增量不同,可能导致本来在后面的元素跑到前面去!

  • 相关阅读:
    谈谈ORACLE应用数据同步器:Primavera Gateway (2/2)
    SQL sever中函数(2)
    AI网络爬虫:批量爬取AI导航网站Futurepedia数据
    Verilog编写VGA控制器
    去耦技术的简单分析
    git 分支重命名 使用IDEA进行操作
    CrossOver2024下载安装详细图文教程
    Harmony SDK API 版本 与 Harmony OS 版本对照表,及如何查看鸿蒙手机Harmony SDK Api 版本
    人工智能未来可期:超越人类能力的新科技
    python矩阵可视化
  • 原文地址:https://blog.csdn.net/ANNE_fly/article/details/134033699