和js快速排序偽代碼相關的問題（用偽代碼寫出快速排序）

本文目錄一覽：

• 1、nodejs實現冒泡排序和快速排序
• 2、快速排序算法的示例代碼
• 3、想問您一些排序算法的偽代碼，謝啦

nodejs實現冒泡排序和快速排序

冒泡排序：雙層循環，內部循環每次選出最大值或者最小值，放到頭上或者放在尾部

快速排序：遞歸調用，每次遞歸選出一個「中值」，頭部和尾部分別跟「中值」比較，找出可交換值後交換位置。每次交換後，數組的逆序減少比其他排序算法要多，所以相對比較快

快速排序算法的示例代碼

    using System;     using System.Collections.Generic;     using System.Linq;     using System.Text;    namespace test{    class QuickSort    {        static void Main(string[] args)        {            int[] array = { 49, 38, 65, 97, 76, 13, 27 };            sort(array, 0, array.Length – 1);            Console.ReadLine();        }        /**一次排序單元，完成此方法，key左邊都比key小，key右邊都比key大。         **@param array排序數組          **@param low排序起始位置          **@param high排序結束位置         **@return單元排序後的數組 */        private static int sortUnit(int[] array, int low, int high)        {            int key = array[low];            while (low  high)            {                /*從後向前搜索比key小的值*/                while (array[high] = key  high  low)                    –high;                 /*比key小的放左邊*/                array[low] = array[high];                   /*從前向後搜索比key大的值，比key大的放右邊*/                while (array[low] = key  high  low)                    ++low;                 /*比key大的放右邊*/                array[high] = array[low];            }            /*左邊都比key小，右邊都比key大。//將key放在游標當前位置。//此時low等於high */            array[low] = key;            foreach (int i in array)            {                Console.Write({0}\t, i);            }            Console.WriteLine();            return high;        }            /**快速排序 *@paramarry *@return */        public static void sort(int[] array, int low, int high)        {            if (low = high)                return;             /*完成一次單元排序*/            int index = sortUnit(array, low, high);             /*對左邊單元進行排序*/            sort(array, low, index – 1);            /*對右邊單元進行排序*/            sort(array, index + 1, high);        }    }} 運行結果：27 38 13 49 76 97 65

13 27 38 49 76 97 6513 27 38 49 65 76 97

快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：

