快速排序是最著名的排序算法之一，因为它是在标准库中用多种编程语言实现的。为什么这么用这个算法？
由于速度快，快速排序算法是最快的排序算法之一，时间复杂度为 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中文网其他相关文章！
