交换式希尔排序(Java实现)

标签: 希尔排序

在之前的插入排序做了一下优化,当一个比较小的数比较靠后时,进行移动的次数必然要增多,所以使用希尔排序进行改进。

实现原理:将一个待排序的数组分成arr.length/2组,步长移动为arr.length/2,将一组内的数字比较的大小,大的放在后面,小的放在前面。进行一轮排序之后,再继续将排序后的数组分为arr.length/2/2 组,步长为arr.length/2/2,从第一个数开始移动arr.length/2/2步,进行比较,同样小的放在前面,大的放后面,依次比较,就能得到一个有序数组。

举例:定义数组 int arr[] = {8,9,1,7,2,3,5,4,6,0};
上面的数组共有10个数据,首先将他们分成10/2 = 5组,从第一个数字开始,步长为10/2步,按照这样来进行分组,分组之后就是 [8,3][9,5][1,4][7,6][2,0],再将他们分别在组内比较,比如8和3比较,3<8,将3与8的位置交换,之后的依次比较,小的放前面,大的放后面。这样一组比较完之后,得到的新数组就是[3, 5, 1, 6, 0, 8, 9, 4, 7, 2],再将得到的数组再进行分组,分成5/2=2组,从第一个数开始移动步长为2,分成的组是[3,1,0,9,7] [5,6,8,4,2]在组内分别使用,直接插入排序进行比较。经过两轮比较之后得到一个比较有序的数组。在进行最后一次比较,分成1组,从第一个开始,步长为1,进行比较,比较完毕 数组是[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

代码实现

package cn.mrlij.sort;

import java.util.Arrays;

/**
 * 交换式希尔排序
 * 实现原理:将一个待排序的数组分成arr.length/2组,步长移动为arr.length/2,将一组内的数字比较的大小,
 *          大的放在后面,小的放在前面。进行一轮排序之后,再继续将排序后的数组分为arr.length/2/2 组,
 *          步长为arr.length/2/2,从第一个数开始移动arr.length/2/2步,进行比较,同样小的放在前面,大的放后面
 *
 */
//举例:定义数组 int arr[] = {8,9,1,7,2,3,5,4,6,0};
    //上面的数组共有10个数据,首先将他们分成10/2 = 5组,从第一个数字开始,步长为10/2步,按照这样来进行分组
    //分组之后就是 [8,3][9,5][1,4][7,6][2,0],再将他们分别在组内比较,比如8和3比较,3<8,将3与8的位置交换,
    //之后的依次比较,小的放前面,大的放后面。这样一组比较完之后,得到的新数组就是[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
    //再将得到的数组再进行分组,分成5/2=2组,从第一个数开始移动步长为2,分成的组是[3,1,0,9,7] [5,6,8,4,2]在组内分别使用
    //直接插入排序进行比较。经过两轮比较之后得到一个比较有序的数组。在进行最后一次比较,分成1组,从第一个开始,步长为1,进行比较
    //比较完毕 数组是[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
public class ShellSort {
    public static void main(String[] args) {
        int arr[] = {8,9,1,7,2,3,5,4,6,0};

        for(int i = 5;i<arr.length;i++){
            for(int j = i-5;j>=0;j-=5){

               if(arr[j]>arr[j+5]){
                   int temp = arr[j];
                   arr[j] = arr[j+5];
                   arr[j+5] = temp;
               }
            }
        }
        System.out.println();
        System.out.println(Arrays.toString(arr));
        for(int i = 2;i<arr.length;i++){
            //分成两组 [3,1,0,9,7] [5,6,8,4,2]
            for(int j = i-2;j>=0;j-=2){
                if(arr[j]>arr[j+2]){
                    int temp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        for(int i = 1;i<arr.length;i++){
            //分成两组 [3,1,0,9,7] [5,6,8,4,2]
            for(int j = i-1;j>=0;j-=1){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

 

原文链接:加载失败,请重新获取