排序算法/选择,插入,冒泡，归并和快速排序

学习笔记

选择排序

思考过程

给定一个数组,[0,1,…..n-1]

  1. n个数选一个最小值，放在0位置
  2. n-1个数选一个n-1个数中的最小值，放在1位置
    ……
    直到整个数组有序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Sort01_SelectSort {
    public static void SelectSort(int[] arr){
        if(arr == null || arr.length < 2) return;

        for (int minValueIndex = 0; minValueIndex < arr.length;minValueIndex++) {
            for (int j = minValueIndex + 1 ; j < arr.length ; j++) {
                if (arr[minValueIndex] > arr[j]) {
                    swap(arr,minValueIndex,j);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

时间复杂度分析

每遍历一轮，找到最大或者最小值的下标，和第一个数交换，结束一轮运算，乱序数组减一，周而复始，直到整个数组有序。
分析一下数组选择排序时间复杂度：
第一次遍历：N*(取数+比较) + 1次交换
… (N-1)(取数+比较) + 1次交换
..
.
= 2 * （N + (N-1) + … + 1） + N
= 2*(aN^2 + bN + c) +N
= 2aN^2 + (2b+1)N + 2c
= aN^2 + bN + c
= N^2
忽略低阶项和常数得到时间复杂度
===> O(n^2)
时间复杂度的意义： a算法：3_N^3 + 2_N^2 + 1 b算法：100w_N^2 + 500w_N + 1000w 当N→无穷大时，常数项就可以忽略，复杂度只与数据量有关。

冒泡排序

思考过程

  1. n个数相邻两两比较，最大值冒泡到最右边
  2. n-1个数相邻两两比较，最大值冒泡到n-1个数的最右边
    ……
    直到整个数组有序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Sort02_BubbleSort {
    public static void BubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        for (int end = arr.length -1 ; end > 0; end--) {
            for (int j = 0; j < end  ; j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

时间复杂度分析

每遍历一轮，相邻的两个数比较交换，谁大谁在后面，直到找到最大或最小值，结束一轮运算，乱序数组减一，周而复始，直到整个数组有序。
分析：
第一次遍历 ： (N-1)*(比较+交换)
…
..
.
冒泡排序和选择排序对所有不同情况的数据样本，复杂度的表现都是一样的，O(N^2).

插入排序

一个数组，先让0-0范围有序，再让0-1范围内有序，周而复始，直到整个数组有序。 先局部有序，再逐一插入单个数。，类比打牌，把牌一个一个插入到前面有序的牌中。

  1. 指针停在0位置，[0]有序
  2. 指针停在1位置, 与前面的数依次比较，小的放前面，直到[0,1]有序
  3. 指针停在2位置, 与前面的数依次比较，小的放前面,指针左移一位，直到[0,1,2]有序 …… 直到整个数组有序
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
public class Sort03_InsertSort {

    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        for (int end = 1; end < arr.length; end++) {
            int maxIndex = end;
            while (maxIndex - 1  >= 0 && arr[maxIndex -1] > arr[maxIndex]) {
                swap(arr,maxIndex - 1, maxIndex);
                maxIndex--;
            }
        }
    }


    //优化版本
    public static void insertSort2(int[] arr) {
        if (arr == null || arr.length < 2) return;

        for (int end = 1; end < arr.length; end++) {
            for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
                swap(arr, pre, pre + 1);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

归并排序

建立的归并操作的基础上，稳定的排序算法，时间复杂度O(nlogn) . 先将每个子序列有序，再使子序列段间有序，最后合成一个有序序列。 又叫做二路归并。
*

递归实现思路

思考过程：

  1. 保证左边数组有序
  2. 保证右边数组有序
  3. 合并左右两边数组使整个数组有序。
  • 3.1 需要一个辅助数组来保存比较后的数

非递归实现思路

相比递归实现，非递归使用变化的步长(step)来代表拆分的子序列;

  1. 步长为1时： [1][2][4][3][5][0] 交替 ，每个序列中只有一个数
  2. 步长为2时： [12][34][05] 交替 ， 第1步时的左右序列已合并变有序， 每个序列中有两个数
  3. 步长为4时： [1234][05] ，第2步时的左右序列已合并变为左序列且有序.
  4. 步长为8，超过数组本身长度，直接合并为一个序列，排序完毕。

时间复杂度估算： 步长逼近N，需要O(logN)次，每一次所有数需要合并一次，所以是O(n) ==> 所以复杂度为O(nlogn)

代码实现

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
public class Sort04_MergeSort {

    /**
     * 归并排序递归实现
     * @param arr
     */
    public static void mergeSortByRecursive(int[] arr) {
        if (arr == null || arr.length < 2) return;
        process(arr,0,arr.length - 1);
    }

    // 保证输入数组有序
    public static void process(int[] arr,int L , int R) {
        //基线条件：: 只有一个元素时，结束
        if (L == R) return;
        // 中间位置
        // int mid = (L + R) / 2 ，这种计算方法可能导致 L+ R超出整数范围
        int mid = L + ((R - L) >> 1);
        //让左边数组全部有序
        process(arr, L , mid);
        //让右边数组全部有序
        process(arr, mid + 1, R);
        //合并左边和右边数组
        merge(arr,L,mid,R);
    }

    // 合并左组和右组
    private static void merge(int[] arr, int L, int M, int R) {
        // 申请一个辅助数组合并左组和右组
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //要么p1越界，要么p2越界，不可能出现同时越界
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        //合并数据回填
        for (int j = 0; j < help.length; j++) {
            arr[L + i] = help[i];
        }
    }



    /**
     * 归并排序非递归实现
     */
    public static void mergeSortNotRecursive(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //初始步长为1
        int step = 1;
        int N = arr.length;
        while (step < N) {
            // -- 调整步长 -- start
            int L = 0;
            while (L < N) {
                //计算中点位置
                int M = 0;
                if (N - L >= step) {
                    M = L + step - 1;
                } else {
                    //只剩下左组的边界情况
                    M = N - 1;
                }
                // M到了N-1，说明没有右组
                if (M == N - 1) {
                    break;
                }
                int R = 0;
                //算右组的个数 (N-1)-(M+1) + 1 = N-1-M
                if (N - 1 - M >= step) {
                    // R能来到step位置
                    R = M + step;
                } else {
                    // 凑不够右组
                    R = N - 1;
                }
                // M，R都算出来，合并左组和右组,算法和递归合并排序一致
                merge(arr, L, M, R);
                //有可能 R+1越界
                if (R == N - 1) {
                    break;
                } else {
                    // 下一个左组的位置
                    L = R + 1;
                }
            }
            // -- 调整步长 -- end
            //边界考虑：步长超过数组本身长度，排序结束。防止step * 2 超过整数最大值
            // 为什么 step >= N/2 不行， 因为n/2 是向下取整的。
            // 比如17个数，步长为8的时候，17/2 = 8 ,直接停了。
            if (step > N / 2) {
                break;
            }
            //增加步长*2
            step *= 2;
        }

    }

}

快速排序

D & C 思想

  1. 基线条件：最简单的数组： 空数组或只有一个元素的数组，不需要排序直接返回。
  2. 缩小问题规模：选择基准值，把整个数组分解 [小于基准值 , 基准值, 大于基准值]

荷兰国旗问题

现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。
红 = 0 ，白 = 1 ，蓝 = 2
[0,1,2,1,0,2,1,0,2,1] => 变成 [0,0,0,1,1,1,1,2,2,2]

简单场景:

一个数组[x,x,x,p], 小于等于p的放左边,大于p的放右边

数组分为[Less区,待排序区,P], 初始化时,Less区大小为0, 指针从左往右移动,指向的数为当前数

  1. 当前数 <= p(基准值),当前数和Less区外的下一个数做交换,Less区右扩,当前数跳下一个,越界了停止。
  2. 当前数 > P(基准值),当前数直接跳下一个,越界了停止。

进阶场景:

一个数组[x,x,x,x,x,p],小于p的放左边,等于p的放中间,大于p的放右边。
数组要分为三个区域,[Less区,待排序区,(More区,p)].

  1. 当前数< 基准值, 当前数与Less区的下个数做交换,Less区右扩, 当前数跳下一个。
  2. 当前数> 基准值, 当前区与More区的前一个数做交换,More区向左扩,当前数不动(交换过还没看)。
  3. 当前数 = 基准值，直接跳下一个。
  4. 最后,基准值和More区的第一个数换,排序结束

快排的递归实现

快排最小问题规模等价于荷兰国旗问题：一串数字,选一个数为基准值，把小于基准值的数放在它的左边，大于基准值的数放在它的右边。 要求时间复杂度为O(n)，并且只能使用有限几个变量
a. 先按单个数分层,返回单个数的左右边界.
b. 递归函数

非递归版本思路

用Stack栈做任务,每一个最小任务就是一个荷兰国旗问题,还是使用partition方法来实现分层。

代码实现

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
import java.util.Stack;
public class Sort05_QuickSort {

    /**
     * 1. 实现场景: 一个数组[x,x,x,p], 小于等于p的放左边,大于p的放右边
     * @param arr
     */
    //方法效果:拿数组的最右一个数做基准值, 结果返回<=该数放左边,>=该数放右边。
    public static void splitNum01(int[] arr) {
        //Less区的右边界
        int lessEqualR = -1;
        //当前指针下标
        int index = 0;
        //最右值
        int mostR = arr.length - 1;
        while(index < arr.length) {
            if(arr[index] <= arr[mostR]){
                //交换两个值
                swap(arr,lessEqualR + 1 , index);
                lessEqualR++;
                index++;
                //上三句可简写成一句
                //swap(arr,++lessEqualR,index++);
            }else {
                index++;
            }
        }
    }

    /**
     *2.进阶场景: 一个数组[x,x,x,x,x,p],小于p的放左边,等于p的放中间,大于p的放右边。
     * @param arr
     */
    public static void splitNum02(int[] arr) {
        //Less区的右边界
        int lessR = -1;
        //more区的左边界
        int moreL = arr.length - 1;
        //当前指针下标
        int index = 0;
        //划分值下标
        int poivt = arr.length - 1;
        while(index < moreL) {
            if(arr[index] < arr[poivt]){
                swap(arr,++lessR,index++);
            }else if  (arr[index] > arr[poivt]){
                swap(arr,--moreL,index);
            }else {
                index++;
            }
        }
        // 第4步
        swap(arr,moreL,poivt);
    }

    /**
     * 3. 快速排序递归实现
     */

    /**
     * 先按单个数分层,返回单个数的左右边界.
     * @param arr
     * @param L
     * @param R
     * @return
     */
    //拿单个数来分层, 在arr[L...R]范围上,拿arr[R]做划分值
    //返回等于arr[R]区域的左右边界
    public static int[] partition(int[] arr,int L,int R) {
        //Less区的右边界
        int lessR = L-1;
        //more区的左边界
        int moreL = R;
        //当前指针下标
        int index = L;
        //划分值下标
        int poivt = R;
        while(index < moreL) {
            if(arr[index] < arr[poivt]){
                swap(arr,++lessR,index++);
            }else if  (arr[index] > arr[poivt]){
                swap(arr,--moreL,index);
            }else {
                index++;
            }
        }
        // 第4步
        swap(arr,moreL,poivt);
        //返回左右边界
        return new int[]{lessR+1,moreL};
    }

    /**
     * 递归函数
     *
     * @param arr
     */
    public static void quickSortByRecursive(int[] arr) {
        if(arr == null || arr.length < 2) return;
        process(arr,0,arr.length -1);
    }
    //递归
    public static void process(int[] arr,int  L , int R) {
        if(L >= R) return;
        int[] equalRange = partition(arr,L,R);
        // equalRange[0],等于区域的第一个数
        // equalRange[1],等于区域的最后一个数
        process(arr,L,equalRange[0]-1);
        process(arr,equalRange[1]+1,R);
    }

    /**
     * 4. 快速排序非递归实现
     *  用Stack栈做任务,每一个最小任务就是一个荷兰国旗问题,还是使用partition方法来实现分层。
     */
    //任务定义
    public  static class Job {
        public int L;
        public int R;
        public Job(int left, int right) {
            L = left;
            R = right;
        }
    }
    public static void quickSortByNotRecursive(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        Stack<Job> stack = new Stack<>();
        stack.push(new Job(0, arr.length - 1));
        while (!stack.isEmpty()) {
            Job cur = stack.pop();
            int[] equals = partition(arr, cur.L, cur.R);
            if (equals[0] > cur.L) { // 有< 区域
                stack.push(new Job(cur.L, equals[0] - 1));
            }
            if (equals[1] < cur.R) { // 有 > 区域
                stack.push(new Job(equals[1] + 1, cur.R));
            }
        }
    }

    /**
     * 交换方法
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}