快速排序

快速排序算法

快速排序是最著名的排序算法之一，因为它是在标准库中用多种编程语言实现的。为什么这么用这个算法？
由于速度快，快速排序算法是最快的排序算法之一，时间复杂度为 O(n * log n)，其中 n 是数组的大小，log 是对数底数 2。

它是如何运作的？

理解快速排序算法所需的主要概念是分治策略。
分而治之的战略是一个著名的军事术语，它过去的意思是，要征服一个大国，你应该首先让这个国家分裂，通常是由于内部冲突或内战，然后你去横扫整个国家。很忙。
好的，但是这个概念如何转化为计算机科学呢？分而治之，在算法中，意味着他通过解决更小的问题来解决问题，这与数学归纳法的概念非常相似，其中，我们建立f(1)，然后我们建立f(n)，然后，我们证明 f(n - 1) 是有效的，通过这样做，我们可以证明一个概念。
分治问题的工作方式相同，首先我们解决最简单的问题，通常称为基本情况，然后，我们制定递归情况，最后，我们将问题分解为最简单的问题，因为我们知道如何解决这些问题。

算法

我将展示 C 语言的实现，然后我将逐行解释它是如何工作的，因为这是一个相当复杂的想法。

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

void _quick_sort(uint32_t *arr, size_t low, size_t high);
void quick_sort(uint32_t *arr, size_t size);

int32_t main(void)
{
    uint32_t list[] = {1, 4, 5, 10, 2, 9, 17, 100, 4, 2, 1000};

    // 11 is the number of elements list has
    // this is really usefull, because whenever we pass an array to a function, it decays as a pointer
    // due to this, if the function is in another translation layer it won't be able to know, so it can do the 
    // sizeof(list) / sizeof(list[1]) trick
    quick_sort(list, 11);

    for (size_t i = 0; i < 11; ++i)
    {
        printf("%u ", list[i]);
    }

    return EXIT_SUCCESS;
}

// Just a helper to have a cleaner interface
void quick_sort(uint32_t *arr, size_t size)
{
    // Note: here we are passing the high bound as the size - 1,
    // so in here we are having an inclusive range
    // this is important because it makes the algorithm slightly simpler
    // and it requires less -1's which usually causes a lot of off-by one mistakes
    _quick_sort(arr, 0, size - 1);
}

size_t partition(uint32_t *arr, size_t low, size_t high)
{
    // Partition is the operation that puts all the elements smaller than the pivot
    // We are picking the last element as the pivot always,
    // I guess we could be more clever and pick a random element
    // or the median of the first, middle and last elements
    // but this is just a simple example
    size_t pivot_index = high;
    uint32_t pivot = arr[pivot_index];

    // This is going to be the index of the pivot at the end
    // of the loop
    size_t i = low;
    for (size_t j = low; j <= high; ++j)
    {
        // If the current element is less than the pivot,
        // we swap it with the element at index i
        // and increment i,
        // doing this we will know exacyly where the pivot
        // should be placed after the iteration is done
        // because all the elements of index < i are less than the pivot
        // and all the elements of index > i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] < pivot)
        {
            uint32_t temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;

            ++i;
        }
    }

    // putting the pivot at the right spot, remember, it could've been anywhere
    arr[pivot_index] = arr[i];
    arr[i] = pivot;

    return i;
}

void _quick_sort(uint32_t *arr, size_t low, size_t high)
{
    // The main idea of this function, is to use a window, that has the bounds
    // [low, high] inclusive, so if the window has length 0, low = high
    // it means we reached our base case, and the list is already sorted
    // since an array without elements is always going to be sorted
    // I guess
    if (low >= high)
    {
        return;
    }

    // The pivot index is the index of the pivot element after partitioning,
    // so it means that the list is weakly sorted around the pivot,
    // (i.e. all elements to the left of the pivot are less than the pivot)
    // and all elements to the right are greater then
    size_t pivot_index = partition(arr, low, high);

    // Here we have a cool implementation detail
    // since pivot_index is a size_t, it is unsigned
    // and if we subtract 1 from an unsigned 0,
    // we get undefined behavior
    // This would happen, if the last element should be the first
    // in this case, no sorting is necessary, since there is nothing
    // before it
    if (pivot_index > 0)
    {
        // Sorting the left hand window
        // they have the bounds, [low, pivot_index - 1]
        // the -1 is so it is inclusive
        // because we now know the pivot is in the right spot
        _quick_sort(arr, low, pivot_index - 1);
    }

    // Same thing with before, now, we are sorting the right side of the window
    _quick_sort(arr, pivot_index + 1, high);
}

所以算法的主要思想很简单，将数组划分为两部分，一部分是所有元素都小于主元，另一部分是所有元素都大于主元。
然后，递归地将这个算法应用于零件本身，直到零件没有元素，在这种情况下，我们可以确定它已正确排序。

在快速排序算法中选择主元有一个重要的细微差别，如果我们选择不好的主元，我们最终会得到一个可怕的复杂性，因为每次我们将数组分成两个数组时，我们最终都会得到小的数组，在这种情况下，我们将有 n 次递归调用，并且必须遍历 n 个元素，因此快速排序的最坏情况是 O(n*n)，这非常糟糕，所以我们需要小心选择一个主元，一个好的方法是选择一个随机数，通过这样做，我们很确定会得到中间情况，即 O(n * log n), log n 因为在平均情况下，我们将分裂将数组分成两个数组，其中元素为初始数组的一半，并且由于我们必须遍历所有元素，因此存在因子 n。

以上是快速排序的详细内容。更多信息请关注PHP中文网其他相关文章！