跳至正文
View Categories

< 1 min read

快速排序算法 #

  1. 快速排序算法介绍
  2. 快速排序算法原理
  3. 快速排序算法的实现

收获 #

学完本节内容，可以初步理解并掌握快速排序算法。

快速排序算法介绍 #

快速排序(Quick Sort)是一种效率很高的排序算法，是对冒泡排序的一种改进排序算法。
快速排序首先任意选取一个数据(通常选待排序列表中的第一个数)作为基准数据，将待排序列表中的数据分割成独立的两部分，所有比基准数据小的数都放到它左边，所有比基准数据大的数都放到它右边，此时基准数据排序完成，第一轮快速排序完成。然后再按此方法对两部分的数据分别进行快速排序，整个排序过程可以递归进行，直到被分割的数据只有一个或零个时，递归结束，列表排序完成。
快速排序的名字起得简单直接，因为这种排序算法速度快，效率高，是处理大数据最快的排序算法之一。

快速排序算法原理 #

快速排序的原理如下：

  1. 从待排序列表中选取一个基准数据base(通常选取第一个数据)。然后设置两个游标 left 和 right，分别指向列表的起始数据和末尾数据。将游标right的数据与基准数据比较，如果大于或等于基准数据，则right往左移动。
    base=list[0]
    while list[right]>=base:
        right-=1
  1. 当游标right的数据小于基准数据时，right停止移动，将游标right指向的数据赋值给游标left。然后将游标left的数据与基准数据比较，如果小于基准数据，则left往右移动
    if list[right]<base:
        list[left]=list[right]
  1. 当游标left的数据大于或等于基准数据时，left停止移动，将游标left指向的数据赋值给游标rigt。
  2. 重复1，2，3步骤操作。当left与right相遇时，移动结束。将基准数据base赋值给相遇的位置。用基准数据进行分割操作后，基准数据的位置就是它最终排序完成的位置，第一轮排序完成。
    list[left]=base
  1. 递归地对左右两个部分的数据进行快速排序。即在每个子列表中，选取基准，分割数据。直到被分割的数据只有一个或零个时，列表排序完成。

快速排序算法的实现 #

python实现代码如下：

def quicksort(a,start,end):
    if start>=end:#当子序列包含一个或0个点的时候，停止排序，认为排序完成
        return
    base=a[start]#选取一个种子点,一般从最左边开始
    left,right=start,end
    while left<right:#第一次能否进入循环的判断
        while a[right]>=base and left<right:#进入循环后，right值在不断变化，需要重新添加跳出循环的条件（and left<right）
            right-=1
        a[left]=a[right]#当右指针检索到小于base的数值时，暂停检索，并将其数值赋值给左指针位置的数值
        while a[left]<=base and left<right:
            left+=1
        a[right]=a[left]#当左指针检索到大于base的数值时，暂停检索，并将其数值赋值给右指针位置的数值
    a[left]=base#当left=right时，把base插入left位置，完成第一轮排序
    #以下用递归思想依次对子序列进行快速排序（重复上述操作）
    quicksort(a,start,left-1)
    quicksort(a,left+1,end)

if __name__=='__main__':
    a=[10,17,50,7,30,15,5,38,21]
    quicksort(a,0,len(a)-1)
    print(a)

小结 #

理解并掌握快速排序算法的原理
掌握快速排序的代码实现

习题 #

  1. 习题1：画出快速排序算法的流程图
  2. 习题2：使用快速排序算法，对列表[10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]进行升序排列
What are your Feelings