隨機化快速排序演算法

Ⅰ 隨機化演算法的舉例

下面，我們就隨機化問題，舉一個例子：
一個長度在4..10的字元串中，需要判定是否可以在字元串中刪去若干字元，使得改變後字元串符合以下條件之一：
（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA。
例如：長度為6字元串「POPKDK」，若刪除其中的「O」，「D」兩個字母，則原串變為：「PPKK」，符合條件（2）AABB。
分析：
這道題很容易想到一種演算法：運用排列組合：枚舉每4個字母，然後逐一判斷。演算法是可行的，但是如果需要題目中加上一句話：需要判斷n個字元串，且n<=100000，那麼這樣的耗時是不能讓人忍受①的，因為在枚舉的過程中，是非常浪費時間的。
（①：這里是指信息學中要求演算法的普遍運算時間為：1000ms）
所以這道題有可能可以藉助於隨機化演算法，下面我們來算一下在10個字元中取4個字元一共有多少種取法：C(4,10)=210。那麼很容易得知，隨機化演算法如果隨機300次，能得到的結果基本上就正確了(概率為1-(209/210)^300，約為0.76)，而隨機時的時間消耗是O(1)，只需要判斷沒有隨機重復即可，判重的時間復雜度也為O(1)，並且最多隨機300次，這樣就可以有效地得到答案，最大運算次數為：O(300n)，這是在計算機的承受范圍內（1000ms）的。
從這里就能看出，隨機化演算法是一個很好的概率演算法，但是它並不能保證正確，而且它單獨使用的情況很少，大部分是與其他的演算法：例如貪心、搜索等配合起來運用。 排序問題。快速排序是排序方法中較為便捷的方法之一，但是由於它極不穩定，最好的時候時間復雜度為O(n㏒n)，這里的㏒是指以2為底的對數運算。最壞的時候能達到與普通排序方法一樣的O(n^2)。
而制約快速排序的有兩個：一是數據，越無序的數據，快排的速度越快；二是中間點的枚舉。
因為兩個制約條件都與隨機有著不可分開的關系。
所以，在快速排序中加入隨機化演算法無疑是十分重要的。
運用在：
（1）數據讀入時，隨機排放數據位置。
（2）中間點的枚舉進行多次隨機化後決定。
這樣就基本上將快速排序的時間復雜度維持在最好狀態。

Ⅱ 快速排序的復雜度怎麼算，是多少

這個，我確實一點也不懂，幫你搜索。

1.
快速排序-時空復雜度：
快速排序每次將待排序數組分為兩個部分，在理想狀況下，每一次都將待排序數組劃分成等長兩個部分，則需要logn次劃分。
而在最壞情況下，即數組已經有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序將不幸退化為冒泡排序，所以快速排序時間復雜度下界為O(nlogn)，最壞情況為O(n^2)。在實際應用中，快速排序的平均時間復雜度為O(nlogn)。
快速排序在對序列的操作過程中只需花費常數級的空間。空間復雜度S(1)。
但需要注意遞歸棧上需要花費最少logn最多n的空間。

2.快速排序-隨機化演算法：
快速排序的實現需要消耗遞歸棧的空間，而大多數情況下都會通過使用系統遞歸棧來完成遞歸求解。在元素數量較大時，對系統棧的頻繁存取會影響到排序的效率。
一種常見的辦法是設置一個閾值，在每次遞歸求解中，如果元素總數不足這個閾值，則放棄快速排序，調用一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對系統遞歸棧的頻繁存取，節省了時間的消費。
一般的經驗表明，閾值取一個較小的值，排序演算法採用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值T=10，排序演算法用選擇排序。
閾值不要太大，否則省下的存取系統棧的時間，將會被簡單排序演算法較多的時間花費所抵消。
另一個可以參考的方法，是自行建棧模擬遞歸過程。但實際經驗表明，收效明顯不如設置閾值。

