实现思路
将所需要的数字存入一个列表中
首先, 设置将最左侧的那个数设置为基准数, 在列表中索引为 0
然后设置两个移动位 (用于比较), 分别为最左边和最右边
然后最右边那位向左移寻找比基准数小的那一位, 最右边那位则从左向右寻找比基准数大的那一位
再后, 将找到的两位对应的数字替换, 继续执行 3, 直到两个移动位相遇, 把基准为替换到相遇的那一位
最后, 将列表以基准数那一位一分为二切开, 左边和右边部分继续执行上述 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()
快速排序比较冒泡排序效率要高得多~
来源: http://www.bubuko.com/infodetail-2524437.html