快排、递归、堆和基数四种排序方法

发表于   |   分类于   |  

接下来文章将会讲述四种排序算法的实现和可行性证明。只有证明一个算法的正确性，才算理解一种算法。

快速排序

步骤

1)从需要排序的数组选中一个作为Key，比Key小的放在右边，比Key大的放在左边。

2 )Key右侧的元素重复步骤1)

3)Key右侧的元素重复步骤1)

观察源码即可找到实现步骤一效果的方法。

可行性证明

题设

1
2
3
4
5
6

1)每次排序选中Key的左侧小于等于Key 

2)每次排序选中Key的右侧大于等于Key

3)需要排序数组长度为2或3时，数据一定是升序

假设数组为 a[] ，Key的下标为k，数组范围为0-n。

1
2
3
4
5
6

1)当 0<=i<k 时，a[i] <=a[k] && a[i]<= a[i+1].

2)当 k<j<=n 时，a[j] >=a[k] && a[j]>= a[j-1].

3)结合1)、2)可以推导出：当 0<=l<n , a[i]<a[i+1]，即排序结果有序

优点和缺点

  • 优点:空间复杂度为 O(N)

  • 缺点:时间复杂度O(Nlog(N))，但是不稳定。Key的选择很关键，选不好复杂度就会变为N的平方。

  • 优化方法：选择数组头部中间尾部，三个元素中间值作为Key。

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

package sort;

import java.util.Arrays;

/**

 * Created by baobing on 16/7/15.

 */

public class QuickSort {

    private int[] list;



    public QuickSort(int[] list) {

        this.list = list;

    }



    public void sort() {

        sort(0, list.length-1);

    }



    public void sort(int low, int high) {

        if (low >= high) {

            return;

        }

        int key = list[low];

        int first = low;

        int last = high;

        while (first < last) {

            //一定要从后往前先

            while (first < last && list[last] >= key) {

                last--;

            }

            list[first] = list[last];

            while (first < last && list[first] <= key) {

                first++;

            }

            list[last] = list[first];

        }

        list[first] = key;

        sort(low, first - 1);

        sort(first + 1, high);

    }

    public static void main(String[] args) {

        int[] list = {10, 18, 12, 4, 5, 8, 15, 3, 23};

        QuickSort q = new QuickSort(list);

        q.sort();

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

    }

}

归并排序

步骤

1）将数组分为两个大小相同的数组（有可能大小相差1），继续分割数组，直到数组大小为1.

2）现在从同一个数组分割来的两个数组都为升序，将两个数组合并为一个升序的数组。

3）重复步骤 2）直到整个数组被合并

原理

典型的分治算法。通过子序列的有序性，保证自身的有序性。

优点缺点

  • 优点：时间复杂度为O(Nlog(N)) 并且极其稳定

  • 缺点：空间复杂度为O(2N)),比较节省空间的场合不适用，尤其是比较大的数组

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

package sort;



import java.util.Arrays;



/**

 * Created by hubaobin on 16/7/16.

 */

public class MergeSort {

    int[] list;



    public MergeSort(int[] list) {

        this.list = list;

    }



    /**

     * 合并两个有序的数组

     * 第一个数组的起始下标为low 终止下标为mid

     * 第二个数组的起始下标为mid+1 终止下标为high

     */

    private void merge(int low, int mid, int high) {

        //用于保存两个数组合并结果

        int[] temp = new int[high - low + 1];

        //第一个数组的始末下标

        int first1 = low, end1 = mid;

        //第二个数组的始末下标

        int first2 = mid + 1, end2 = high;

        //记录临时数组的下标

        int k = 0;

        while (first1 <= end1 && first2 <= end2) {

            if (list[first1] < list[first2]) {

                temp[k++] = list[first1++];

            } else {

                temp[k++] = list[first2++];

            }

        }

        //第一个数组的剩余元素放入临时数组

        while (first1 <= end1) {

            temp[k++] = list[first1++];

        }

        //第二个数组的剩余元素放入临时数组

        while (first2 <= end2) {

            temp[k++] = list[first2++];

        }

        //排序好的临时数组覆盖原数组

        System.arraycopy(temp, 0, list, low, temp.length);

    }



    /**

     * 排序数组

     *

     * @param low  起始下标

     * @param high 末尾下标

     */

    public void sort(int low, int high) {

        if (low >= high) return;

        int mid = (low + high) >> 1;

        sort(low, mid);

        sort(mid + 1, high);

        merge(low, mid, high);

    }



    public void sort() {

        sort(0, list.length - 1);

    }



    public static void main(String[] args) {

        int[] list = {10, 18, 12, 4, 5, 8, 15, 3, 23};

        MergeSort q = new MergeSort(list);

        q.sort();

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

    }

}