3.快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化演算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴於輸入數據，而是由於隨機函數取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入數據達到O(nlogn)的期望時間復雜度。一位前輩做出了一個精闢的總結：「隨機化快速排序可以滿足一個人一輩子的人品需求。」
隨機化快速排序的唯一缺點在於，一旦輸入數據中有很多的相同數據，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間復雜度將毫無疑問的降低到O(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。

4.設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設置兩個變數I、J，排序開始的時候：I=0，J=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即 key=A[0]；
3）從J開始向前搜索，即由後開始向前搜索（J=J-1），找到第一個小於key的值A[J]，並與A[I]交換；
4）從I開始向後搜索，即由前開始向後搜索（I=I+1），找到第一個大於key的A[I]，與A[J]交換；
5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1。找到並交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j+完成的最後另循環結束)
例如：待排序的數組A的值分別是：（初始關鍵數據：X=49） 注意關鍵X永遠不變，永遠是和X進行比較，無論在什麼位子，最後的目的就是把X放在中間，小的放前面大的放後面。
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時：I=4,J=6 )
此時再執行第三步的時候就發現I=J，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最

Ⅲ 快速排序演算法原理與實現

快速排序的基本思想就是從一個數組中任意挑選一個元素（通常來說會選擇最左邊的元素）作為中軸元素，將剩下的元素以中軸元素作為比較的標准，將小於等於中軸元素的放到中軸元素的左邊，將大於中軸元素的放到中軸元素的右邊。

然後以當前中軸元素的位置為界，將左半部分子數組和右半部分子數組看成兩個新的數組，重復上述操作，直到子數組的元素個數小於等於1（因為一個元素的數組必定是有序的）。

以下的代碼中會常常使用交換數組中兩個元素值的Swap方法，其代碼如下

