欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-02-23 10:00:04
...

一、排序算法的分类

  1. 选择排序(直接选择排序堆排序
  2. 交换排序(冒泡排序快速排序
  3. 插入排序(直接插入排序希尔排序
  4. 归并排序
  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