快速排序的多种实现写法_快速排序的各种写法

快速排序

分析

时间复杂度

1. 快速排序和Shell排序都有多种策略可选择,快速排序对于中轴值的选择,选择得好每次左右子问题的规模就相近,则只需要划分lgN次就可以将整个排序划分完全
2. 而每个子问题划分成下一个子问题的时间复杂度是n(即partition()算法).所以整体就是NlgN.
3. 如果划分得不好,即每次左右子问题规模差距极大,即每次划分为长度为1和left(剩余)两个子问题,则共需划分N次,所以最差时间为N^2

空间复杂度

1. 由划分子问题的次数决定调用栈的次数,和上面一样是[lgn,n]

稳定性

1. 稳定性取决于划分子问题时是否保证稳定性.
2. 快慢指针法是不稳定的,因为也是使用交换法进行调整分组,这种交换是直接交换位于"大于段"的任意两个元素来给"小于等于段"腾位置,所以对于"大于段"中的两个等值元素有可能被打乱顺序.
3. 对于顺序存储结构应该是不稳定的 (如果能将partition()函数写成稳定性的划分是可以实现稳定的).
4. 链式存储结构可实现稳定性, patition()函数目的同 LC86. 分隔链表 对于这题我有大多人没有想到的方法, 最后附上

算法实现

快排的partition()函数

1. 这个算法其实是比较难的, 快排中其它部分的代码几乎就是模板一样固定死了. 而partition()函数的写法有3种及以上.
2. 等价于下面两个问题 (第一个问题勉强算是, 只是需要稍微改造一下, 快排中用到时我进行了改动)

• 给定数组nums,再给一个数num,把小于等于num的数放在数组的左边,大于num的放数组右边.空间O(1)时间O(n)
• 给定数组nums,再给一个数num,把小于num的数放在数组的左边, 等于num的数放在数组的中间,大于num的放数组右边.空间O(1)时间O(n)

public class Partition extends Sort { //Sort抽象类最后补充
    public static void main(String[] args) {
        new Partition().correctTest(null);
    }

    @Override
    public void sortNums(int[] nums) {
//        segmentTwoPart_LeftRightPoint(nums, 6);
//        segmentTwoPart_FastSlowPoint(nums, 1);
        segmentTwoPart_LeftRightPoint_Variant(nums, 6);

    }

