排序算法之希尔排序及Java实现

超、凢脫俗 2022-05-26 03:59 139阅读 0赞

## 一、排序算法的分类 ##

1.  选择排序（[直接选择排序][Link 1]，[堆排序][Link 2]）
2.  交换排序（[冒泡排序][Link 3]，[快速排序][Link 4]）
3.  插入排序（[直接插入排序][Link 5]，[希尔排序][Link 6]）
4.  [归并排序][Link 7]
5.  桶式排序
6.  基数排序

## 二、希尔排序的原理 ##

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。它的主要思想是将整个序列分成多个子序列，之后依次对每个子序列进行直接插入排序，经过多次不同的子序列分割并排序后，整个数组基本有序，之后对数组中的所有元素进行一次直接插入排序。对于倒序的数组，如果采用直接插入排序的话，需要多次移动和插入操作，而采用希尔排序会大大减少移动的次数，加快了处理速度。

## 三、希尔排序的实现 ##

希尔排序的步长可以自己定义，也可以采用每次折半的方法，比如一共有12个数据，第一次步长为6进行第一轮排序，第二次步长为3进行第二轮排序，第三次步长为1进行最后一轮排序。每一次的排序都是直接排序算法。

public class ShellSort {
        
    
        public static void sheSort(int[] a){
    
            //开始时步长增量为长度的一半，之后依次减半，直到步长为1时跳出while循环
            // 12 3 6 9 23 5 8 10 34 81 37 39
            //第一轮
            // 12 3 6 9 23 5   8 10 34 81 37 39
            // 8 3 6 9 23 5 12 10 34 81 37 39
            //第二轮
            // 8 3 6  9 23 5  12 10 34  81 37 39
            // 8 3 5 9 10 6 12 23 34 81 37 39
            //第三轮
            // 3 5 6 8 9 10 12 23 34 37 39 81
            for(int incremt=a.length/2;incremt>0;incremt=incremt/2){
                System.out.println("incremt: " + incremt);
                //直接插入排序
                for(int i=incremt;i<a.length;i++)
                {
                    int tmp = a[i];
                    int j = 0;
                    for(j=i-incremt; j>=0&&tmp<a[j]; j-=incremt){
                        a[j+incremt] = a[j];
                    }
                    a[j + incremt] = tmp;
                }
                for(int k=0; k<a.length; k++){
                    System.out.print(a[k] + " ");
                }
                System.out.println();
            }
        }
        public static void main(String args[]){
            int[] test = {
       12,3,6,9,23,5,8,10,34,81,37,39};
            sheSort(test);
            System.out.println("测试结果");
            for(int i=0; i<test.length; i++){
                System.out.print(test[i] + " ");
            }
        }
    }

测试结果

incremt: 6
    8 3 6 9 23 5 12 10 34 81 37 39 
    incremt: 3
    8 3 5 9 10 6 12 23 34 81 37 39 
    incremt: 1
    3 5 6 8 9 10 12 23 34 37 39 81 
    测试结果
    3 5 6 8 9 10 12 23 34 37 39 81

[Link 1]: https://blog.csdn.net/xdzhouxin/article/details/80017538
[Link 2]: https://blog.csdn.net/xdzhouxin/article/details/80079195
[Link 3]: https://blog.csdn.net/xdzhouxin/article/details/80017719
[Link 4]: https://blog.csdn.net/xdzhouxin/article/details/80031668
[Link 5]: https://blog.csdn.net/xdzhouxin/article/details/80024190
[Link 6]: https://blog.csdn.net/xdzhouxin/article/details/80070031
[Link 7]: https://blog.csdn.net/xdzhouxin/article/details/80070839