最好情况: 时间复杂度 O(nlog2n)
最坏情况: 逆序序列, 时间复杂度为 O(n2)
平均时间复杂度: O(nlogn)
空间复杂度: O(nlog2n)
稳定性: 不稳定
- array_test = [5, 9, 10, 6, 5, 26, 17, 4, 11, 8]
- def quick_sort(array, low, high):
- if low >= high:
- return
- key = array[low]
- start, end = low, high
- while low < high:
- while low < high and array[high] >= key:
- high -= 1
- if low < high:
- array[low] = array[high]
- low += 1
- while low < high and array[low] <= key:
- low += 1
- if low < high:
- array[high] = array[low]
- high -= 1
- array[low] = key
- quick_sort(array, start, low - 1)
- quick_sort(array, high + 1, end)
- return array
- print(quick_sort(array_test, 0, len(array_test) - 1))
输出:[4, 5, 5, 6, 8, 9, 10, 11, 17, 26]
来源: http://www.bubuko.com/infodetail-2514744.html