基數排序算法流程圖?　1：n個元素組成的集合，第i個順序統計量，就是該集合中第i小的元素所以，集合中的最小值就是第1個順序統計量，最大值就是第n個順序統計量中位數是所屬集合的“中點元素”，當n是奇數的時候，中位數唯一，位于(n 1)/2處如果n是偶數，中位數有兩個，分别位于n/2和(n/2) 1，我來為大家講解一下關于基數排序算法流程圖?跟着小編一起來看一看吧!

基數排序算法流程圖

　1：n個元素組成的集合，第i個順序統計量，就是該集合中第i小的元素。所以，集合中的最小值就是第1個順序統計量，最大值就是第n個順序統計量。中位數是所屬集合的“中點元素”，當n是奇數的時候，中位數唯一，位于(n 1)/2處。如果n是偶數，中位數有兩個，分别位于n/2和(n/2) 1。

　　2：選擇問題，就是選擇第i個順序統計量的問題。如果利用排序的話，那最快可以在O(n lgn)時間内解決，但其實有更快的算法。

　　3：為了找到n個元素中的最小值或者最大值，最少需要n-1次比較：

MINIMUM(A)

min = A[1]

for i = 2 to A.len

if min > A[i]

min = A[i]

return min

　　4：對于需要同時找到最大值和最小值的問題，如果是獨立找出最大值和最小值的話，需要2n-2次比較，實際上，采用某種方法可以實現比較次數最多到3（n/2）次。該方法是：記錄已知的最大值和最小值，對輸入的元素成對的進行處理，首先将2個輸入元素相互比較，然後把較小的元素與最小值比較，較大的元素與最大值比較，這樣，每兩個元素共需比較3次。如果n是奇數，把最大值和最小值的初值都設置為第一個元素的值，所以，比較次數為3((n-1)/2)。如果n是偶數，把前兩個元素作比較，确定最初的最大值和最小值，所以，比較次數為3((n-1)/2)。所以，不管哪一種情況，總的比較次數最多為3(n/2)。

　　如果要找第二小的元素，證明最壞情況下需要n lg n – 2次比較。

　　證明：采用這樣的方法找最小元素：将n個元素成對比較，找到n/2個小元素，然後對着n/2個元素再次成對比較，知道最後一個元素，也就是最小元素。

　　在該算法中，可以從底向上畫出一棵完全二叉樹，數有n個葉子結點，有n-1個内部結點，每個内部結點代表了一次比較，所以在尋找最小元素的過程中，需要n-1次比較。

　　為了找到第二小的元素，因該元素肯定是在與最小元素的比較過程中被淘汰掉了，所以為了尋找該元素，可以在該完全二叉樹中，找到包含最小元素的分支，該分支一共有lg n個結點，在這lgn個結點中在找最小節點就好了，也是需要lg n – 1次比較。所以一共需要n lg n – 2次比較。

　　5：對于一般的選擇問題，可以采用類似于快速排序的方法，可以使運行時間達到Θ(n)。該算法稱為RANDOMIZED-SELECT算法。該算法也是随機算法，因為其中調用了RANDOMIZED-PARTITION。算法僞代碼如下：

RANDOMIZED-SELECT(A, p, r, i)

if(p == r)

return A[p]

q = RANDOMIZED-PARTITION(A, p, r)

k = q – p 1

if(k == i)

return A[q]

else if I < k

return RANDOMIZED-SELECT(A,p, q-1, i)

else return RANDOMIZED-SELECT(A,q 1, r, i-k)

　　該算法的最壞情況運行時間為Θ( )。但因為是随機的，所以不存在一個特定的輸入會導緻最壞情況的發生。該算法的期望運行時間為O(n)。

int randompartition(int *set, int begin, int end)

{

int i, j, k;

int x;

int ran;

srand((int)time(NULL));

ran = randomab(begin, end);

exchange(set ran, set end);

x = set[end];

i = begin - 1;

for(j = begin; j <= end - 1; j )

{

if(set[j] <= x)

{

i ;

exchange(set i, set j);

}

}

exchange(set i 1, set end);

return i 1;

}

int partitionselect(int *set, int begin, int end, int index)

{

int q;

int k;

if(index <= 0 || index > (end-begin 1))

{

printf("error index: %d", index);

return -1;

}

if(begin == end)

{

return set[begin];

}

q = randompartition(set, begin, end);

k = q - begin 1;

if(index == k)

{

return set[q];

}

else if(index < k)

{

partitionselect(set, begin, q-1, index);

}

else

{

partitionselect(set, q 1, end, index-k);

}

}

　　6：SELECT算法可以在最壞情況運行時間為O(n)來解決選擇問題，該算法步驟如下：　　a、将輸入數組的n個元素劃分為n/5組，每組5個元素，且至多有一個組由剩下的nmod 5個元素組成。　　b、尋找n/5個組中每一組的中位數。（方法首先對每組中的元素進行插入排序，然後從排序過的序列中選出中位數）　　c、對第2步中找出的n/5個中位數，遞歸調用SELECT找出其中位數x。（如果有偶數個中位數，根據約定，x是下中位數。）　　d、 利用修改過的PARTITION過程，按中位數的中位數x對輸入數組進行劃分。讓k比劃分低區的元素多1，所以x是第k小的元素，并且有n-k個元素在劃分的高區。　　e、如果i=k，則返回x，否則，如果i<k，則在低區遞歸調用SELECT以找出第i小的元素，如果i>k，則在高區找第（i-k）個最小元素。

　　圖中箭頭指向表示大的數值指向小的數值，所以根據圖可以看出，在x的右邊，每一個包含5個元素的組中至少有3個元素大于x，x的左邊，每一組中至少有3個元素小于x。（保證x分割一邊必定有元素存在）　　圖中顯示的中位數的中位數x的位置，每次選取x作為劃分的好處是能夠保證必定有一部分在x的一邊。　　所以算法最壞情況的遞歸公式可以寫成：

　　使用替換法可以得出T（n）<=cn。

注：凡屬于本公衆号内容，未經允許不得私自轉載，否則将依法追究侵權責任。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!