快速排序是利用分而治之的思想,算法的描叙看起来很容易让人理解,但想通过代码来高效的实现却不容易,主要是要考虑高效, 不能使用instert, 而应该使用在原地交换元素的方法来代替插入。从插入排序算法的实现就可以看出这点。

可以参考:数据结构(下) 邓俊辉教授 清华大学
快速排序

要实现选取一个基准数(key),比它大的都在它的右边,比它小的都在它的左边,
通常选取数组第一个元素为基准数,把它存到一个变量里面。
有两个指针,left指针初始指上数组头部, right指针初始指上数组尾部, 从数组前后两处开始比较,若尾部的元素比key大,则hight指针往中间跳一格(减去1),若比key小,则把right指针指上的元素存放在left指针的指向的位置
然后左边也如此,
最后左右指针到达同一位置, 把key 放到指针处,
文字过于难描述, 建议看邓俊辉教授的视频。

具体代码实现:

l = [4,5,3,2,8]


def quick_sort(lists, left, right):
    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[right] = key
    quick_sort(lists, low, left-1)
    quick_sort(lists, left+1, high)
    return lists

quick_sort(l, 0 , len(l)-1)

print(l)

快速排序简单版本

此版本比上版本会多占一点内存空间
l = [3, 1, 9, 4, 2, 8, 5, 7]


def ks_sort(l):
    if len(l) < 2:
        return l
    else:
        st = l[0]
        max_l = []
        min_l = []
        for i in l[1:]:
            if i > st:
                max_l.append(i)
            else:
                min_l.append(i)

        return ks_sort(min_l) + [st] + ks_sort(max_l)

print(ks_sort(l))

标签: none

添加新评论