算法---java实现经典排序算法

1、基数排序

package use4;

import java.util.Arrays;

public class BasicSort {

    public static void main(String[] args) {
        int[] arrays = new int[]{53,542,3,63,14,214,154,748,616};
        System.out.println("开始");


        sort(arrays);

        System.out.println("结束");

    }

    /**
     * 1.获取原序列的最大位多少
     * @param arrays
     */
    public static void sort(int[] arrays){

        /**
         * 获取最大位数
         */
        int max = 0;
        for(int i=0;i<arrays.length;i++){
            if (arrays[i]>max){
                max = arrays[i];
            }
        }
        /**
         * 获取字符串长度，所以把int类型转字符串类型
         */
        int maxLength = (max+"").length();


        /**
         * 定义二维数组，大小10，表示10个桶，每一个桶则是一个数组
         * [[],[],[],[],[]...]
         */
        int[][] bucket = new int[10][arrays.length];

        /**
         * 辅助数组
         */
        int[] bucketElementCount = new int[10];


        /**
         * 循环获取无序数列
         */
        for (int j=0;j<arrays.length;j++){
            int locationElement = arrays[j]%10;

            /**
             * 放入桶中
             */
            bucket[locationElement][bucketElementCount[locationElement]] = arrays[j] ;
            bucketElementCount[locationElement]++;
        }

        /**
         * 遍历每一个桶，讲元素存放原数组中
         */
        int index = 0;
        for (int k = 0;k<bucketElementCount.length;k++){
            if (bucketElementCount[k] !=0){
                for (int l = 0;l<bucketElementCount[k];l++){
                    arrays[index++] = bucket[k][l];
                }
            }
            bucketElementCount[k] = 0;
        }

        System.out.println(Arrays.toString(arrays));

        /**
         * 第一轮针对个位数进行比较
         */

        for (int j = 0;j<arrays.length;j++){
            int locationElement = arrays[j]/1%10;

            bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
            bucketElementCount[locationElement]++;
        }

        /**
         * 取出来按照桶的顺序放回原数组中
         */
        int indx = 0;
        for (int k = 0;k<bucketElementCount.length;k++){
            if (bucketElementCount[k] !=0){
                for (int l=0;l<bucketElementCount[k];l++){
                    arrays[indx++] = bucket[k][l];
                }
            }
            bucketElementCount[k] = 0;
        }

        /**
         * 判断十位数
         */

        for (int j = 0;j<arrays.length;j++){
            int locationElement = arrays[j]/10%10;

            bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
            bucketElementCount[locationElement]++;
        }

        /**
         * 取出来按照桶的顺序放回原数组中
         */
        indx = 0;
        for (int k = 0;k<bucketElementCount.length;k++){
            if (bucketElementCount[k] !=0){
                for (int l=0;l<bucketElementCount[k];l++){
                    arrays[indx++] = bucket[k][l];
                }
            }
            bucketElementCount[k] = 0;
        }

        /**
         * 获取百位数比较
         */

        for (int j = 0;j<arrays.length;j++){
            int locationElement = arrays[j]/100%10;

            bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
            bucketElementCount[locationElement]++;
        }

        /**
         * 取出来按照桶的顺序放回原数组中
         */
        indx = 0;
        for (int k = 0;k<bucketElementCount.length;k++){
            if (bucketElementCount[k] !=0){
                for (int l=0;l<bucketElementCount[k];l++){
                    arrays[indx++] = bucket[k][l];
                }
            }
            bucketElementCount[k] = 0;
        }


        System.out.println("基数排序后的顺序:"+Arrays.toString(arrays));
    }

}
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

2、冒泡排序

package use4;

import java.util.Arrays;

public class BubblingSort {

    public static void main(String[] args) {

        int[] arrays = new int[]{4,5,6,3,2,1};
        /**
         * 底层for循环控制行数
         */
        for (int i=0;i<arrays.length-1;i++){
            /**
             * 控制比较次数
             */
            for(int j=0;j<arrays.length-1-i;j++){
                if (arrays[j] > arrays[j+1]){
                    int temp = 0;//类似空桶
                    temp = arrays[j]; //蓝颜色水倒入空桶
                    arrays[j] = arrays[j+1];//把橘色的水倒入原来蓝色的空桶
                    arrays[j+1] = temp;//把蓝颜色水倒入原橘色的空桶中
                }
            }
        }
        System.out.println(Arrays.toString(arrays));
    }

}
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

3、快速排序

