python实现快速排序的示例(二分法思想)

yipeiwu_com5年前Python基础

本文介绍了python实现快速排序的示例(二分法思想),分享给大家,具体如下:

实现思路

将所需要的数字存入一个列表中

1.首先,设置将最左侧的那个数设置为基准数,在列表中索引为0
2.然后设置两个移动位(用于比较),分别为最左边和最右边
3.然后最右边那位向左移寻找比基准数小的那一位,最右边那位则从左向右寻找比基准数大的那一位
4.再后,将找到的两位对应的数字替换,继续执行3,直到两个移动位相遇,把基准为替换到相遇的那一位
5.最后,将列表以基准数那一位一分为二切开,左边和右边部分继续执行上述1-4步,直到没有比较数为止(也就是一个数),排序完成。

看下图你就明白了:

实现代码

# coding: utf-8
# 快速排序,利用二分思想实现
def quick_sort(list, left, right):
  if left > right:
    return
  temp = list[left]
  i = left
  j = right
  while i != j:
    # 先从右向左寻找
    while list[j] >= temp and i < j:
      j -= 1
    # 再从左向右寻找
    while list[i] <= temp and i < j:
      i += 1
    if i < j:
      t = list[i]
      list[i] = list[j]
      list[j] = t
  # 基准数替换
  list[left] = list[i]
  list[i] = temp
  # 递归调用
  quick_sort(list, left, i - 1)
  quick_sort(list, i + 1, right)

while True:
  list = []
  try:
    num = int(input('你想比较几个数?\n'))
  except ValueError:
    continue
  for k in range(num):
    a = int(input('请输入第' + str(k+1) + '个数:\n'))
    list.append(a)
  quick_sort(list, 0, num-1)
  print('排序结果为:')
  for l in range(len(list)):
    print(list[l], end=' ')
  print()

快速排序比较冒泡排序效率要高得多~

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

django使用xadmin的全局配置详解

django使用xadmin的全局配置详解

这篇主要写一些xadmin一些基础的全局设置 主题设置 首先需要在创建好的app中新建一个adminx.py的文件,然后添加代码 # _*_ coding: utf-8 _*_ i...

Python实现SVN的目录周期性备份实例

本文实例讲述了Python实现SVN的目录周期性备份方法。分享给大家供大家参考。具体如下: 起因:今天用SVN时,不小心把远程SVN服务器上的目录删掉了,然后在本地又手贱地还原了一下项目...

python二叉树的实现实例

树的定义树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机...

pycharm debug功能实现跳到循环末尾的方法

pycharm debug功能实现跳到循环末尾的方法

可以使用条件断点,如图,在断点上右键可以设置,条件自己输入,python语法: 以上这篇pycharm debug功能实现跳到循环末尾的方法就是小编分享给大家的全部内容了,希望能给大家...

python儿童学游戏编程知识点总结

python爬虫基本告一段落,琢磨搞点其他的,正好在网上看到一个帖子,一个外国13岁小朋友用python写的下棋程序,内容详细,也有意思,拿来练手。 13岁啊。。 我这年纪还在敲 dir...