快速排序算法Java、Python、Go和Rust四种代码实现

快速排序- 是最流行和最有效的排序算法之一。快速排序使用一个简单但强大的概念。该算法将数据集划分为更小的子集，对每个子集进行排序，并将结果组合成一个结构化的整体。但请注意，快速排序并不是一种稳定的排序算法。这意味着具有相同值的元素可以改变它们在结果集中的相对顺序

“分而治之”的思想就是将一个问题分成更小的子问题，解决它们，并将结果组合成整体问题的解决方案。在快速排序的情况下，这意味着选择一个项目作为“枢轴pivot”，将数据集分成两组（比“枢轴”更小和更大），对两组进行排序，并将它们组合成一个有序列表。

下面显示的Java算法对数组中提供的整数进行排序。

static void quickSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
 
    int high = arr.length - 1;
    quickSort(arr, 0, high);
}
 
static void quickSort(int[] arr, int begin, int end) {
    if (begin < end) {
        int pivotIndex = partition(arr, begin, end);
 
        quickSort(arr, begin, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, end);
    }
}
 
static int partition(int[] arr, int begin, int end) {
    int pivot = arr[end];
    int i = (begin - 1);
 
    for (int j = begin; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;
 
            int swapTemp = arr[i];
            arr[i] = arr[j];
            arr[j] = swapTemp;
        }
    }
 
    int swapTemp = arr[i + 1];
    arr[i + 1] = arr[end];
    arr[end] = swapTemp;
 
    return i + 1;
}

  • QuickSort()方法是用户的入口点。检查传递的数组不为空或长度为零，然后使用附加参数调用同一方法的版本。
  • 该方法实现了递归快速排序算法。
  • begin < end条件意味着我们正在排序的子数组包含多个元素。
  • 我们调用partition()方法来获取主元索引(pivotIndex)，然后递归地对两个子数组进行排序：从begin到pivotIndex -1和从pivotIndex + 1到end。
  • partition()方法确定给定子数组的主元索引 (pivotIndex)。
  • 它使用两个相互移动的指针（i 和 j），如果元素在轴上的位置错误，则交换元素。
  • 当循环结束时，它返回索引，该索引现在是轴在排序数组中的位置。

该算法的结果是，通过对数组进行递归划分和排序，轴左侧的所有元素都将变小，右侧的元素将变大。当每个子数组包含一个元素或为空时，算法终止。

优点：

  • 最佳平均时间复杂度： QuickSort的平均时间复杂度为O(n log n)，使其成为解决一般问题的最快排序算法之一。这意味着在大多数情况下，即使对于大型数据集，QuickSort 的运行速度也非常快。
  • 良好的缓存利用率： 与其他排序算法（例如合并排序或堆排序）相比， QuickSort显示出更好的 CPU 缓存利用率。这是由于参考局部性，这是将数据划分为更小的子集的结果。
  • 可扩展性： QuickSort对于大型数据集具有非常高的可扩展性和效率。它快速排序大量数据的能力使其在数据库和事务处理系统等工业应用中非常有用。
  • 枢轴选择的灵活性：能够选择不同的枢轴选择策略（例如第一个元素、最后一个元素、中位数、随机元素），使算法能够适应特定的输入数据要求，从而提高其在各种场景下的性能。
  • 适用于分布式数据： QuickSort对于分散（无序）或随机分布的数据特别有效，因为这种情况可以最大限度地降低算法最坏情况性能(O(n^2))的风险。

