快速排序演算法
快速排序是最著名的排序演算法之一，因為它是在標準庫中用多種程式語言實現的。為什麼這麼用這個演算法？
由於速度快，快速排序演算法是最快的排序演算法之一，時間複雜度為 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中文網其他相關文章！
