快速排序算法

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

它是如何工作的？

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

算法

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

#include 
#include 
#include 

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  i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] = 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.