尽管快速排序算法有许多优点，但也必须注意潜在的缺点，例如：

  • 结构化数据问题，即最坏情况 O(n^2) 时间复杂度：在最坏情况下，当输入数据已经排序或几乎排序时（或者在主元选择不当的任何其他情况下），QuickSort 的时间复杂度退化为 O(n^2)。与 O(n log n) 的平均复杂度相比，效率要低得多。快速排序的最佳情况发生在主元将数据分成近似相等的两部分时，这保证了后续排序的效率。然而，对于已经部分或完全排序的数据，主元的选择可能会导致划分非常不均匀。例如，如果您通过透视从已排序集合的一端选择一个元素，则分割部分之一可能包含大部分元素，而另一个部分可能包含很少元素或不包含任何元素。这种情况会导致效率低下，因为算法必须对较大的部分进行更多的递归调用，这不是最优的。
  • 排序算法不稳定 当应用算法后相同输入元素的顺序可能发生变化时，排序算法被称为“不稳定”。换句话说，如果我们在原始数据集中有两个具有相同键值的元素A和B，并且排序算法改变了它们的相对位置，我们说它是一个不稳定的算法。在对整数进行排序的情况下，这并不重要 - 数字 1 始终是数字 1，无论我们将其写为 11 还是 11 但是，当我们对整数进行排序时，这可能很重要列出客户的姓名，例如，名单上的第一位是来自格但斯克的 Jan Kowalski，另一位是来自华沙的 Jan Kowalski。
  • 无法保证一致的性能：由于 QuickSort 的性能取决于输入数据和主元选择，因此很难保证跨应用程序的一致性能。在某些情况下，其他排序算法可能更可预测且更可靠。

快速排序– Java – Arrays.sort()
在 Java 世界中，由于内置的​​ Array.sort()函数，您通常不必自己实现排序算法。它自动使用快速排序算法，无需手动实现。

Python实现：

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        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 quicksort(left) + middle + quicksort(right)

# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = quicksort(my_list)
print("Sorted list:", sorted_list)

  • quicksort 函数是一个递归函数，使用快速排序算法对输入列表进行排序。
  • 它从列表中选择一个枢轴元素，将列表分为小于枢轴的元素、等于枢轴的元素和大于枢轴的元素。
  • 然后，函数递归地将快速排序算法应用于左右分区，并将结果连接起来。


Go实现

package main

import (
    "fmt"
)

func quicksort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    pivotIndex := partition(arr)

    quicksort(arr[:pivotIndex])
    quicksort(arr[pivotIndex+1:])

    return arr
}

func partition(arr []int) int {
    pivotIndex := len(arr) / 2
    arr[pivotIndex], arr[len(arr)-1] = arr[len(arr)-1], arr[pivotIndex]

    i := 0
    for j := 0; j < len(arr)-1; j++ {
        if arr[j] <= arr[len(arr)-1] {
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }

    arr[i], arr[len(arr)-1] = arr[len(arr)-1], arr[i]
    return i
}

func main() {
    mySlice := []int{64, 34, 25, 12, 22, 11, 90}
    sortedSlice := quicksort(mySlice)
    fmt.Println("Sorted slice:", sortedSlice)
}

  • quicksort 函数是一个递归函数，使用快速排序算法对输入片段进行就地排序。
  • partition 函数用于将切片分为两半，即小于中枢的元素和大于中枢的元素。
  • 主函数演示了如何使用 quicksort 函数对整数片段进行排序。

请注意，在 Go 中，切片是通过引用传递的，因此在函数内部对切片的修改会影响原始切片。为了方便起见，quicksort 函数会返回已排序的切片。

Rust实现

fn quicksort<T: Ord>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }

    let pivot_index = partition(arr);

    quicksort(&mut arr[0..pivot_index]);
    quicksort(&mut arr[pivot_index + 1..]);
}

fn partition<T: Ord>(arr: &mut [T]) -> usize {
    let pivot_index = arr.len() / 2;
    arr.swap(pivot_index, arr.len() - 1);

    let mut i = 0;
    for j in 0..arr.len() - 1 {
        if arr[j] <= arr[arr.len() - 1] {
            arr.swap(i, j);
            i += 1;
        }
    }

    arr.swap(i, arr.len() - 1);
    i
}

fn main() {
    let mut my_vec = vec![64, 34, 25, 12, 22, 11, 90];
    quicksort(&mut my_vec);
    println!("Sorted vector: {:?}", my_vec);
}

  • quicksort 函数是一个递归函数，使用快速排序算法对输入片段进行就地排序。
  • partition 函数用于将切片分为两半，即小于中枢的元素和大于中枢的元素。
  • 主函数演示了如何使用快速排序功能对整数向量进行排序。

这段 Rust 代码使用了泛型，使得 quicksort 和 partition 函数可以处理任何实现 Ord 特性的切片类型，这意味着可以对它们进行排序比较。

四种代码中，Python最简洁。