publicstaticvoidSwap(int[] A, inti, intj){

inttmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

(3)隨機化快速排序演算法擴展閱讀：

快速排序演算法 的基本思想是：將所要進行排序的數分為左右兩個部分，其中一部分的所有數據都比另外一 部分的數據小，然後將所分得的兩部分數據進行同樣的劃分，重復執行以上的劃分操作，直 到所有要進行排序的數據變為有序為止。

定義兩個變數low和high，將low、high分別設置為要進行排序的序列的起始元素和最後一個元素的下標。第一次，low和high的取值分別為0和n-1，接下來的每次取值由劃分得到的序列起始元素和最後一個元素的下標來決定。

定義一個變數key，接下來以key的取值為基準將數組A劃分為左右兩個部分，通 常，key值為要進行排序序列的第一個元素值。第一次的取值為A[0]，以後毎次取值由要劃 分序列的起始元素決定。

從high所指向的數組元素開始向左掃描，掃描的同時將下標為high的數組元素依次與劃分基準值key進行比較操作，直到high不大於low或找到第一個小於基準值key的數組元素，然後將該值賦值給low所指向的數組元素，同時將low右移一個位置。

如果low依然小於high，那麼由low所指向的數組元素開始向右掃描，掃描的同時將下標為low的數組元素值依次與劃分的基準值key進行比較操作，直到low不小於high或找到第一個大於基準值key的數組元素，然後將該值賦給high所指向的數組元素，同時將high左移一個位置。

重復步驟(3) (4)，直到low的植不小於high為止，這時成功劃分後得到的左右兩部分分別為A[low……pos-1]和A[pos+1……high]，其中，pos下標所對應的數組元素的值就是進行劃分的基準值key，所以在劃分結束時還要將下標為pos的數組元素賦值 為 key。

Ⅳ 隨機化的演算法

在我們的生活中，人們經常會去擲色子來看結果，投硬幣來決定行動，這就牽涉到一個問題：隨機。
計算機為我們提供好了隨機方法（部分計算器也提供了），那麼對於有些具有瑕疵的演算法，如果配上隨機化演算法的話，又是可以得到一樣不到的結果。
這種演算法看上去是憑著運氣做事，其實，隨機化演算法是有一定的理論基礎的，我們可以想像，在[1,10000]這個閉區間里，隨機1000次，隨機到2這個數的幾率是多大，何況1000次的隨機在計算機程序中僅僅是一眨眼的功夫。可以看出，隨機化演算法有著廣闊的前景。只是由於隨機化演算法比較難於掌控，所以並不是很多人都接觸過他，但肯定有很多人都聽說過。
下面，我們就隨機化問題，舉一個例子：
一個長度在4..10的字元串中，需要判定是否可以在字元串中刪去若干字元，使得改變後字元串符合以下條件之一：
（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA。
例如：長度為6字元串「POPKDK」，若刪除其中的「O」，「D」兩個字母，則原串變為：「PPKK」，符合條件（2）AABB。
分析：
這道題很容易想到一種演算法：運用排列組合：枚舉每4個字母，然後逐一判斷。演算法是可行的，但是如果需要題目中加上一句話：需要判斷n個字元串，且n<=100000，那麼這樣的耗時是不能讓人忍受①的，因為在枚舉的過程中，是非常浪費時間的。
(①：這里是指信息學中要求演算法的普遍運算時間為：1000ms）
所以這道題有可能可以藉助於隨機化演算法，下面我們來算一下在10個組符中取4個字元一共有多少種取法：C(4,10)=210。那麼很容易得知，隨機化演算法如果隨機100次，能都到的結果基本上就正確了，而隨機時的時間消耗是O(1)，只需要判斷沒有隨機重復即可，判重的時間復雜度也為O(1)，並且最多隨機100次，這樣就可以有效地得到答案，最大運算次數為：O(100n)，這是在計算機的承受范圍內（1000ms）的。
從這里就能看出，隨機化演算法是一個很好的概率演算法，但是它並不能保證正確，而且它單獨使用的情況很少，大部分是與其他的演算法：例如貪心、搜索等配合起來運用。
再舉一個例子：
排序問題。快速排序是排序方法中較為便捷的方法之一，但是由於它極不穩定，最好的時候時間復雜度為O(n㏒n)，這里的㏒是指以2為底的對數運算。最壞的時候能達到與普通排序方法一樣的O(n^2)。
而制約快速排序的有兩個：一是數據，越無序的數據，快排的速度越快；二是中間點的枚舉。
因為兩個制約條件都與隨機有著不可分開的關系。
所以，在快速排序中加入隨機化演算法無疑是十分重要的。

Ⅳ java編程實現隨機數組的快速排序

java編程實現隨機數組的快速排序步驟如下：

1、打開Eclipse，新建一個Java工程，在此工程里新建一個Java類；

2、在新建的類中聲明一個產生隨機數的Random變數，再聲明一個10個長度的int型數組；

3、將產生的隨機數逐個放入到數組中；

4、利用排序演算法對隨機數組進行排序。

具體代碼如下：

importjava.util.Random;
publicclassDemo{
publicstaticvoidmain(String[]args){
intcount=0;
Randomrandom=newRandom();
inta[]=newint[10];
while(count<10){
a[count]=random.nextInt(1000);//產生0-999的隨機數
count++;
}
for(inti=0;i<a.length-1;i++){
intmin=i;
for(intj=i+1;j<a.length;j++){
if(a[j]<a[min]){
min=j;
}
}
if(min!=i){
intb=a[min];
a[min]=a[i];
a[i]=b;
}
}
for(intc=0;c<a.length;c++){
System.out.print(a[c]+"");
}
}
}

Ⅵ 快速排序怎樣隨機化

procere qsort(l,r:integer);
var i,j,x,t:longint;
begin
i:=l;j:=r;x:=a[random(r-l+1)+l];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;

這是我編的快排過程
是隨機啊

如果一直是1，n-1的劃分（就是最差情況，不二分）就成O(n^2)的演算法了
就起不到快排的作用了

Ⅶ 什麼是隨機快速排序

隨機選擇快速排序是一種比較常見的優化快速排序的方法，即隨機選取一個元素作為主元，而不是像普通快速排序那樣選取第一個元素作為主元，這種情況下雖然最壞情況仍然是O(n^2），但最壞情況不再依賴於輸入數據，而是由於隨機函數取值不佳。
實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n）。所以隨機化快速排序可以對於絕大多輸入數據達到O(nlogn）的期望時間復雜度。