排序方法——快速排序
2021-06-29 11:06
标签：.com 子序列 交换 python print amp 迭代 src 快速排序 快速排序：又称为划分交换排序，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 步骤： 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。 排序方法——快速排序 标签：.com 子序列 交换 python print amp 迭代 src 快速排序 原文地址：https://www.cnblogs.com/peiyanh/p/9646417.html
快速排序分析
function quick_sort(array, start, end){
// 数组长度为0和1退出
if(end start){
return
}
// 设置一个基准数
let mid = array[start]
// 向右的游标
let low = start
// 向左的游标
let high = end
// 当low=>high时退出循环
while(low high){
// 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
while(low = mid){
high -= 1
}
// 将high指向的元素放到low的位置上
array[low] = array[high]
// 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while(array[low] high){
low += 1
}
// 将low指向的元素放到high的位置上
array[high] = array[low]
}
// 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
array[low] = mid
// 对基准元素左边的子序列进行快速排序
quick_sort(array, start, low-1)
// 对基准元素右边的子序列进行快速排序
quick_sort(array, low+1, end)
}
let arr = [54,26,93,17,77,31,44,55,20];
let len = arr.length - 1;
quick_sort(arr, 0, len)
console.log(arr) // [ 17, 20, 26, 31, 44, 54, 55, 77, 93 ]
# python
def quick_sort(alist, start, end):
"""快速排序"""
# 递归的退出条件
if start >= end:
return
# 设定起始元素为要寻找位置的基准元素
mid = alist[start]
# low为序列左边的由左向右移动的游标
low = start
# high为序列右边的由右向左移动的游标
high = end
while low high:
# 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
while low = mid:
high -= 1
# 将high指向的元素放到low的位置上
alist[low] = alist[high]
# 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while low mid:
low += 1
# 将low指向的元素放到high的位置上
alist[high] = alist[low]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
alist[low] = mid
# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low-1)
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low+1, end)
alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)
快速排序演示
上一篇：排序方法——插入排序