快速排序

快速排序演算法

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