首页 > 编程语言 > 详细

算法导论之快速排序

时间:2018-05-18 00:11:59      阅读:18      评论:0      收藏:0      [点我收藏+]

标签:链接   on()   for   aps   插入   函数   根据   none   一个   

快速排序

个人思绪很混乱, 建议直接看原文

简洁版:

技术分享图片
def PARTITION(A, p, r):
    x = A[r] # 锚点 主元{大于它放一边,小于的放另一边}
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1


def QUICKSORT(A, p, r):
    if p < r: #分治
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q-1)
        QUICKSORT(A, q+1, r)
View Code

 

注释版:

技术分享图片
import random

def PARTITION(A, p, r):
    x = A[r] # 锚点 主元{大于它放一边,小于的放另一边}
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1
"""partition函数体解析:
1. 将列表, 首元素下标, 尾元素下标传递进来
2. 设定基准值为尾元素
3. 遍历列表, 将列表内的每一项与基准值比较
4.  1. 如果当前元素小于基准值, 用指针记录下标
    2. 如果当前元素大于基准值, 过
    3. 如果当前元素小于基准值, 将指针后移一位, 将当前元素与指针现在所指的元素, 交换位置
5. 循环结束, 列表遍历完毕, 当前指针左侧的元素都比基准值小, 右侧的元素都比基准值大, 将基准值插入到此指针的位置
"""

"""
循环内部两个指针的解析:
1. 将尾元素设定为基准值
2. i指针默认设定的是j-1, 即: -1
3. j指针是根据循环的次数而变化, 从0到尾元素的下标
4. 1. 如果从开始遍历, 每一个元素都比基准值小的话, i指针只是记录了这些元素的位置, 
      并一直向后移动, i指针走过的位置, 都为小于基准值的元素
   2. 接着往后遍历, 如果j指针指向的元素大于基准值, 直接跳过
   3. 接着往后遍历, 如果j指针指向的元素小于基准值, 停下, 
      i指针还是停留在上一个比基准值小的元素的位置, 将i指针后移, i指向第一个比基准值大的元素, 将这个元素与j指向的元素交换位置
5. 1. 如果j指针指向的元素, 比基准值大, 过, i的值不变
   2. 如果j指针指向的元素, 比基准值小, i指针后移一位, 将i指针指向的元素与j指针指向的元素, 交换位置
6. 循环结束, 列表已遍历一遍, i指针左侧的元素都比基准值小, 右侧的元素都比基准值大, 将基准值插入到i指针位置处 
"""



def QUICKSORT(A, p, r):
    if p < r: #分治
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q-1)
        QUICKSORT(A, q+1, r)

"""QuickSort()函数体解析
1. 将传递进来的列表进行partition()函数分割, 
2. 分割为左列表[都比基准值小], 右列表[都比基准值大], 递归调用自己, 直到被分成n个列表长度为一的小列表
3. 结束第二步, 就代表列表排序完毕 
"""

if __name__ == "__main__":
    A = [i for i in range(1, 1000)]
    random.shuffle(A)
    print("洗牌之后的列表:" + str(A))
    QUICKSORT(A, 0, len(A)-1)
    print("快排之后的列表:" + str(A))
View Code

 

算法导论之快速排序

标签:链接   on()   for   aps   插入   函数   根据   none   一个   

原文:https://www.cnblogs.com/amou/p/9053928.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号