您现在的位置是：首页 > Python

当前栏目

快速排序（python）

Python 排序

2023-03-02 10:31:57 时间

# 前言 #

基于前面介绍的桶排序和冒泡排序的缺点，我们提出了快速排序，快速排序是以首个数字作为基准，将整个输入分为两部分，左边小于这个基准，右边大于这个基准；重复操作这个，就可以根据这个基准不断进行划分输入数据，最终会实现分类的功能

一趟快速排序的算法是：

1）设置两个变量i、j，[排序][Link 1]开始的时候：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-完成的时候，此时令循环结束）。

# 代码实现 #

1 def quicksort(array, start, end):
      2     key = array[start]
      3     i, j = start, end
      4     if start >= end:
      5         return
      6     while i != j:
      7         # 找到右边第一个小于基准的数
      8         while (array[j]>=key) and (i<j):
      9             j -= 1
     10         # 找到左边第一个大于基准的数
     11         # i += 1
     12         while (array[i]<=key) and (i<j):
     13             i += 1
     14         # 如果找到了那么就进行交换
     15         if i < j:
     16             temp = array[j]
     17             array[j] = array[i]
     18             array[i] = temp
     19 
     20     # 结束之后将基准与中间值进行交换
     21     temp = array[start]
     22     array[start] = array[i]
     23     array[i] = temp
     24     print(array)
     25     quicksort(array, start, i-1)
     26     quicksort(array, i+1, end)
     27 
     28 
     29 if __name__ == '__main__':
     30     array = [6, 33, 5, 6, 4, 6, 2, 8, 3]
     31     quicksort(array, 0, len(array)-1)
     32     print(array)
    ~

快速排序在每次交换的过程中不会向冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大得多了，因此总的比较和交换的次数就变少了，速度自然就提高了；当然在最坏的情况下，仍然是相邻的两个数进行交换，因此快速排序的最坏最坏时间复杂度和冒泡排序是一样的，都是O(N\*2)，它的平均时间复杂度是O(NlogN)

[Link 1]: http://baike.baidu.com/view/58783.htm

猜你喜欢

【统计学基础】从可视化到统计检验，比较两个或多个变量分布的方法总结
PyTorch自然语言处理入门与实战
说说 Spring 定时任务如何大规模企业级运用
微服务的版本号要怎么设计？
家里已给全款买房，2023 届秋招拿了一堆 offer ，如何选择？？
软件开发入门教程网之TypeScript 声明文件
唱歌就能画一幅图像？ #whisper-to-stable-diffusion
Python 一行代码算出每个省面积的神器—Geopandas
免费的 AI 动作捕捉工具 #Rokoko Video
软件开发入门教程网站之TypeScript Array(数组)
软件开发入门教程网之TypeScript 基础语法
AIGC + 任意应用情景组合，从技术层面给了大家体验不同领域的创作的机会
软件开发入门教程网之TypeScript 类
微软靠OpenAI反杀Google？想多了
虹科方案|数据中心虚拟化和 HK-ATTO 产品—旨在协同工作的端到端解决方案
软件开发入门教程网之Git 基本操作
耗时3天，做了一个，不纯粹的机器学习网站
性能测试|JMeter线程组设置
性能测试|JMeter取样器（一）
软件开发入门教程网之Git 分支管理

zl程序教程

当前栏目

快速排序（python）

相关文章