排序算法之快速排序
2020-12-13 03:56
标签：就是 dom col 思路 http while import 元素 span 一、快速排序的思路 关键点 如何完成对元素E的归位，元素E将序列分成左右两部分，左边的部分比E元素小，右边的部分比E元素大，这样左边和右边排序后，中间的E元素位置未变，而且左边和右边使用同样的归位方式进行排序。 （1）加入现在有一列数据需要排序： （2）快排先取出第一个数： （3）此时第一个数的位置是空的，就需要从右边将小于4的数取出放置在左侧的空位置 （4）右侧的空位置就循环左侧的数，将大于4的数填在右侧的空位置 （5）然后右侧继续循环填补左侧的空位置，当左侧与右侧的位置相同时，这就是取出左侧第一个数4的位置 这样就完成了一次归位，同理左侧与右侧都用相同的方式进行归位，完成排序。 二、实现 三、扩展 快排中隐含的问题就是时间复杂度最坏情况就是o(n2)，一般情况是o(nlogn)，当出现序列中的元素全部是降序，但是你要进行升序排列时，会出现这种情况，那么，如何解决这种问题呢？可以在选取temp元素时，随机的选一个元素与temp元素进行交换，避免这类情况的发生。 上面都是按照升序排列的，如果需要进行降序排列，只需要修改两个地方即可： 排序算法之快速排序 标签：就是 dom col 思路 http while import 元素 span 原文地址：https://www.cnblogs.com/shenjianping/p/11096853.html
def partition(li,left,right):
temp=li[left]#表示从左边取出的第一个元素
while leftright:
while left and li[right]>=temp: #从右边开始循环，寻找比归位元素小的元素放到左边空的位置
right-=1
li[left]=li[right]
while left
import random
def partition(li, left, right):
swap = random.randint(left, right) # 产生随机的位置索引
li[swap], li[left] = li[left], li[swap] # 将第一个元素与随即产生的元素进行交换
temp = li[left] # 表示从左边取出的第一个元素
while left right:
while left and li[right] >= temp: # 从右边开始循环，寻找比归位元素小的元素放到左边空的位置
right -= 1
li[left] = li[right]
while left and li[left] # 从左边开始循环，寻找比归位元素大的元素放到右边空的位置
left += 1
li[right] = li[left]
li[left] = temp # 跳出循环说明左右两个位置重合了left=right，此时放temp元素
return left
def quickSort(li, left, right):
if left # 至少两个元素才能进行快排
mid = partition(li, left, right) # 返回归位元素的位置
quickSort(li, left, mid - 1) # 左边元素进行排序
quickSort(li, mid + 1, right) # 右边元素进行排序
li = [2, 9, 5, 7, 6, 12, 25, 48, 36]
quickSort(li, 0, len(li) - 1)
print(li) # [2, 5, 6, 7, 9, 12, 25, 36, 48]
...
while left right:
while left and li[right] temp: # 从右边开始循环，寻找比归位元素大的元素放到左边空的位置
right -= 1
li[left] = li[right]
while left and li[left] >= temp: # 从左边开始循环，寻找比归位元素小的元素放到右边空的位置
left += 1
li[right] = li[left]
...