摘要
Title: 785. 快速排序
Tag: 快速排序
Memory Limit: 64 MB
Time Limit: 1000 ms

785. 快速排序

题意

给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
思路
- 三个步骤
  - 找轴点
  - 调整范围
  - 递归左右两端
- 核心思想
  - 分治

代码

带注释版

注意，模板背过就好，别瞎改

'''
Author: NEFU AB-IN
Date: 2022-02-16 14:57:13
FilePath: \ACM\Acwing\785.py
LastEditTime: 2022-02-16 15:09:52
'''

a = []


def quicksort(l, r):
    if l >= r: #当区间只剩0或1个元素时返回
        return
    pivot = a[l + r >> 1] #确定轴点
    i, j = l - 1, r + 1 #确定两个指针，分别指向区间外，因为等会是先移动，再判断
    while i < j:
        while True:
            i += 1
            if a[i] >= pivot: #直到a[i]比轴点的数大，才停下来
                break
        while True:
            j -= 1
            if a[j] <= pivot:
                break
        if i < j: #如果符合i在左，j在右，就交换
            a[i], a[j] = a[j], a[i]
    quicksort(l, j) # 往左分治
    quicksort(j + 1, r) #往右分治


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    quicksort(0, n - 1)
    for i in a:
        print(i, end=" ")

无注释版

'''
Author: NEFU AB-IN
Date: 2022-02-16 14:57:13
FilePath: \ACM\Acwing\785.py
LastEditTime: 2022-02-16 15:09:52
'''

a = []


def quicksort(l, r):
    if l >= r:
        return
    pivot = a[l + r >> 1]
    i, j = l - 1, r + 1
    while i < j:
        while True:
            i += 1
            if a[i] >= pivot:
                break
        while True:
            j -= 1
            if a[j] <= pivot:
                break
        if i < j:
            a[i], a[j] = a[j], a[i]
    quicksort(l, j)
    quicksort(j + 1, r)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    quicksort(0, n - 1)
    for i in a:
        print(i, end=" ")

785. 快速排序

题意

思路

代码