尚硅谷JAVA数据结构与算法--希尔排序

一、希尔排序

也称缩小增量排序，分为交换法和移动法，移动法速度更快。

交换法：

package 希尔排序;
//交换法
import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr={7,1,4,6,8,9,5,2,3,10};
        shellsort(arr);
    }

    public static void shellsort(int[] arr){
        int temp=0;
        int count=0;
        for(int gap=arr.length/2;gap>0;gap=gap/2){
            for (int i = gap; i < arr.length; i++) {
                for(int j=i-gap;j>=0;j-=gap){
                   if(arr[j]>arr[j+gap]){
                       temp=arr[j];
                       arr[j]=arr[j+gap];
                       arr[j+gap]=temp;
                   }
                }
            }
            System.out.println("希尔排序第"+(++count)+"轮结果="+ Arrays.toString(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

移动法（速度更快）

package 希尔排序;
//移动法（相比于交换法更快）
import java.util.Arrays;

public class ShellSort2 {
    public static void main(String[] args) {
        int[] arr={7,1,4,6,8,9,5,2,3,10};
        shellsort(arr);
    }

    //对希尔排序进行优化->移动法
    public static void shellsort(int[] arr){
        int count=0;
        //缩小增量gap
        for(int gap=arr.length/2;gap>0;gap=gap/2){
            //从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j=i;//保存位置下标
                int temp=arr[j];//保存第一个找到的数组元素
                if(arr[j-gap]>arr[j]){
                    while(j-gap>=0&&temp<arr[j-gap]){
                        //不直接进行交换而是进行移动
                        arr[j]=arr[j-gap];
                        j-=gap;
                    }
                    //当退出while循环后，代表找到了temp插入的位置
                    arr[j]=temp;
                }
            }
            System.out.println("希尔排序第"+(++count)+"轮结果为"+ Arrays.toString(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

二、归并排序

package 归并排序;

import java.util.Arrays;

public class test {
    public static void main(String[] args) {
        int[] arr={8,4,5,7,1,3,6,2};
        int[] temp=new int[arr.length];
        mergesort(arr,0,arr.length-1,temp);

        System.out.println("归并排序后的结果为"+ Arrays.toString(arr));
    }

    //分+合的方法
    public static void mergesort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid=(left + right)/2;
            //向左递归进行分解
            mergesort(arr,left,mid,temp);
            //向右递归进行分解
            mergesort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }

    //合并的方法
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i=left;//初始化i，左边有序序列的初始索引
        int j=mid+1;//初始化j,右边有序序列的初始索引
        int t=0;//指向temp数组的当前索引

        //（一）
        //先把左右两边的有序序列按照规则填充到temp数组中
        //直到两边的有序序列，有一边处理完毕为止
        while(i<=mid&&j<=right){
            //如果左边的有序序列的当前元素小于右边序列的当前元素
            //则将左边的当前元素，拷贝到temp数组中
            if(arr[i]<=arr[j]){
                temp[t]=arr[i];
                t+=1;
                i+=1;
            }else{//反之，则将右边的当前元素，拷贝到temp数组中
                temp[t]=arr[j];
                t+=1;
                j+=1;
            }
        }
        //(二)
        //把有剩余数据的一边的数据依次填充到temp数组中
        while(i<=mid){//左边有剩余
             temp[t]=arr[i];
             t+=1;
             i+=1;
        }
        while(j<=right){//右边有剩余
            temp[t]=arr[j];
            t+=1;
            j+=1;
        }

        //（三）
        //将temp数组中的数据拷贝到arr
        //注意，不是每次都拷贝所有
        t=0;
        int templeft=left;
        System.out.println("templeft="+templeft+"right="+right);
        while(templeft<=right){
            //第一次合并templeft=0,right=1//tl=2,ri=3//tl=0,ri=3;
            //最后一次合并tl=0,ri=7
            arr[templeft]=temp[t];
            t+=1;
            templeft+=1;
        }
    }
}

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
74
75
76
77

三、 基数排序

package 基数排序;

import java.util.Arrays;

public class test {
    public static void main(String[] args) {
        int[] arr={53,3,542,748,14,214};
        radixSort(arr);
    }
    public static void radixSort(int[] arr){
        //1、遍历数组，得到数组中最大的元素
        int max=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>max){
                max=arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength=(max+"").length();//将数字转化成字符串，使得可以使用length方法

        //定义一个二维数组
        //说明
        //1、二维数组包含10个一维元素
        //2、为防止数据溢出，则每一个一维数组（桶），大小定为arr.length
        //3、基数排序是经典的空间换时间的算法
        int[][] bucket=new int[10][arr.length];

        //为了记录每个桶中实际放了多少个元素，我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //比如：bucketElementCounts[0],记录的就是bucket[0]桶中放入数据个数
        int[] bucketElementCounts=new int[10];

        //使用循环对代码进行处理
        for (int i = 0, n=1; i < maxLength; i++, n *= 10) {
            //针对每个元素的对应位进行排序处理，第一次是个位，第二次是十位，第三次是百位
            for (int i1 = 0; i1 < arr.length; i1++) {
                //取出每个元素的对应位的值
                int digitOfElement = arr[i1] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i1];
                bucketElementCounts[digitOfElement]++;
            }

            //按照这个桶的顺序（一维数组的下标依次取出数据，放入到原来数组中）
            int index = 0;
            //遍历每一桶，并将桶中的数据放入到原数组中
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中有数据，我们才放到原数组中
                if (bucketElementCounts[k] != 0) {
                    //循环该桶即第k个桶（即第k个一维数组）放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index] = bucket[k][l];
                        index++;//数组下标+1，然后放入第k个桶的下一个元素
                    }
                }
                //第i+1轮数据处理后，需要将每个bucketElementCounts[k]=0!!!
                bucketElementCounts[k] = 0;
            }
            System.out.println("第" +(i+1)+"轮，的排序处理是"+ Arrays.toString(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