package use4;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] arrays = new int[]{2,9,4,7,3,3,6,5};
        sort(arrays,0,arrays.length-1);
        System.out.println(Arrays.toString(arrays));
    }
    public static void sort(int[] arrays,int left,int right){
        int l  = left;
        int r = right;
        int pivot = arrays[(left+right)/2];
        int temp = 0;
        while (l<r){
            //在左边查找小于中间值的
            while(arrays[l]<pivot){
                l++;
            }
            //查询右边小于中间值
            while (arrays[r]>pivot){
                r--;
            }
            if (l>=r){
                break;
            }
            temp = arrays[l];
            arrays[l] = arrays[r];
            arrays[r] = temp;
            /**
             * 交换完数据arrays[l] = pivot
             */
            if (arrays[l]==pivot){
                r--;
            }
            if (arrays[r]==pivot){
                l++;
            }
            if (r==l){
                l++;
                r--;
            }
            if (left<r){
                sort(arrays,left,r);
            }
            if (right>l){
                sort(arrays,l,right);
            }
        }
    }
}
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

4、插入排序

package use4;

import java.util.Arrays;


public class InsertSort {

    public static void main(String[] args) {

        int[] array = new int[]{2,5,6,3,4,7,1,8};
        //控制拿去每一个元素
        for(int i=1;i<array.length;i++){
            //比较次数
            for (int j=i;j>=1;j--){
                //是否小于前面的元素
                if (array[j]<array[j-1]){
                    int temp = 0;
                    temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }else {

                    //continue 与 break

                    break;
                }
            }

        }

        System.out.println("排序后的结果："+ Arrays.toString(array));


    }

}
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

5、选择排序

package use4;

import java.util.Arrays;


public class SelectSort {

    public static void main(String[] args) {

        int[] arr = new int[]{3,2,4,5,6,8,7,1};
        for (int i=0;i<arr.length;i++){

            for (int j=arr.length-1;j>i;j--){

                if (arr[j]<arr[i]){

                    int temp = 0;
                    temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;

                }

            }


        }

        System.out.println("选择排序后的结果:"+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

6、希尔排序

package use4;

import java.lang.reflect.Array;
import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {

        int[] array = new int[]{1,5,9,7,2,6,0,3,8,4};

        /**
         * 实现增量变化
         */
        for (int gap = array.length/2;gap>0;gap/=2){

            for (int i=gap;i<array.length;i++){

                for (int j=i-gap;j>=0;j-=gap){
                        if (array[j]>array[j+gap]){
                            int temp = 0;
                            temp = array[j];
                            array[j] = array[j+gap];
                            array[j+gap] = temp;
                        }
                }
            }

        }

        System.out.println(Arrays.toString(array));

    }

}
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

7、归并排序

package use4;

import java.util.Arrays;


public class MSort {

    public static void main(String[] args) {

        int[] array = new int[]{6,9,4,7,1,2,0,5,3,8};

        //临时数组
        int[] temp = new int[array.length];

        sort(array,0,array.length-1,temp);



        System.out.println(Arrays.toString(array));

    }


    public static void sort(int[] array,int left,int right,int[] temp){
        if (left<right){
            /**
             * 求出中间值
             */
            int mid = (left+right)/2;

            /**
             * 向左边分解
             */
            sort(array,left,mid,temp);

            /**
             * 向右边分解
             */
            sort(array,mid+1,right,temp);


            /**
             * 合并数据
             */
            sum(array,left,right,mid,temp);

        }



    }

    /**
     * 合并元素
     * @param array
     * @param left
     * @param right
     * @param mid
     * @param temp
     */
    public static void sum(int[] array,int left,int right,int mid,int[] temp){

        int i = left;

        int j = mid+1;

        /**
         * 指向临时数组下标
         */
        int t = 0;

        /**
         * 开始循环比较左右两遍数组元素比较
         */
        while (i<=mid && j<=right){

            if (array[i]<=array[j]){
                temp[t] = array[i];
                t++;
                i++;
            }else {
                temp[t] = array[j];
                t++;
                j++;
            }


        }

        /**
         * 把剩余的元素直接存放在临时数组中
         */
        while(i<=mid){
            temp[t] = array[i];
            t++;
            i++;
        }

        while (j<=right){
            temp[t] = array[j];
            t++;
            j++;
        }

        /**
         * 临时数组中的元素拷贝至原数组中
         */

        int tempIndex = left;
        int k = 0;
        while (tempIndex<=right){
            array[tempIndex] = temp[k];
            k++;
            tempIndex++;
        }

    }


}
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120