快速排序的实现对比

Posted on In , Views: Waline:

原地 v.s. 非原地 (in-place v.s. out-place)
原地：快慢指针、左右指针、挖坑法
单独处理相等元素：三路快排
非递归实现

当序列有序时，时间复杂度将是N^2，所以此时我们选取 前中后 中值为中间的值和关键字的位置进行交换，那么我们再进行排序的序列的时间复杂度基本上被优化为N*logN。人为打乱排序

快排的核心是序列分割：以参考元素(pivot)为界将序列分为大小两部分，并递归该操作。下面的示例代码未采用in-place操作，实现上简单粗暴，也更突出该核心思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def partition(arr):
    pivot = arr[0]
    part_less = [item for item in arr[1:] if item <= pivot]
    part_great = [item for item in arr[1:] if item > pivot]
    return part_less, pivot, part_great
    
def quick_sort(arr):
    if len(arr) <=1:
        return arr
    part_less, pivot, part_great = partition(arr)
    return quick_sort(part_less) + [pivot] + quick_sort(part_great)

from random import randint
arr = [randint(1, 20) for i in range(10)]
print(arr)
arr_sorted = quick_sort(arr)
print(arr_sorted)

通常的快速排序会采用in-place操作，这里仅用于展示快排的核心思想。需要注意，虽然与 pivot 相等的元素最终会与 pivot元素 并列排布，但在实现时我们仅将 pivot元素 置于两个分组之间，与之相等的元素通常不做特殊处理，可归于任一分组，留待递归处理。当然也可以将与pivot相等的元素都找出来，即所谓的三路快排，后面也会讲到，适用于元素存在大量重复情况，如荷兰国旗问题。

快慢指针

快慢指针或前后指针(Lomuto partition scheme)：less | great | unprocessed
遍历指标(快指针)在前，遍历序列(标记已处理|未处理序列界线)；分界指标(慢指针)在后，标记已处理部分中大小元素界线。遍历遇到小于pivot元素，就将其与分界指标处元素(第一个大元素)交换位置，并相应移动分界指针位置，之后继续遍历，直至全部比较一遍，最后再将 pivot元素调换到中间。
细节：分界指标可指向小元素末尾，也可指向大元素起始，前者指标递增要先于元素调换，后者指标递增要后于元素调换。此外pivot可取序列首位或末位，尤其是取首位元素时，需格外注意不能移动首位的pivot，具体可有多种处理方式，pivot取末位元素时，则相对简单。

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
#-------pivot取末位元素-------#
def partition(arr, start, end):
    pivot = arr[end] # pivot取末位元素
    marker = start   # 指向大元素起始
    for index in range(start, end): # 遍历到end-1，pivot单独处理
        if arr[index] < pivot: # 是否含=都可以
            arr[index], arr[marker] = arr[marker], arr[index] # swap
            marker += 1
    arr[marker], arr[end] = arr[end], arr[marker] # 末位pivot与大元素调换
    return marker

def partition(arr, start, end):
    pivot = arr[end]
    marker = start -1 # 指向小元素末尾
    for index in range(start, end):  # 遍历到end-1，pivot单独处理
        if arr[index] < pivot: # 是否含=都可以
            marker += 1
            arr[index], arr[marker] = arr[marker], arr[index] # swap
    arr[marker+1], arr[end] = arr[end], arr[marker+1] # 末位pivot与大元素调换
    return marker+1