初始狀態 {49 38 65 97 76 13 27} 進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65} 分別對前後兩部分進行快速排序{27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。圖示 快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴於輸入數據，而是由於隨機函數取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入數據達到O(nlogn)的期望時間複雜度。一位前輩做出了一個精闢的總結：「隨機化快速排序可以滿足一個人一輩子的人品需求。」

隨機化快速排序的唯一缺點在於，一旦輸入數據中有很多的相同數據，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到O(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。 QUICKSORT(A，p，r)

1　if pr

2　then q ←PARTITION(A，p，r)

3　QUICKSORT(A，p，q-1)

4　QUICKSORT(A，q+1，r)

為排序一個完整的數組A，最初的調用是QUICKSORT(A，1，length[A]）。

快速排序算法的關鍵是PARTITION過程，它對子數組A[p..r]進行就地重排：

PARTITION(A，p，r)

1　x←A[r]

2　i←p-1

3　for j←p to r-1

4　do if A[j]≤x

5　then i←i+1

6　exchange A[i]←→A[j]

7　exchange A[i+1]←→A[r]

8　return i+1 對PARTITION和QUICKSORT所作的改動比較小。在新的劃分過程中，我們在真正進行劃分之前實現交換：

（其中PARTITION過程同快速排序偽代碼（非隨機））

RANDOMIZED-PARTITION(A，p，r)

1　i← RANDOM(p，r)

2　exchange A[r]←→A[i]

3　return PARTITION(A，p，r)

新的快速排序過程不再調用PARTITION，而是調用RANDOMIZED-PARTITION。

RANDOMIZED-QUICKSORT(A，p，r)

1　if pr

2　then q← RANDOMIZED-PARTITION(A，p，r)

3　RANDOMIZED-QUICKSORT(A，p，q-1)

4　RANDOMIZED-QUICKSORT(A，q+1，r) 這裡為方便起見，我們假設算法Quick_Sort的範圍閾值為1（即一直將線性表分解到只剩一個元素），這對該算法複雜性的分析沒有本質的影響。

我們先分析函數partition的性能，該函數對於確定的輸入複雜性是確定的。觀察該函數，我們發現，對於有n個元素的確定輸入L[p..r]，該函數運行時間顯然為θ（n）。

最壞情況

無論適用哪一種方法來選擇pivot，由於我們不知道各個元素間的相對大小關係（若知道就已經排好序了），所以我們無法確定pivot的選擇對劃分造成的影響。因此對各種pivot選擇法而言，最壞情況和最好情況都是相同的。

我們從直覺上可以判斷出最壞情況發生在每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的時候（設輸入的表有n個元素）。下面我們暫時認為該猜測正確，在後文我們再詳細證明該猜測。

對於有n個元素的表L[p..r]，由於函數Partition的計算時間為θ（n），所以快速排序在序壞情況下的複雜性有遞歸式如下：

T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n) (1)

用迭代法可以解出上式的解為T(n)=θ（n2）。

這個最壞情況運行時間與插入排序是一樣的。

下面我們來證明這種每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的情況就是最壞情況。

設T(n）是過程Quick_Sort作用於規模為n的輸入上的最壞情況的時間，則

T(n)=max(T(q)+T(n-q))+θ（n)，其中1≤q≤n-1 (2)

我們假設對於任何kn，總有T(k）≤ck，其中c為常數；顯然當k=1時是成立的。

將歸納假設代入（2），得到：

T(n）≤max(cq2+c(n-q)2)+θ（n)=c*max(q2+(n-q)2)+θ（n)

因為在[1,n-1]上q2+(n-q)2關於q遞減，所以當q=1時q2+(n-q)2有最大值n2-2(n-1）。於是有：

T(n）≤cn2-2c(n-1)+θ（n）≤cn2

只要c足夠大，上面的第二個小於等於號就可以成立。於是對於所有的n都有T(n）≤cn。

這樣，排序算法的最壞情況運行時間為θ（n2），且最壞情況發生在每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的時候。

時間複雜度為o（n2）。

最好情況

如果每次劃分過程產生的區間大小都為n/2，則快速排序法運行就快得多了。這時有：

T(n)=2T(n/2)+θ（n),T(1)=θ（1) (3)

解得：T(n)=θ（nlogn)

快速排序法最佳情況下執行過程的遞歸樹如下圖所示，圖中lgn表示以10為底的對數，而本文中用logn表示以2為底的對數.

由於快速排序法也是基於比較的排序法，其運行時間為Ω（nlogn)，所以如果每次劃分過程產生的區間大小都為n/2，則運行時間θ（nlogn）就是最好情況運行時間。

但是，是否一定要每次平均劃分才能達到最好情況呢？要理解這一點就必須理解對稱性是如何在描述運行時間的遞歸式中反映的。我們假設每次劃分過程都產生9:1的劃分，乍一看該劃分很不對稱。我們可以得到遞歸式：

T(n)=T(n/10)+T(9n/10)+θ（n),T(1)=θ（1) (4)

請注意樹的每一層都有代價n，直到在深度log10n=θ（logn）處達到邊界條件，以後各層代價至多為n。遞歸於深度log10/9n=θ（logn）處結束。這樣，快速排序的總時間代價為T(n)=θ（nlogn），從漸進意義上看就和劃分是在中間進行的一樣。事實上，即使是99:1的劃分時間代價也為θ（nlogn）。其原因在於，任何一種按常數比例進行劃分所產生的遞歸樹的深度都為θ（nlogn），其中每一層的代價為O(n），因而不管常數比例是什麼，總的運行時間都為θ（nlogn），只不過其中隱含的常數因子有所不同。（關於算法複雜性的漸進階，請參閱算法的複雜性)

平均情況

快速排序的平均運行時間為θ(nlogn)。

我們對平均情況下的性能作直覺上的分析。

要想對快速排序的平均情況有個較為清楚的概念，我們就要對遇到的各種輸入作個假設。通常都假設輸入數據的所有排列都是等可能的。後文中我們要討論這個假設。

當我們對一個隨機的輸入數組應用快速排序時，要想在每一層上都有同樣的劃分是不太可能的。我們所能期望的是某些劃分較對稱，另一些則很不對稱。事實上，我們可以證明，如果選擇L[p..r]的第一個元素作為支點元素，Partition所產生的劃分80%以上都比9:1更對稱，而另20%則比9:1差，這裡證明從略。

平均情況下，Partition產生的劃分中既有「好的」，又有「差的」。這時，與Partition執行過程對應的遞歸樹中，好、差劃分是隨機地分佈在樹的各層上的。為與我們的直覺相一致，假設好、差劃分交替出現在樹的各層上，且好的劃分是最佳情況劃分，而差的劃分是最壞情況下的劃分。在根節點處，劃分的代價為n，劃分出來的兩個子表的大小為n-1和1，即最壞情況。在根的下一層，大小為n-1的子表按最佳情況劃分成大小各為（n-1)/2的兩個子表。這兒我們假設含1個元素的子表的邊界條件代價為1。