堆排序

步骤

  • 最大堆：完全二叉树，所有根节点的子节点小于等于本身

1）N个节点的树，构建为最大堆。

2）根节点与树最后一个叶子节点交换。

3）除去尾部的交换节点之后的树，构造为最大堆

4）重负步骤2）

优点缺点

  • 优点 复杂度O(Nlog(N)) 空间复杂度为O(N)

  • 缺点 构建最大堆浪费不少时间

源码

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

package sort;



import java.util.Arrays;



/**

 * Created by hubaobin on 16/7/16.

 */

public class HeapSort {

    private int[] list;



    public HeapSort(int[] list) {

        this.list = list;

    }



    /**

     * 排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的

     */

    private void sort() {

        buildMaxHeapify();

        //末尾与头交换，交换后调整最大堆

        for (int i = list.length - 1; i > 0; i--) {

            swap(0, i);

            maxHeapify(i, 0);

        }

    }





    private void buildMaxHeapify() {

        //没有子节点的才需要创建最大堆，从最后一个的父节点开始

        int startIndex = getParentIndex(list.length - 1);

        //从尾端开始创建最大堆，每次都是正确的堆

        for (int i = startIndex; i >= 0; i--) {

            maxHeapify(list.length, i);

        }

    }



    /**

     * 创建最大堆

     *

     * @paramheapSize需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了

     * @paramindex当前需要创建最大堆的位置

     */

    private void maxHeapify(int heapSize, int index) {

        //当前点与左右子节点比较

        int left = getChildLeftIndex(index);

        int right = getChildRightIndex(index);



        int largest = index;

        if (left < heapSize && list[index] < list[left]) {

            largest = left;

        }

        if (right < heapSize && list[largest] < list[right]) {

            largest = right;

        }

        //得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整

        if (largest != index) {

            swap(index, largest);

            maxHeapify(heapSize, largest);

        }

    }



    private void swap(int a, int b) {

        int temp = list[a];

        list[a] = list[b];

        list[b] = temp;

    }



    /**

     * 父节点位置

     */

    private static int getParentIndex(int current) {

        return (current - 1) >> 1;

    }



    /**

     * 左子节点position注意括号，加法优先级更高

     */

    private static int getChildLeftIndex(int current) {

        return (current << 1) + 1;

    }



    /**

     * 右子节点position

     */

    private static int getChildRightIndex(int current) {

        return (current << 1) + 2;

    }

    public static void main(String[] args) {

        int[] list = {10, 18, 12, 4, 5, 8, 15, 3, 23};

        HeapSort q = new HeapSort(list);

        q.sort();

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

    }



}

基数排序

步骤

1）将需要排序的数组list中的数字根据他们的个位数字i放到对应的数组bucket[i]的末尾。

2）从0-9依次将bucket中的数字放置到需要排序的数组list。

3）接下来是十位、百位，重复类似步骤1），指导数组list中的所有元素该位置都没有数字。

优点和缺点

优点：

  • 时间复杂度低O(Mlog(N)).（N为排序数字个数M为最大位）对于N大M小的情况尤为突出。

  • 可以实现相同大小的数字，依旧保持先后顺序

缺点

  • 辅助空间需求要求比较大

  • M大N小时，性能下降

  • 试用的排序类型比较少，整数最适合

缺点

源码

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

package sort;



import java.util.Arrays;



/**

 * Created by hubaobin on 16/7/17.

 */

public class RadixSort {

    int list[];



    public RadixSort(int[] list) {

        this.list = list;

    }



    public void sort() //d表示最大的数有多少位

    {

        int n = 1;

        //bucket[i]用来装载需要排序的位等于i的数字

        int[][] bucket = new int[10][list.length];

        //idxArr[i] 表示bucket[i]填充数据个数

        int[] idxArr = new int[10];

        for (int i = 0; i < 10; i++) idxArr[i] = 0;



        while (true) {

            boolean isContinue = false;

            //将数组放入bucket

            for (int i = 0; i < list.length; i++) {

                int divRes = list[i] / n;

                if (divRes >= 10) isContinue = true;

                int lsd = (divRes % 10);

                bucket[lsd][idxArr[lsd]++] = list[i];

            }

            //bucket中的数字放回原数组

            for (int i = 0, k = 0; i < 10; i++) {

                for (int j = 0; j < idxArr[i]; j++) {

                    list[k++] = bucket[i][j];



                }

                idxArr[i] = 0;

            }

            if (!isContinue) break;

            n *= 10;

        }

    }



    public static void main(String[] args) {

        int[] list = {10, 18, 12, 4, 5, 8, 15, 3, 23};

        RadixSort q = new RadixSort(list);

        q.sort();

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

    }

}