def quick_sort(arr, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(arr) - 1
    if start >= end: # Base case of recursion
        return
    marker = partition(arr, start, end)
    quick_sort(arr, start, marker-1)
    quick_sort(arr, marker+1, end)

from random import randint
for _ in range(10):
    arr = [randint(1, 20) for i in range(10)]
    arr_check = arr.copy()
    quick_sort(arr)
    arr_check.sort()
    if arr != arr_check:
        print('Not Passed')
        break

arr = [randint(1, 20) for i in range(10)]
print(arr)
quick_sort(arr)
print(arr)

#-------pivot取末位元素-------#
# pivot位于末尾，遍历时最后遇到，代码可写的更紧凑
def partition(arr, start, end):
    pivot = arr[end] # pivot取末位元素
    marker = start   # 指向大元素起始
    for index in range(start, end+1): #pivot最后处理
        if arr[index] <= pivot: # 必须取=
            arr[index], arr[marker] = arr[marker], arr[index] # swap
            marker += 1
    return marker-1

def partition(arr, start, end):
    pivot = arr[end]
    marker = start -1 # 指向小元素末尾
    for index in range(start, end+1):  # 遍历到end-1，pivot单独处理
        if arr[index] <= pivot: # 必须取=
            marker += 1
            arr[index], arr[marker] = arr[marker], arr[index] # swap
    return marker
    
#------pivot取首位元素------#
def partition(arr, start, end):
    pivot = arr[start]
    marker = start + 1 # 指向大元素起始
    for index in range(start+1, end+1): # 略过首位的pivot，需遍历到end
        if arr[index] < pivot: # 是否含=都可以
            arr[index], arr[marker] = arr[marker], arr[index] # swap
            marker += 1
    arr[marker-1], arr[start] = arr[start], arr[marker-1] # 首位pivot与小元素调换
    return marker-1

def partition(arr, start, end):
    pivot = arr[start]
    marker = start   # 指向小元素末尾
    for index in range(start+1, end+1): # 略过首位的pivot，需遍历到end
        if arr[index] < pivot: # 是否含=都可以
            marker += 1
            arr[index], arr[marker] = arr[marker], arr[index] # swap
    arr[marker], arr[start] = arr[start], arr[marker] # 首位pivot与小元素调换
    return marker

#-----------不推荐-----------#
def partition(arr, start, end):
    pivot = arr[start] # pivot取首位元素
    marker = start
    for index in range(start, end+1):  # 需遍历到end
        if arr[index] < pivot: #不能取=：首位的pivot不能动，marker指向小元素末尾
            marker += 1
            arr[index], arr[marker] = arr[marker], arr[index] # swap
    arr[marker], arr[start] = arr[start], arr[marker] # 首位pivot与小元素调换
    return marker
# 取等号为什么会越界

def partition(arr, start, end):
    pivot = arr[start]
    marker = start-1
    for index in range(start, end+1):
        if arr[index] <= pivot: #必须取=：首位的pivot不能动，marker指向小元素末尾
            marker += 1
            arr[index], arr[marker] = arr[marker], arr[index] # swap
    arr[marker], arr[start] = arr[start], arr[marker] # 首位pivot与小元素调换
    return marker
# 不取等号为什么会无限递归

def partition(arr, start, end):
    pivot = arr[start]
    marker = start
    for index in range(start, end+1):
        if arr[index] <= pivot: # 必须取=：首位的pivot不能动，marker指向大元素起始
            arr[index], arr[marker] = arr[marker], arr[index] # swap
            marker += 1
    arr[marker-1], arr[start] = arr[start], arr[marker-1] # 首位pivot与小元素调换
    return marker-1
# 不取等号为什么会无限递归

def partition(arr, start, end):
    pivot = arr[start]
    marker = start + 1
    for index in range(start, end+1):
        if arr[index] < pivot: # 不能取=：首位的pivot不能动，marker指向大元素起始
            arr[index], arr[marker] = arr[marker], arr[index] # swap
            marker += 1
    arr[marker-1], arr[start] = arr[start], arr[marker-1] # 首位pivot与小元素调换
    return marker-1
# 取等号为什么会越界

As this scheme is more compact and easy to understand, it is frequently used in introductory material, although it is less efficient than Hoare’s original scheme e.g., when all elements are equal.[17] This scheme degrades to O(n2) when the array is already in order.

左右指针

左右指针(Hoare partition scheme)：less | unprocessed | great
左指针向右找小元素，遇到大元素暂停；右指针向左找大元素，遇到小元素暂停；两指针都暂停时交换元素位置，之后继续左右夹逼，直至两指针相遇，最后再将 pivot元素调换到中间。实现上的关键的点为：

  • 必须确保pivot元素在最终调换前不能被移动；
  • pivot取首位元素时与小元素末位调换，pivot取末位元素时与大元素首位调换。

而为了确保上述要点，最佳实践为：

  • 与pivot同侧的指针在比较元素时要包含等号；
  • pivot取首位元素则先移动右指针，pivot取末位元素则先移动左指针；
  • 左右指针移动时应确保不越过对方(left < right)，并在相遇时结束；

这些操作可确保相遇位置刚好指向pivot最终位置：先动左指针(pivot取末位)，相遇于大元素首位；先动右指针(pivot取首位)，相遇于小元素末位。不遵守这些实践要求也可以，且实现方式有很多种，只是需要小心应对各种corner case，代码会比较丑。

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
def partition(arr, left, right):
    index_pivot = left      # pivot取首位元素
    pivot = arr[index_pivot]
    while left != right:    # != 或 < 都可以
        # pivot取首位元素，右指针先走
        while left < right and arr[right] >= pivot: # 可不取=
            right -= 1      # 右指针向左直至出现小于pivot的元素
        while left < right and arr[left] <= pivot:  # 必须取=
            left += 1       # 左指针向右直至出现小于pivot的元素
        arr[left], arr[right] = arr[right], arr[left]
    arr[left], arr[index_pivot] = arr[index_pivot], arr[left] #left或right均可
    return left
 

def partition(arr, left, right):
    index_pivot = right     # pivot取末位元素
    pivot = arr[index_pivot]
    while left != right:    # != 或 < 都可以
        # pivot取首位元素，左指针先走
        while left < right and arr[left] <= pivot:  # 可不取=
            left += 1
        while left < right and arr[right] >= pivot: # 必须取=
            right -= 1
        arr[left], arr[right] = arr[right], arr[left]
    arr[left], arr[index_pivot] = arr[index_pivot], arr[left] #left或right均可
    return left
    
#-----------不推荐------------#
def partition(arr, left, right):
    index_pivot = left      # pivot取首位元素
    pivot = arr[index_pivot]
    left += 1               # 跳过首位的pivot
    while left != right:    # != 或 < 都可以
        # 左右指针哪个先走均可，且均可不取=
        # 但至少一侧要取=，否则可能陷入死循环
        while left < right and arr[right] > pivot:
            right -= 1
        while left < right and arr[left] <= pivot:
            left += 1
        arr[left], arr[right] = arr[right], arr[left]
    # left, right会在小元素末位相遇
    # 但也可能 pivot 本身就是最小元素，此时需修正位置
    if arr[left] > pivot: 
        left -= 1
    arr[left], arr[index_pivot] = arr[index_pivot], arr[left] #left或right均可
    return left

def partition(arr, left, right):
    index_pivot = left      # pivot取首位元素
    pivot = arr[index_pivot]
    while left != right:
        # 左右指针哪个先走均可
        while left < right and arr[left] <= pivot: # 必须取=
            left  += 1
        while left < right and arr[right] > pivot:
            right -= 1
        arr[left], arr[right] = arr[right], arr[left]
    # left, right会在大元素首位相遇，此时需修正位置
    # 但也可能 pivot 本身就是最大元素，此时无需修正
    if arr[left] > pivot: 
        left -= 1
    arr[left], arr[index_pivot] = arr[index_pivot], arr[left]
    return left

def partition(arr, left, right):
    index_pivot = left
    pivot = arr[index_pivot]
    while left != right:
        while arr[right] > pivot:                  # 不能取=
            right -= 1
        while left < right and arr[left] <= pivot: # 必须取=
            left  += 1
        if left > right:
            break
        arr[left], arr[right] = arr[right], arr[left]
    # left和right相等
    arr[right], arr[index_pivot] = arr[index_pivot], arr[right]
    return right

def partition(arr, left, right):
    index_pivot = left
    pivot = arr[index_pivot]
    while left != right:
        while left < right and arr[left] <= pivot: # 必须取=
            left  += 1
        while arr[right] > pivot:                  # 不能取=
            right -= 1
        if left > right:
            break
        arr[left], arr[right] = arr[right], arr[left]
    # left可能大于right，只能取right
    arr[right], arr[index_pivot] = arr[index_pivot], arr[right]
    return right

def partition(arr, left, right):
    index_pivot = left
    pivot = arr[index_pivot]
    while True:
        while arr[right] > pivot:                  # 不能取=
            right -= 1
        while left < right and arr[left] <= pivot: # 必须取=
            left  += 1
        if left >= right:
            break
        arr[left], arr[right] = arr[right], arr[left]
    # left和right相等
    arr[right], arr[index_pivot] = arr[index_pivot], arr[right]
    return right

def partition(arr, left, right):
    index_pivot = left
    pivot = arr[index_pivot]
    while True:
        while arr[right] > pivot:                  # 不能取=
            right -= 1
        while left < right and arr[left] <= pivot: # 必须取=
            left  += 1
        if left > right:
            break
        arr[left], arr[right] = arr[right], arr[left]
        left  += 1; right -= 1  # 避免两者相等时陷入死循环
    # left-1与right+1指向同一元素(但right+1可能是负数?)
    arr[left-1], arr[index_pivot] = arr[index_pivot], arr[left-1]
    return left-1

def partition(arr, start, end):
    pivot = arr[start]
    left = start + 1 # 跳过首位的pivot
    right = end
    while True:
        # 左右指针可都不取=(也可都取=)，而不会陷入死循环
        while right > start and arr[right] > pivot:
            right -= 1
        while left < end and arr[left] < pivot:
            left  += 1
        if left > right:
            break
        arr[left], arr[right] = arr[right], arr[left]
        left  += 1; right -= 1
    arr[left-1], arr[start] = arr[start], arr[left-1] # 只能取left-1
    return left-1

def partition(arr, start, end):
    pivot = arr[start]
    left = start + 1 # 跳过首位的pivot
    right = end
    while True:
        # 左右指针可都不取=(也可都取=)，而不会陷入死循环
        while right > start and arr[right] > pivot:
            right -= 1
        while left < end and arr[left] < pivot:
            left  += 1
        if left >= right:
            break
        arr[left], arr[right] = arr[right], arr[left]
        left  += 1; right -= 1
    arr[right], arr[start] = arr[start], arr[right] # 只能取right
    return right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def partition(arr, left, right):
    pivot = arr[(left + right) // 2]
    while True:
        while arr[left]  < pivot: # 不能取=
            left += 1
        while arr[right] > pivot: # 不能取=
            right -= 1
        if left >= right:
            return right
        arr[left], arr[right] = arr[right], arr[left]
        left  += 1; right -= 1

def quick_sort(arr, start=None, end=None):
     if start is None:
         start = 0
     if end is None:
         end = len(arr) - 1
     if start >= end: # Base case of recursion
         return
     marker = partition(arr, start, end)
     quick_sort(arr, start, marker)
     quick_sort(arr, marker+1, end)

挖坑法

挖坑法：less | unprocessed | great
挖坑法与左右指针类似，从两侧交替向中间移动，但不同于左右指针交换元素的做法，挖坑法将pivot元素的值保存后，将其所在位置作为“空位”使用(挖坑)。pivot取序列首位，则空位需存小元素，因此先走右指针，遇到小元素就将元素填入空位，并将元素所处位置作为新的空位，用于存大元素，供左指针使用，如此交替循环，直至两指针相遇。类似的，如果pivot取序列末位，则需先走左指针。最后将pivot元素值填入位于中间的空位。实现上的关键的点为：

  • pivot取序列首位，需先走右指针；pivot取序列末位，需先走左指针
    同时，类似上述左右指针的要点：
  • 元素与pivot比较，左右两边至少一边要取等号，可以两边都取等号
  • 移动左右指针时应确保不越过对方(left < 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
def partition(arr, left, right):
    pivot = arr[left]    # pivot取首位元素，先移右指针
    while left != right: # != 或 < 都可以
        while left < right and arr[right] >= pivot:
            right -= 1
        arr[left] = arr[right]
        while left < right and arr[left] <= pivot:
            left += 1
        arr[right] = arr[left]
    arr[left] = pivot   # left 或 right 都可以
    return left

def partition(arr, left, right):
    pivot = arr[right]   # pivot取末位元素，先移左指针
    while left != right: # != 或 < 都可以
        while left < right and arr[left] <= pivot:
            left += 1
        arr[right] = arr[left]
        while left < right and arr[right] >= pivot:
            right -= 1
        arr[left] = arr[right]
    arr[right] = pivot   # left 或 right 都可以
    return right

#-----------不推荐------------#
def partition(arr, left, right):
    pivot = arr[left]    # pivot取首位元素，先移右指针
    while left < right:  # 会出现left>right，不能取!=
        while arr[right] > pivot: # 不要求left<right，但不能取=
            right -= 1
        arr[left] = arr[right]
        while left< right and arr[left] <= pivot: # 必须取=
            left += 1
        arr[right] = arr[left]
    arr[left] = pivot   # 必须取 left
    return left

def partition(arr, left, right):
    pivot = arr[right]   # pivot取末位元素，先移左指针
    while left < right:  # 会出现left>right，不能取!=
        while arr[left] < pivot: # 不要求left<right，但不能取=
            left += 1
        arr[right] = arr[left]
        while left < right and arr[right] >= pivot: # 必须取=
            right -= 1
        arr[left] = arr[right]
    arr[right] = pivot   # 必须取 right
    return right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quick_sort_test(arr, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(arr) - 1
    if start >= end: # Base case of recursion
        return
    print(arr, start, end)
    marker = partition(arr, start, end)
    print(marker)
    quick_sort_test(arr, start, marker-1)
    quick_sort_test(arr, marker+1, end)

arr = [randint(1, 20) for i in range(10)]
quick_sort_test(arr)
print(arr)

三路快排

https://algs4.cs.princeton.edu/23quicksort/
Entropy-optimal Sorting
三路快排可以基于前后指针实现，也可基于左右指针实现

  • 基于前后指针扩展：less | equal | unprocessed | great
    将等于pivot的元素放在原本的大元素区间，引入右指针，在序列右侧存放大元素
  • 基于左右指针扩展：equal | less | unprocessed | great | equal
    将等于pivot的元素存放在左右两边的外侧，最后再将两侧这些元素调换到中间
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
def partition(arr, start, end):
    pivot = arr[start]
    left = index = start+1
    right = end
    while index <= right:
        if arr[index] < pivot:
            arr[index], arr[left] = arr[left], arr[index] # swap
            left  += 1
            index += 1
        elif arr[index] > pivot:
            arr[index], arr[right] = arr[right], arr[index] # swap
            right -= 1
        else:
            index += 1
    arr[left-1], arr[start] = arr[start], arr[left-1] # 首位pivot与小元素调换
    return left-1, right


def partition(arr, start, end):
    pivot = arr[start]
    ll = left  = start
    rr = right = end

    while left != right:
        while left < right and arr[right] >= pivot:
            if arr[right] == pivot:
                arr[rr], arr[right] = arr[right], arr[rr]
                rr -= 1
            right -= 1
        while left < right and arr[left] <= pivot:
            if arr[left] == pivot:
                arr[ll], arr[left] = arr[left], arr[ll]
                ll += 1                                
            left += 1
        arr[left], arr[right] = arr[right], arr[left]
    
    #left, right都指向小元素末位
    for k in range(start, ll):
        arr[k], arr[left] = arr[left], arr[k]
        left -= 1
    for k in range(rr+1, end+1):
        right += 1
        arr[k], arr[right] = arr[right], arr[k]
    return left+1, right

   
def partition(arr, start, end):
    pivot = arr[start]
    ll = left = start + 1 # 跳过首位的pivot
    rr = right = end

    while True:
        while right > start and arr[right] > pivot:
            right -= 1
        while left < end and arr[left] < pivot:
            left  += 1
        if left == right and arr[left]==pivot:
             # 没有这一部分依然能实现排序
             # 但某些情况下过程与预期不服
            arr[left], arr[ll] = arr[ll], arr[left]
            ll += 1
        if left >= right:
            break
        arr[left], arr[right] = arr[right], arr[left]
        if arr[left] == pivot:
            arr[left], arr[ll] = arr[ll], arr[left]  
            ll += 1
        if arr[right] == pivot:
            arr[right], arr[rr] = arr[rr], arr[right]
            rr -= 1
        left  += 1; right -= 1

    left = right+1 # right+1指向大元素首位
    for k in range(start, ll):
        left -= 1
        arr[k], arr[left] = arr[left], arr[k]
    for k in range(rr+1, end+1):
        right += 1
        arr[k], arr[right] = arr[right], arr[k]
    return left, right

arr = [5, 1, 1, 4, 2, 4, 2, 4, 4, 2, 4, 5, 1, 3, 2, 1, 5, 5, 2, 5]
count = 0
for _ in range(10):
    arr = [randint(1, 3) for i in range(20)]
    arr1 = arr.copy()
    arr2 = arr.copy()
    l, r = partition(arr, 0, 19)
    ll, rr = partition1(arr1, 0, 19)
    if rr-ll != r-l:
        count += 1
        print(arr2)
        print(arr, arr1)
        print(l, r, ll, rr)
print(count)

arr = [randint(1, 20) for i in range(10)]
arr = [randint(1, 5) for i in range(20)]
print(arr)
partition(arr, 0, 9)
print(arr)

def partition(arr, lo, hi):
    pivot = arr[lo]
    i = lo+1; j=hi
    p = lo; q = hi+1
    while True:
        while i<=j and arr[i] < pivot:
            i += 1
        while i<=j and arr[j] > pivot:
            j -= 1
        if i>=j:
            break
        arr[i], arr[j] = arr[j], arr[i]
        if arr[i]==pivot:
            p += 1
            arr[p], arr[i] = arr[i], arr[p]                    
        if arr[j]==pivot:
            q -= 1
            arr[q], arr[j] = arr[j], arr[q]   
        i += 1
        j -= 1                 

    #i = j + 1
    for k in range(lo, p+1):
        arr[k], arr[j] = arr[j], arr[k]
        j -= 1
    for k in range(q, hi+1):
        arr[k], arr[i] = arr[i], arr[k]
        i += 1
        
    return j+1, i-1


# https://algs4.cs.princeton.edu/23quicksort/QuickBentleyMcIlroy.java.html
def partition(arr, lo, hi):
    i = p = lo
    j = q = hi+1
    pivot = arr[lo]
    while True:
        i += 1
        j -= 1
        while arr[i] < pivot:
            if i == hi:
                break
            i += 1
        while arr[j] > pivot:
            if j == lo:
                break
            j -= 1
        if i==j and arr[i] == pivot:
            p += 1
            arr[p], arr[i] = arr[i], arr[p]
        if i>=j:
            break
        arr[i], arr[j] = arr[j], arr[i]
        if arr[i]==pivot:
            p += 1
            arr[p], arr[i] = arr[i], arr[p]                    
        if arr[j]==pivot:
            q -= 1
            arr[q], arr[j] = arr[j], arr[q]                    
    i = j + 1
    for k in range(lo, p+1):
        arr[k], arr[j] = arr[j], arr[k]
        j -= 1
    for k in range(q, hi+1):
        arr[k], arr[i] = arr[i], arr[k]
        i += 1
        
    return j+1, i-1

def quick_sort_3way(arr, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(arr) - 1
    if start >= end: # Base case of recursion
        return
    left, right = partition(arr, start, end)
    quick_sort_3way(arr, start, left-1)
    quick_sort_3way(arr, right+1, end)

def quick_sort_test(arr, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(arr) - 1
    if start >= end: # Base case of recursion
        return
    print(arr, start, end)
    left, right = partition(arr, start, end)
    print(left, right)
    quick_sort_test(arr, start, left-1)
    quick_sort_test(arr, right+1, end)

arr = [randint(1, 20) for i in range(10)]
quick_sort_test(arr)
print(arr)

尾递归调用优化 空间复杂度

Most practical implementations of Quick Sort use randomized version. The randomized version has expected time complexity of O(nLogn). The worst case is possible in randomized version also, but worst case doesn’t occur for a particular pattern (like sorted array) and randomized Quick Sort works well in practice.

Merge sort accesses data sequentially and the need of random access is low, preferred over QuickSort for Linked Lists.

The depth of quicksort’s divide-and-conquer tree directly impacts the algorithm’s scalability, and this depth is highly dependent on the algorithm’s choice of pivot.
Python没有尾递归优化，默认递归栈深度为1000，数据量多时很容易就达到最大深度了

非递归操作

需要借助栈或队列

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
def quick_sort(array, l, r):
  if l >= r:
    return
  stack = []
  stack.append(l)
  stack.append(r)
  while stack:
    low = stack.pop(0)
    high = stack.pop(0)
    if high - low <= 0:
      continue
    x = array[high]
    i = low - 1
    for j in range(low, high):
      if array[j] <= x:
        i += 1
        array[i], array[j] = array[j], array[i]
    array[i + 1], array[high] = array[high], array[i + 1]
    stack.extend([low, i, i + 2, high])

#------------#
def partition(arr, l, h):
    i = ( l - 1 )
    x = arr[h]
 
    for j in range(l, h):
        if   arr[j] <= x:
 
            # increment index of smaller element
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
 
    arr[i + 1], arr[h] = arr[h], arr[i + 1]
    return (i + 1)
    
def quickSortIterative(arr, l, h):
 
    # Create an auxiliary stack
    size = h - l + 1
    stack = [0] * (size)
 
    # initialize top of stack
    top = -1
 
    # push initial values of l and h to stack
    top = top + 1
    stack[top] = l
    top = top + 1
    stack[top] = h
 
    # Keep popping from stack while is not empty
    while top >= 0:
 
        # Pop h and l
        h = stack[top]
        top = top - 1
        l = stack[top]
        top = top - 1
 
        # Set pivot element at its correct position in
        # sorted array
        p = partition( arr, l, h )
 
        # If there are elements on left side of pivot,
        # then push left side to stack
        if p-1 > l:
            top = top + 1
            stack[top] = l
            top = top + 1
            stack[top] = p - 1
 
        # If there are elements on right side of pivot,
        # then push right side to stack
        if p + 1 < h:
            top = top + 1
            stack[top] = p + 1
            top = top + 1
            stack[top] = h

参考链接：
Quicksort - Algorithms
三种快排及四种优化方式