python快排的三种写法
2021/12/25 17:37:27
本文主要是介绍python快排的三种写法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
# -*- encoding : utf-8 -*- # @Author : 日落了 # @ Motto : 天不生python,IT 万古如长夜 # @Time :2020/6/16-21:56 # @template : 快速排序 def quickSort(arr, start, end): if start >= end: return povit_index = sort3(arr, start, end) quickSort(arr, start, povit_index - 1) quickSort(arr, povit_index + 1, end) # java C++ C#的写法 def sort1(arr, start, end): # 直接使用start的话,第一个index的位置就发生了变化,需要保留第一个位置 left = start right = end pivot = arr[start] # 两个指针一起协作 所以使用到三个while while left < right: while left < right and arr[right] > pivot: right -= 1 while left < right and arr[left] <= pivot: left += 1 # 因为左边的都小于基准值 右边都大于基准值就行 temp = arr[left] arr[left] = arr[right] arr[right] = temp # 指针交换 temp = arr[left] arr[left] = arr[start] arr[start] = temp return left def sort3(array, start, end): left = start right = end base = array[start] while left < right: # 也是有顺序的 while left < right and array[right] > base: right -= 1 while left < right and array[left] <= base: left += 1 # 简化交换,但是注意与以往不同的是指针指向的内存没有发生改变 array[left], array[right] = array[right], array[left] # 为什么是arr[start]而不能用base,因为array[left] 就是base值,这样做会使得重复 array[left], array[start] = array[start], array[left] return left # 这种是可读性比较差的方法 结果:passed def sortf(array, start, end): if start >= end: return # 挖坑法 left = start right = end base = array[start] while left < right: while left < right and array[right] > base: right -= 1 array[left] = array[right] while left < right and array[left] <= base: left += 1 array[right] = array[left] array[right] = base sortf(array, start, left - 1) sortf(array, left + 1, end) # 挖坑法 结果 passed def sort4(array, start, end): left = start right = end base = array[start] while left < right: # 跟顺序有关 while left < right and array[right] > base: right -= 1 array[left] = array[right] while left < right and array[left] <= base: left += 1 array[right] = array[left] # 下面这样一步叫做挖个坑让标准值跳到里面去,所以不能使用array[start] array[left] = base return left if __name__ == '__main__': import random array = [random.randint(1, 1000) for i in range(5)] # 属于原地排队 直接 quickSort(array, 0, array.__len__() - 1) # sortf(array, 0, array.__len__() - 1) print(array)
这篇关于python快排的三种写法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04Python外包有哪些常见的主要库-icode9专业技术文章分享
- 2024-10-02基于深度学习的钢铁缺陷检测系统(yolov8、注意力机制、PyQt5界面、Python)
- 2024-10-01怎么用python搭建一个系统-icode9专业技术文章分享
- 2024-09-30Python基础入门教程
- 2024-09-30获取参数学习:Python中的基础教程
- 2024-09-30Python编程基础详解
- 2024-09-29点击加载学习:Python编程基础教程
- 2024-09-29数据科学五大Python前端库:第二部分
- 2024-09-27使用python 将ETH账户的资产打散
- 2024-09-26Python编程基础