在一個差的劃分後接一個好的劃分後，產生出三個子表，大小各為1，（n-1)/2和（n-1)/2，代價共為2n-1=θ（n）。一層劃分就產生出大小為（n-1)/2+1和（n-1)/2的兩個子表，代價為n=θ（n）。這種劃分差不多是完全對稱的，比9:1的劃分要好。從直覺上看，差的劃分的代價θ（n）可被吸收到好的劃分的代價θ（n）中去，結果是一個好的劃分。這樣，當好、差劃分交替分佈劃分都是好的一樣：仍是θ（nlogn），但θ記號中隱含的常數因子要略大一些。關於平均情況的嚴格分析將在後文給出。

在前文從直覺上探討快速排序的平均性態過程中，我們已假定輸入數據的所有排列都是等可能的。如果輸入的分佈滿足這個假設時，快速排序是對足夠大的輸入的理想選擇。但在實際應用中，這個假設就不會總是成立。

解決的方法是，利用隨機化策略，能夠克服分佈的等可能性假設所帶來的問題。

一種隨機化策略是：與對輸入的分佈作「假設」不同的是對輸入的分佈作「規定」。具體地說，在排序輸入的線性表前，對其元素加以隨機排列，以強制的方法使每種排列滿足等可能性。事實上，我們可以找到一個能在O(n）時間內對含n個元素的數組加以隨機排列的算法。這種修改不改變算法的最壞情況運行時間，但它卻使得運行時間能夠獨立於輸入數據已排序的情況。

另一種隨機化策略是：利用前文介紹的選擇支點元素pivot的第四種方法，即隨機地在L[p..r]中選擇一個元素作為支點元素pivot。實際應用中通常採用這種方法。

快速排序的隨機化版本有一個和其他隨機化算法一樣的有趣性質：沒有一個特別的輸入會導致最壞情況性態。這種算法的最壞情況性態是由隨機數產生器決定的。你即使有意給出一個壞的輸入也沒用，因為隨機化排列會使得輸入數據的次序對算法不產生影響。只有在隨機數產生器給出了一個很不巧的排列時，隨機化算法的最壞情況性態才會出現。事實上可以證明幾乎所有的排列都可使快速排序接近平均情況性態，只有非常少的幾個排列才會導致算法的近最壞情況性態。

一般來說，當一個算法可按多條路子做下去，但又很難決定哪一條保證是好的選擇時，隨機化策略是很有用的。如果大部分選擇都是好的，則隨機地選一個就行了。通常，一個算法在其執行過程中要做很多選擇。如果一個好的選擇的獲益大於坏的選擇的代價，那麼隨機地做一個選擇就能得到一個很有效的算法。我們在前文已經了解到，對快速排序來說，一組好壞相雜的劃分仍能產生很好的運行時間 。因此我們可以認為該算法的隨機化版本也能具有較好的性態。

想問您一些排序算法的偽代碼，謝啦

冒泡排序：網頁鏈接

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。一個優秀的算法可以節省大量的資源。在各個領域中考慮到數據的各種限制和規範，要得到一個符合實際的優秀算法，得經過大量的推理和分析。

C++自帶的algorithm庫函數中提供了排序算法。

穩定的

冒泡排序（bubble sort） — O(n^2）

雞尾酒排序(Cocktail sort，雙向的冒泡排序) — O(n^2）

插入排序（insertion sort）— O(n^2)

桶排序（bucket sort）— O(n); 需要 O(k) 額外空間

計數排序(counting sort) — O(n+k); 需要 O(n+k) 額外空間

合併排序（merge sort）— O(nlog n); 需要 O(n) 額外空間

原地合併排序— O(n^2)

二叉排序樹排序 （Binary tree sort） — O(nlog n)期望時間； O(n^2)最壞時間； 需要 O(n) 額外空間

鴿巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 額外空間

基數排序（radix sort）— O(n·k); 需要 O(n) 額外空間

Gnome 排序— O(n^2)

圖書館排序— O(nlog n) with high probability，需要 （1+ε)n額外空間

不穩定的

選擇排序（selection sort）— O(n^2)

希爾排序（shell sort）— O(nlog n) 如果使用最佳的現在版本

組合排序— O(nlog n)

堆排序（heapsort）— O(nlog n)

平滑排序— O(nlog n)

快速排序（quicksort）— O(nlog n) 期望時間，O(n^2) 最壞情況； 對於大的、亂數列表一般相信是最快的已知排序

Introsort— O(nlog n)

耐心排序— O(nlog n+ k) 最壞情況時間，需要 額外的 O(n+ k) 空間，也需要找到最長的遞增子串行（longest increasing subsequence）

不實用的

Bogo排序— O(n× n!) 期望時間，無窮的最壞情況。

Stupid sort— O(n^3); 遞歸版本需要 O(n^2) 額外存儲器

珠排序（Bead sort） — O(n) or O（√n)，但需要特別的硬件

Pancake sorting— O(n)，但需要特別的硬件

stooge sort——O（n^2.7）很漂亮但是很耗時