欢迎访问宙启技术站
智能推送

通过Python函数实现快速排序算法的方法。

发布时间:2023-06-13 03:26:43

快速排序算法是一种被广泛应用的排序算法,其核心思想是选取一个基准数将待排序数组分成两个部分,一部分是所有小于基准数的元素,另一部分是所有大于等于基准数的元素。然后分别对两部分进行递归排序,最终将数组排序完成。通过Python编程语言可以很方便地实现快速排序算法。

快速排序的核心函数是partition(),该函数旨在将待排序数组分成两个部分。具体实现过程如下:

1. 选取数组中的一个数作为基准数,通常是选取 个数。

2. 从右往左遍历数组,找到 个小于基准数的数,将其放入数组左侧。

3. 从左往右遍历数组,找到 个大于基准数的数,将其放入数组右侧。

4. 继续重复以上两个步骤,直到左右两个指针相遇。此时将基准数放入相遇位置,左侧数组为所有小于基准数的元素,右侧数组为所有大于等于基准数的元素。

快速排序的递归调用实现也比较简单,分别对左侧数组和右侧数组进行排序,直到数组长度为1或0时返回。

下面是使用Python实现快速排序算法的完整代码:

def partition(arr, low, high):
    i = (low - 1)
    pivot = arr[high]

    for j in range(low, high):
        if arr[j] < pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)


def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)


arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr, 0, n - 1)
print("排序后的数组:")
for i in range(n):
    print(f"{arr[i]} ")

在上面的实现中,partition()函数用于分割数组,quickSort()函数用于递归调用。

可以通过传入需要排序的任意数组来测试上述代码,并将输出的排序结果与预期的结果进行比较。