    public void segmentTwoPart_FastSlowPoint(int[] nums, int num) {
        /*
        1. 有两个指针,将数组划分成三段:小于等于段/大于段/未筛选段
        2. (-∞,lessEqualR-1]是小于等于段,[lessEqualR,i]是大于段,[i+1,∞)未筛选
        3. i遍历过的地方都是分好段的,方式是:nums[i]属于哪一段就放到哪一段的末尾:
          nums[i] <= num时就要放到小于等于段末尾. 当>时就不动,自动放到大于段末尾
         */
        int lessEqualR = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= num) { // 作为快速排序的子问题划分算法,不管这里的"=="是否触发swap(),都是不稳定的.
                // 因为: 只要触发交换,即交换[lessEqualR,i]大于段中nums[lessEqualR]和nums[i],都会导致原本minRight和i位置互换,
                // 而之后这两个元素并会再次被遍历到,所以只有一次交换操作,会导致大于段失去稳定性
                swap(nums, i, lessEqualR);
                lessEqualR++;
            }
        }
        // lessEqualR-1就是小于等于段尾元素下标
        System.out.println(lessEqualR - 1);
    }

    /**
     * 快慢指针的另一种写法,思想是一样的,只是写法稍有不同
     */
    public void segmentTwoPart_FastSlowPoint_Variant(int[] arr) {
        int lessEqualR = -1; // 代表小于段的尾元素下标
        int index = 0;
        int N = arr.length;
        while (index < N) {
            if (arr[index] <= arr[N - 1]) {
                swap(arr, ++lessEqualR, index++);
            } else {
                index++;
            }
        }
        // lessEqualR代表小于等于段的尾元素下标
        System.out.println(lessEqualR);
    }

    /**
     * 也是采用"分段思想",不过采用相向指针
     * <p>
     * 就是将segmentThreePart_OppositePoint()划分"大于段"的操作用在了划分"小于等于段".
     * 1.将"未筛选段"逐个遍历,满足小于等于的条件就放到"小于等于段"的下一个位置,即未筛选段头
     * 2.放的方式是交换,交换后继续筛选原本未筛选段头的元素即遍历的当前位置元素
     * 3.不满足条件就不动,注意因为不动这些不满足条件的,所以要让不满足条件的远离"小于等于段",所以遍历时从"小于等于段"的另一端开始
     */
    public static void segmentTwoPart_OppositePointer(int[] nums, int num) {
        int lessEqualR = 0; //"小于等于段"尾, 也是"已筛选段"的头
        for (int i = nums.length - 1; i >= lessEqualR; i--) {
            if (nums[i] <= num) {
                swap(nums, lessEqualR, i);
                lessEqualR++;
                i++;
            }
        }
        // lessEqualR代表小于等于段的尾元素下标
        System.out.println(lessEqualR);
    }

    /**
     * 过了很久以后我能想起来的解法,是segmentTwoPart()快慢指针演变的
     * 1. 有三个指针,将数组划分成三段:小于段/等于段/大于段/未筛选段
     * 2. (-∞,lessEqualR-1]是小于段,[lessEqualR,equalsR]等于段,[equalsR,i]是大于段,[i+1,∞)未筛选
     * 3. i遍历过的地方都是分好段的,方式是:nums[i]属于哪一段就放到哪一段的末尾,nums[i] < num时就要放到小于段末尾;nums[i] = num时就要放到等于段末尾;当>时就不动,自动放到大于段末尾:
     *    a) nums[i]<num时放到小于段末尾,又因为小于段和等于段紧挨着,所以只能让等于段整体后移才行.方式是先放到等于段尾下一个位置,然后让等于段头和段尾交换,
     *     因为等于端头正好在小于段尾,这样等于段头元素拼接到等于段尾,小于段尾的下一个位置拼接了nums[i]
     *    b) nums[i]=num时放到等于段末尾,就和segmentTwoPart()的快慢指针放置小于等于段的方式一样
     *    c) nums[i]>num时不动,自动放到大于段末尾
     */
    public void segmentThreePart_FastSlowPoint(int[] nums, int num) {
        int lessR = 0; //小于段下一个元素位置,即等于段头
        int equalsR = 0; // 等于段下一个元素位置,即大于段头
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < num) {
                swap(nums, i, equalsR);
                swap(nums, lessR, equalsR);
                lessR++;
                equalsR++;
            } else if (nums[i] == num) {
                swap(nums, i, equalsR);
                equalsR++;
            }
        }
        System.out.println("等于段的范围: [" + lessR + ", " + (equalsR - 1) + "]");
    }

    /**
     * 1. 小于段就是采用segmentTwoPart_FastSlowPoint()方法划分
     * 2. 遇到"=="则不动,即放在等于段
     * 3. 遇到">"放到大于段,放的方式是拼接到大于段前一个位置,交换时原大于段前一个位置的元素并没有被遍历到,
     * 所以交换完下一次继续遍历该元素现在的位置,即nums[i]
     */
    public void segmentThreePart_OppositePoint(int[] nums, int num) {
        int lessR = 0; // 小于段下一个位置,即等于段头
        int moreL = nums.length - 1; // 大于段前一个位置,即等于段尾
        for (int i = 0; i <= moreL; i++) {
            if (nums[i] < num) {
                swap(nums, lessR, i);
                lessR++;
            } else if (nums[i] == num) {
            } else if (nums[i] > num) {
                swap(nums, moreL, i);
                moreL--;
                i--;
            }
        }
        System.out.println("等于段的范围: [" + lessR + ", " + moreL + "]");
    }

    /**
     * 左右双指针法
     * 重点: 谁先移动,退出循环时谁就会超出其代表的范围
     *
     * 注意:不支持nums.length=1的情况
     */
    public void segmentTwoPart_LeftRightPoint(int[] nums, int num) {
        if (nums.length <= 1) {
            return;
        }
        int left = 0; // 小于等于段段尾
        int right=  nums.length - 1; // 大于段段头
        while(left < right) {
            while (left < right && nums[left] <= num) {
                left++;
            }
            while (left < right && nums[right] > num) {
                right--;
            }
            if (left < right) { //需要进行交换
                swap(nums, left, right);
            }
        }
        // 最终肯定是left主动越界到right位置,变成小于等于段段尾下一个位置
        System.out.println(left - 1);
    }

    /**
     * 左右双指针法
     * 先让right移动, 谁先移动,退出循环时谁就会超出其代表的范围,这里right超出范围
     */
    public void segmentTwoPart_LeftRightPoint_Variant(int[] nums, int num) {
        if (nums.length <= 1) {
            return;
        }
        int left = 0; //小于等于段段尾
        int right=  nums.length - 1; // 大于段段头
        while(left < right) {
            while (left < right && nums[right] > num) {
                right--;
            }
            while (left < right && nums[left] <= num) {
                left++;
            }
            if (left < right) {
                swap(nums, left, right);
            }
        }
        // 最终肯定是right主动越界left到位置,所以left是一直处于小于等于段段尾
        System.out.println(left);
    }

    /**
     * 坑法 - 同数据结构与算法C语言版
     * 局限性: 划分两段的依据值pivot必须是头元素, 因为left要在第一个坑处.
     * 不过不影响快排的pivot策略,因为只需要在找到最合适的pivot后将头元素和该pivot交换位置即可
     *
     * 分析: 根据谁先移动,最终谁就会越界,所以right会跑到大于段前一个位置,此时left和right重叠为坑,填坑后left还表示小于等于段段尾
     */
    public void segmentTwoPart_Pit(int[] nums) {
        int left = 0; //小于等于段段尾
        int right = nums.length - 1; //大于段段头
        int pivot = nums[0]; //划分两段的依据值
        while (left < right) {
            while (left < right && nums[right] > pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        int pivotIndex = left;
        nums[pivotIndex] = pivot;
        System.out.println("小于等于段尾元素下标: " + pivotIndex);
    }
}
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
191
192
193
194
195
196
197
198
199
200

快速排序完整代码

public class QuickSort extends Sort {
    public static void main(String[] args) {
        new QuickSort().correctTest(null);
    }

    @Override
    public void sortNums(int[] nums) {
        quickSortProcess(nums);
    }

    public void quickSortProcess(int[] nums) {
        quickSortSegmentTwoPart01(nums, 0, nums.length - 1);
    }

    /**
     * 选择pivot的策略
     * 1.一定不能始终选择begin作为pivot,因为这样对sorted已排序(降序/升序)的数组效率很低
     * 2.还有一种三值取中法,暂时不研究
     */
    public int quickSortPivotChoose(int[] nums, int begin, int end) {
        // 暂定为随机选择元素作为pivot
        int index = begin + (int)(Math.random() * (end - begin + 1));
        // 将随机的pivot放到begin位置,可以适用于坑法/segmentTwoPart_FastSlowPoint()的partition()算法
        swap(nums, begin, index);
        return begin;
    }

    public void quickSortSegmentTwoPart01(int[] nums, int begin, int end) {
        if (begin >= end) {
            return;
        }

        int pivotChose = quickSortPivotChoose(nums, begin, end);
        int[] pivotIndexes = segmentThreePart_FastSlowPoint(nums, begin, end, nums[pivotChose]);

        // 递归时,必须要让左和右区间都变化1个距离,因为pivotIndex可能每次都不变,导致递归过程无法减少子问题的长度造成stackOverFlow
        // 对比归并排序中mergeSort()中mid=(begin+end)/2,则mid会不断靠近begin,而这里pivotIndex无法确定其变化
        quickSortSegmentTwoPart02(nums, begin, pivotIndexes[0] - 1);
        quickSortSegmentTwoPart02(nums, pivotIndexes[1] + 1, end);
    }

    /**
     * 划分为3个区间,快慢指针做法
     */
    public int[] segmentThreePart_FastSlowPoint(int[] nums, int begin, int end, int pivot) {
        int lessR = begin;
        int equalR = begin;
        for (int i = begin; i <= end; i++) {
            if (nums[i] < pivot) {
                swap(nums, i, equalR);
                swap(nums, lessR, equalR);
                equalR++;
                lessR++;
            } else if (nums[i] == pivot) {
                swap(nums, i, equalR);
                equalR++;
            }
        }
        int equalBegin = lessR;
        int equalEnd = equalR - 1;
        int[] pivotIndexes = new int[]{equalBegin, equalEnd};
        return pivotIndexes;
    }


    /**
     * 测试其它partition()函数写法
     * 快排的递归过程只有一种写法,写法比较多的是partition()算法
     */
    public void quickSortSegmentTwoPart02(int[] nums, int begin, int end) {
        if (begin >= end) {
            return;
        }

        int pivotChose = quickSortPivotChoose(nums, begin, end);
        int pivotIndex = segmentTwoPart_FastSlowPoint(nums, begin, end, nums[pivotChose]);

        quickSortSegmentTwoPart01(nums, begin, pivotIndex - 1);
        quickSortSegmentTwoPart01(nums, pivotIndex + 1, end);
    }

    /**
     * 划分为2个区间(但是要保证左区间最后一个元素一定是pivot),快慢指针做法
     */
    public int segmentTwoPart_FastSlowPoint(int[] nums, int begin, int end, int pivot) {

        int lessEqualR = begin;
        for (int i = begin; i <= end; i++) {
            if (nums[i] <= pivot) {
                swap(nums, i, lessEqualR);
                lessEqualR++;
            }
        }
        // lessEqualR-1就是小于等于段尾元素下标

        // 交换pivot(首元素)和小于等于段尾元素,而不是将数组简单分成两个部分
        swap(nums, begin, lessEqualR - 1);
        return lessEqualR - 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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

补充说明

1. Sort类在排序专栏文章中