快速排序

发表于 分类于

快速排序

1. 介绍

快速排序是一种高效的排序算法，它采用“分而治之”的思想。其原理是：对于一组给定的记录，通过一趟排序后，将原序列分成两部分，其中前部分的所有记录均比后面部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

具体算法步骤如下：

(1) 分解: 将输入的序列array[m,…,n]划分成两个非空子序列array[m,…,k]和array[k+1,…,n]，使array[m,..,k]和array[k+1,…,n]，使array[m,…,k]中任一元素的值不大于array[k+1,…,n]中任一元素的值。

(2) 递归求解：通过递归调用快速排序算法分别对array[m,…,k]和array[k+1,…,n]进行排序。

(3) 合并: 由于对分解出的两个子序列的排序是就地进行的，所以在array[m,…k]和array[k+1,…,n]都是排好序后，不需要执行任何计算，array[m,…,n]就已排好序。

2. Python代码实现

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
# 如何进行快速排序
# 整体有序,基准左边或右边样本为空，比较次数多，最坏时间复杂度，例如基准最小，排序递增
# 最坏时间复杂度为O(n^2),最好时间复杂度为O(nlogn),平均时间复杂度为O(nlogn)
# 平均空间复杂度为O(nlogn)
def quick_sort(left,right,lists):
    if left > right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left <right and lists[right]>=key:
            right -= 1
        lists[left] = lists[right]
        while left <right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[left] = key
    quick_sort(low,left-1,lists)
    quick_sort(left+1,high,lists)
    return lists

if __name__ == "__main__":
    lists = [3,4,2,8,9,5,1]
    print("排序前序列为：",end="")
    for i in lists:
        print(i,end=" ")
    print("\n排序后序列为：",end="")
    for i in (quick_sort(0,len(lists)-1,lists)):
        print(i,end=" ")

3 参考资料

  1. 《Python程序员面试算法宝典》