C++完成翻轉單詞次序。本站提示廣大學習愛好者:(C++完成翻轉單詞次序)文章只能為提供參考,不一定能成為您想要的結果。以下是C++完成翻轉單詞次序正文
桶排序(Bucket sort)或所謂的箱排序,是一個排序算法,任務的道理是將數組分到無限數目的桶子裡。每一個桶子再個體排序(有能夠再應用其余排序算法或是以遞歸方法持續應用桶排序停止排序)。桶排序是鴿巢排序的一種歸結成果。當要被排序的數組內的數值是平均分派的時刻,桶排序應用線性時光(Θ(n))。但桶排序其實不是比擬排序,他不遭到O(n log n)上限的影響。
桶排序以以下法式停止:
1.設置一個定量的數組看成空桶子。
2.尋訪序列,而且把項目一個一個放到對應的桶子去。
3.對每一個不是空的桶子停止排序。
4.從不是空的桶子裡把項目再放回本來的序列中。
桶排序圖文示例
桶排序代碼:
/* * 桶排序 * * 參數解釋: * a -- 待排序數組 * n -- 數組a的長度 * max -- 數組a中最年夜值的規模 */ void bucket_sort(int a[], int n, int max) { int i, j; int *buckets; if (a==NULL || n<1 || max<1) return ; // 創立一個容量為max的數組buckets,而且將buckets中的一切數據都初始化為0。 if ((buckets=(int *)malloc(max*sizeof(int)))==NULL) return ; memset(buckets, 0, max*sizeof(int)); // 1. 計數 for(i = 0; i < n; i++) buckets[a[i]]++; // 2. 排序 for (i = 0, j = 0; i < max; i++) while( (buckets[i]--) >0 ) a[j++] = i; free(buckets); }
解釋:
bucketSort(a, n, max)是感化是對數組a停止桶排序,n是數組a的長度,max是數組中最年夜元素所屬的規模[0,max)。
假定a={8,2,3,4,3,6,6,3,9}, max=10。此時,將數組a的一切數據都放到須要為0-9的桶中。以下圖:
在將數據放到桶中以後,再經由過程必定的算法,將桶中的數據提出出來並轉換成有序數組。就獲得我們想要的成果了。