赞
踩
目录
快速排序(Quicksort),又称划分交换排序(partition-exchangesort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程递归进行,以此达到整个数据变成有序序列。
第一步:在数组中选一个基准元素(通常为数组第一个)。
第二步:将数组中小于基准数的数据移到基准数左边,大于基准数的移到右边。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
第三步:对于基准数左、右两边的数组,不断重复以上两个过程,直到每个子集只有一个元素,即为全部有序。
- #!/usr/bin/python3
- # -*- coding: utf-8 -*-
-
-
- def quick_sort(data: list[int], first: int, last:int) -> None:
- if first >= last:
- return
- low = first
- high = last
- mid = data[low]
- while low < high:
- # 右指针移动
- while low < high and data[high] >= mid:
- high -= 1
- data[low] = data[high]
- # low += 1
-
- # 左指针右移
- while low < high and data[low] < mid:
- low += 1
- data[high] = data[low]
- # high -= 1
-
- data[low] = mid
- print(data)
- # 递归快速排序
- quick_sort(data, first, low-1)
- quick_sort(data, low+1, last)
-
-
- def main():
- data = [54, 26, 93, 17, 77, 31, 45, 55, 20]
- # data = [3,1,5,2,1,0]
- # data = [7, 31, 23, 13, 35, 3]
- print(f"排序前:{data}")
- quick_sort(data, 0, len(data)-1)
- print(f"排序后:{data}")
-
-
- if __name__ == '__main__':
- main()
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。