python 实现快速排序

Enlightenment 发布于2019-07-31 11:18 / 2836人阅读

摘要：排序算法之快速排序快速排序快排的思想首先任意选取一个数据通常选用数组的第一个数作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

Python排序算法之快速排序
快速排序（quickSort）
快排的思想：首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

百度百科给的算法：

一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

时间复杂度：O(nlgn)

# QuickSort by Alvin


def QuickSort(myList, start, end):
    # 判断low是否小于high,如果为false,直接返回
    if start < end:
        i, j = start, end
        # 设置基准数
        base = myList[i]

        while i < j:
            # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
            while (i < j) and (myList[j] >= base):
                j = j - 1

            # 同样的方式比较前半区
            while (i < j) and (myList[i] <= base):
                i = i + 1

            myList[i], myList[j] = myList[j], myList[i]
        # 做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base
        myList[i] = base

        # 递归前后半区
        QuickSort(myList, start, i - 1)
        QuickSort(myList, j + 1, end)
    return myList


myList = [49, 38, 65, 97, 76, 13, 27, 49]
print("Quick Sort: ")
QuickSort(myList, 0, len(myList)-1)
print(myList)

云服务器 GPU云服务器 python快速排序快速排序快速排序函数快速排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44983.html

Github标星2w+，热榜第一，如何用Python实现所有算法

摘要：归并排序归并排序，或，是创建在归并操作上的一种有效的排序算法，效率为大符号。以此类推，直到所有元素均排序完毕。与快速排序一样都由托尼霍尔提出的，因而也被称为霍尔选择算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);编译：周素云、蒋宝尚学会了Python基础知识，想进阶一下，那就来点算法吧！毕竟编程语言只...

zxhaaa 2019-07-31 10:23 评论0 收藏0
python-八大算法

摘要：排序算法总结排序算法平均时间复杂度冒泡排序选择排序插入排序希尔排序快速排序归并排序堆排序基数排序一冒泡排序基本思想两个数比较大小，较大的数下沉，较小的数冒起来。排序算法总结排序算法平均时间复杂度冒泡排序O(n2) 选择排序O(n2) 插入排序O(n2) 希尔排序O(n1.5) 快速排序O(N*logN) 归并排序O(N*logN) 堆排序O(N*logN) 基数排序O(d(n+...

aboutU 2019-07-30 16:20 评论0 收藏0
八大排序算法的Python实现

摘要：是稳定的排序方法。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。算法实现选择排序堆排序描述堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法，它是选择排序的一种。 1、插入排序描述插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定...

princekin 2019-07-24 18:09 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

wuyumin 2019-07-30 15:33 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

Carson 2019-08-26 11:32 评论0 收藏0