实现快速排序算法的步骤和技巧

快速排序算法步骤

• Step 1：从数列中挑出一个元素，称为 "基准"（pivot）；
• Step 2：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• Step 3：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

快速排序算法技巧

• 第一技巧是选择一个合适的基准数，这可以有效地减少递归次数，提高排序的效率。一般选取数列的第一个数或一个数作为基准数，或者随机选择一个数作为基准数。
• 第二技巧是在划分子序列时，尽量保证子序列的大小接近，这样可以尽量减少不必要的递归次数，提高算法的效率。
• 第三技巧是在分区操作时，可以使用指针交换法，这样可以尽量减少数据的移动次数，提高算法的效率。

快速排序算法实现

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([3,6,8,10,1,2,1]))