Python实现快速排序算法及去重的快速排序的简单示例

快速排序是一种常用的排序算法，它的时间复杂度为O(nlogn)，效率较高。在本文中，我们将介绍如何使用Python实现快速排序算法及去重的快速排序。我们分为以下几个步骤：

1. 快速排序算法的实现
2. 去重的快速排序算法的实现
3. 示例说明

步骤1：快速排序算法的实现

快速排序算法的实现过程如下：

1. 选择一个基准元素，通常选择第一个元素或最后一个元素。
2. 将所有小于基准元素的元素移到基准元素的左边，将所有大于基准元素的元素移到基准元素的右边。
3. 对基准元素的左边和右边分别进行递归排序。

我们可以使用以下代码实现快速排序算法：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort(left) + [pivot] + quick_sort(right)

在这个示例中，我们首先定义了一个名为quick_sort的函数，它接受一个参数arr，表示待排序的数组。如果数组长度小于等于1，则直接返回数组。否则，我们选择第一个元素作为准元素pivot，然后将所有小于pivot的元素移到left数组中，将所有大于pivot的元素移到right数组中。最后，我们递归对left和right数组进行排序，并将它们与pivot合并起来。

步骤2：去重的快速排序算法的实现

去重的快速排序算法的实现过程与快速排序算法类似，是在处理相等元素时需要特殊处理。我们可以使用以下代码实现去重的快速排序算法：

def quick_sort_unique(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        elif arr[i] > pivot:
            right.append(arr[i])
        else:
            pivot_count = arr.count(pivot)
            if pivot_count == 1:
                left.append(arr[i])
            else:
                pivot_count -= 1
    return quick_sort_unique(left) + [pivot] * pivot_count + quick_sort_unique(right)

在这个示例中，我们首先定义了一个名为quick_sort_unique的函数，它接受一个参数arr，表示待排序的数组。如果数组长度小于等于1，则直接数组。否则，我们选择第一个元素作为基准元素pivot，然后将所有小于pivot的元素移到left数组中，将所有大于pivot的元素移到right数组中。如果元素等于pivot，则需要特殊处理。如果pivot只出现了一次，则将该元素移到数组中。否则，我们将pivot_count减1，并将该元素留在原数组中。最后，我们递归对left和right数组进行排序，并将它们与pivot合并起来。

步骤3：示例说明

示例1：使用快速排序算法对数组进行排序

在这个示例中，我们将使用快速排序算法对一个数组进行排序。我们可以使用以下代码进行排序：

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = quick_sort(arr)
print(sorted_arr)

在这个示例中，我们首先定义了一个名为arr的数组，它包含了一些整数。然后，我们调用quick_sort函数对该进行排序，并将排序后的结果打印出来。

示例2：使用去重的快速排序算法对数组进行排序

在这个示例中，我们将使用去重的快速排序算法对一个数组进行排序。我们可以使用以下代码进行排序：

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = quick_sort_unique(arr)
print(sorted_arr)

在这个示例中，我们首先定义了一个名为arr的数组，它包含了一些整数。然后，我们调用quick_sort_unique函数对该数组进行排序，并将排序后的结果打印出来。由于去重快速排序算法会去除重复元素，因此排序后的结果中不会包含重复元素。