大多数编程语言都自带用于数组排序的函数,其中很多采用的都是快速排序，快速排序依赖于一个名为分区的概念
分区：从数组随机选取一个值，以其为轴，将比它小的值放到他的左边，比它大的值放到它的右边
假设有一个数组 0 5 2 1 6 3
选取最右边的元素为轴(从技术来说，选取任何值作为轴都是可以的)，以排除轴元素的子数组的最左端元素为左指针，以排除轴元素的子数组的最右端元素为右指针
0 5 2 1 6 3
↑左指针 ↑右指针 ↑轴
分区步骤
(1) 左指针逐个格子向右移动，当遇到大于或等于轴的值时，就停下来
(2) 右指针逐个格子向左移动，当遇到小于或等于轴的值时，就停下来
(3) 将两指针所指的值交换位置
(4) 重复上述步骤，直至两指针重合，或左指针移动到右指针的右边
(5) 将轴与左指针所指的值交换位置
class SortableArray: def __init__(self, array): self.array = array def partition(self, left_pointer, right_pointer): # 总是选取数组最右端的值作为轴 pivot_position = right_pointer pivot = self.array[pivot_position] # 将右指针指向轴的左边一格(因为我们要以排除轴元素的子数组的最左端元素为左指针，最右端元素为右指针) right_pointer -= 1 # 重复循环，直至两指针重合，或左指针移动到右指针的右边 while True: # 左指针逐个格子向右移动，当遇到大于或等于轴的值时，就停下来 while self.array[left_pointer] < pivot: left_pointer += 1 # 右指针逐个格子向左移动，当遇到小于或等于轴的值时，就停下来 while self.array[right_pointer] > pivot: right_pointer -= 1 # 如果两指针重合，或左指针移动到右指针的右边，退出循环 if left_pointer >= right_pointer: break # 否则 将两指针所指的值交换位置，将会继续循环 else: self.swap(left_pointer, right_pointer) # 最后将左指针的值与轴的值交换 self.swap(left_pointer, pivot_position) # 返回左指针(此时的左指针指向的值是原来轴的值)，将用于后面的再分区 return left_pointer # 自定义交换函数 def swap(self, pointer_01, pointer_02): temp_value = self.array[pointer_01] self.array[pointer_01] = self.array[pointer_02] self.array[pointer_02] = temp_value if __name__ == '__main__': arr = [0, 5, 2, 1, 6, 3] quick_sort = SortableArray(arr) quick_sort.partition(0, len(arr)-1) print(quick_sort.array)
快速排序
快速排序严重依赖于分区，运作方式如下所示
(1) 把数组分区。使轴到正确的位置上去
(2) 对轴左右的两个子数组递归地重复第1、2步，也就是说，两个子数组都各自分区，并形成各自的轴以及轴分隔的更小的子数组。然后也对这些子数组分区，以此类推
(3) 当分出的子数组长度为0或1时，即达到基准情形，无需进一步操作
class SortableArray: def __init__(self, array): self.array = array def partition(self, left_pointer, right_pointer): # 总是选取数组最右端的值作为轴 pivot_position = right_pointer pivot = self.array[pivot_position] # 将右指针指向轴的左边一格(因为我们要以排除轴元素的子数组的最左端元素为左指针，最右端元素为右指针) right_pointer -= 1 # 重复循环，直至两指针重合，或左指针移动到右指针的右边 while True: # 左指针逐个格子向右移动，当遇到大于或等于轴的值时，就停下来 while self.array[left_pointer] < pivot: left_pointer += 1 # 右指针逐个格子向左移动，当遇到小于或等于轴的值时，就停下来 while self.array[right_pointer] > pivot: right_pointer -= 1 # 如果两指针重合，或左指针移动到右指针的右边，退出循环 if left_pointer >= right_pointer: break # 否则 将两指针所指的值交换位置，将会继续循环 else: self.swap(left_pointer, right_pointer) # 最后将左指针的值与轴的值交换 self.swap(left_pointer, pivot_position) # 返回左指针(此时的左指针指向的值是原来轴的值)，将用于后面的再分区 return left_pointer def quicksort(self, left_index, right_index): # 基准情形: 分出的子数组长度为0或1 if right_index - left_index <= 0: return # 将数组分成两部分，并返回分隔所用的轴的索引 pivot_position = self.partition(left_index, right_index) # 对轴左侧的部分递归调用quicksort self.quicksort(left_index, pivot_position-1) # 对轴右侧的部分递归调用quicksort self.quicksort(pivot_position+1, right_index) # 自定义交换函数 def swap(self, pointer_01, pointer_02): temp_value = self.array[pointer_01] self.array[pointer_01] = self.array[pointer_02] self.array[pointer_02] = temp_value if __name__ == '__main__': arr = [0, 5, 2, 1, 6, 3, 4, 8, 2, 3, 9] quick_sort = SortableArray(arr) quick_sort.quicksort(0, len(arr)-1) print(quick_sort.array)
快速选择
快速选择的优势在于不需要把整个数组都排序就可以找到正确位置的值，快速选择需要对数组分区，这跟快速排序类似，可以想象成是快速排序和二分查找的结合
class SortableArray: def __init__(self, array): self.array = array def partition(self, left_pointer, right_pointer): # 总是选取数组最右端的值作为轴 pivot_position = right_pointer pivot = self.array[pivot_position] # 将右指针指向轴的左边一格(因为我们要以排除轴元素的子数组的最左端元素为左指针，最右端元素为右指针) right_pointer -= 1 # 重复循环，直至两指针重合，或左指针移动到右指针的右边 while True: # 左指针逐个格子向右移动，当遇到大于或等于轴的值时，就停下来 while self.array[left_pointer] < pivot: left_pointer += 1 # 右指针逐个格子向左移动，当遇到小于或等于轴的值时，就停下来 while self.array[right_pointer] > pivot: right_pointer -= 1 # 如果两指针重合，或左指针移动到右指针的右边，退出循环 if left_pointer >= right_pointer: break # 否则 将两指针所指的值交换位置，将会继续循环 else: self.swap(left_pointer, right_pointer) # 最后将左指针的值与轴的值交换 self.swap(left_pointer, pivot_position) # 返回左指针(此时的左指针指向的值是原来轴的值)，将用于后面的再分区 return left_pointer def quicksort(self, left_index, right_index): # 基准情形: 分出的子数组长度为0或1 if right_index - left_index <= 0: return # 将数组分成两部分，并返回分隔所用的轴的索引 pivot_position = self.partition(left_index, right_index) # 对轴左侧的部分递归调用quicksort self.quicksort(left_index, pivot_position-1) # 对轴右侧的部分递归调用quicksort self.quicksort(pivot_position+1, right_index) # 自定义交换函数 def swap(self, pointer_01, pointer_02): temp_value = self.array[pointer_01] self.array[pointer_01] = self.array[pointer_02] self.array[pointer_02] = temp_value # 快速选择 def quickselect(self, kth_lowest_value, left_index, right_index): # 当子数组只剩一个格子:即达到基准情形 # 此时我们就可以找到所要找的值了 if right_index - left_index <= 0: return self.array[left_index] # 将数组分成两部分，并返回分隔所用的轴的索引 pivot_position = self.partition(left_index, right_index) # 如果要找的值的索引kth_lowest_value比轴的索引小，则只需继续查找轴的左部分子数组，因为要查找的值肯定不会出现在轴的右部分子数组 if kth_lowest_value < pivot_position: # 增加return将返回值层层返回到最外层完美解决了递归返回值为None的问题 return self.quickselect(kth_lowest_value, left_index, pivot_position-1) # 如果要找的值的索引kth_lowest_value比轴的索引大，则只需继续查找轴的右部分子数组，因为要查找的值肯定不会出现在轴的左部分子数组 elif kth_lowest_value > pivot_position: # 增加return将返回值层层返回到最外层完美解决了递归返回值为None的问题 return self.quickselect(kth_lowest_value, pivot_position+1, right_index) # 至此kth_lowest_value只会等于pivot_position # 如果分区后返回的轴的索引等于kth_lowest_value，那么这个轴的值就是我们要找的值 else: return self.array[pivot_position] if __name__ == '__main__': arr = [0, 5, 2, 1, 6, 3, 4, 8, 2, 3, 9] quick_sort = SortableArray(arr) kth_value = quick_sort.quickselect(5, 0, len(arr)-1) print(kth_value) quick_sort.quicksort(0, len(arr)-1) print(quick_sort.array)