箱排序代碼
Ⅰ 誰能幫我把希爾排序·箱排序等等之類的排序都加上去我目前只寫了快速排序，冒泡排序，選擇排序上去
太晚了明天吧我先去睡了
Ⅱ 桶排序的演算法
桶排序演算法要求，數據的長度必須完全一樣，程序過程要產生長度相同的數據，使用下面的方法：Data=rand()/10000+10000上面提到的，每次下一次的掃描順序是按照上次掃描的結果來的，所以設計上提供相同的兩個桶數據結構。前一個保存每一次掃描的結果供下次調用，另外一個臨時拷貝前一次掃描的結果提供給前一個調用。
數據結構設計：鏈表可以採用很多種方式實現，通常的方法是動態申請內存建立結點，但是針對這個演算法，桶裡面的鏈表結果每次掃描後都不同，就有很多鏈表的分離和重建。如果使用動態分配內存，則由於指針的使用，安全性低。所以，筆者設計時使用了數組來模擬鏈表（當然犧牲了部分的空間，但是操作卻是簡單了很多，穩定性也大大提高了）。共十個桶，所以建立一個二維數組，行向量的下標0—9代表了10個桶，每個行形成的一維數組則是桶的空間。
平均情況下桶排序以線性時間運行。像基數排序一樣，桶排序也對輸入作了某種假設， 因而運行得很快。具 體來說，基數排序假設輸入是由一個小范圍內的整數構成，而桶排序則 假設輸入由一個隨機過程產生，該過程將元素一致地分布在區間[0，1)上。 桶排序的思想就是把區間[0，1)劃分成n個相同大小的子區間，或稱桶，然後將n個輸入數分布到各個桶中去。因為輸入數均勻分布在[0，1)上，所以一般不會有很多數落在一個桶中的情況。為得到結果，先對各個桶中的數進行排序，然後按次序把各桶中的元素列出來即可。
在桶排序演算法的代碼中，假設輸入是含n個元素的數組A，且每個元素滿足0≤ A[i]<1。另外還需要一個輔助數組B[O..n-1]來存放鏈表實現的桶，並假設可以用某種機制來維護這些表。
桶排序的演算法如下(偽代碼表示)，其中floor(x)是地板函數，表示不超過x的最大整數。
procere Bin_Sort(var A:List);begin
n:=length(A);
for i:=1 to n do
將A[i]插到表B[floor(n*A[i])]中;
for i:=0 to n-1 do
用插入排序對表B[i]進行排序;
將表B[0],B[1],...,B[n-1]按順序合並;
end;
右圖演示了桶排序作用於有10個數的輸入數組上的操作過程。(a)輸入數組A[1..10]。(b)在該演算法的第5行後的有序表(桶)數組B[0..9]。桶i中存放了區間[i/10，(i+1)/10]上的值。排序輸出由表B[O]、B[1]、...、B[9]的按序並置構成。
要說明這個演算法能正確地工作，看兩個元素A[i]和A[j]。如果它們落在同一個桶中，則它們在輸出序列中有著正確的相對次序，因為它們所在的桶是採用插入排序的。現假設它們落到不同的桶中，設分別為B[i']和B[j']。不失一般性，假設i' i'=floor(n*A[i])≥floor(n*A[j])=j' 得矛盾 (因為i' 來分析演算法的運行時間。除第5行外，所有各行在最壞情況的時間都是O(n)。第5行中檢查所有桶的時間是O(n)。分析中唯一有趣的部分就在於第5行中插人排序所花的時間。
為分析插人排序的時間代價，設ni為表示桶B[i]中元素個數的隨機變數。因為插入排序以二次時間運行，故為排序桶B[i]中元素的期望時間為E[O(ni2)]=O(E[ni2])，對各個桶中的所有元素排序的總期望時間為：O(n)。(1) 為了求這個和式，要確定每個隨機變數ni的分布。我們共有n個元素，n個桶。某個元素落到桶B[i]的概率為l/n，因為每個桶對應於區間[0，1)的l/n。這種情況與投球的例子很類似：有n個球 (元素)和n個盒子 (桶)，每次投球都是獨立的，且以概率p=1/n落到任一桶中。這樣，ni=k的概率就服從二項分布B(k;n,p)，其期望值為E[ni]=np=1，方差V[ni]=np(1-p)=1-1/n。對任意隨機變數X，有右圖所示表達式。
(2)將這個界用到(1)式上，得出桶排序中的插人排序的期望運行時間為O(n)。因而，整個桶排序的期望運行時間就是線性的。
Ⅲ c語言快速排序代碼
#include <stdio.h>
int partions(int l[],int low,int high)
{
int prvotkey=l[low];
l[0]=l[low];
while (low<high)
{
while (low<high&&l[high]>=prvotkey)
--high;
l[low]=l[high];
while (low<high&&l[low]<=prvotkey)
++low;
l[high]=l[low];
}
l[low]=l[0];
return low;
}
void qsort(int l[],int low,int high)
{
int prvotloc;
if(low<high)
{
prvotloc=partions(l,low,high); //將第一次排序的結果作為樞軸
qsort(l,low,prvotloc-1); //遞歸調用排序 由low 到prvotloc-1
qsort(l,prvotloc+1,high); //遞歸調用排序 由 prvotloc+1到 high
}
}
void quicksort(int l[],int n)
{
qsort(l,1,n); //第一個作為樞軸 ，從第一個排到第n個
}
void main()
{
int a[11]={0,2,32,43,23,45,36,57,14,27,39};
for (int b=1;b<11;b++)
printf("%3d",a[b]);
printf("\n");
quicksort(a,11);
for(int c=1;c<11;c++)
printf("%3d",a[c]);
}
Ⅳ 求c語言基數排序與桶排序的源代碼
基數排序：
#include<math.h>
testBS()
{
inta[]={2,343,342,1,123,43,4343,433,687,654,3};
int*a_p=a;
//計算數組長度
intsize=sizeof(a)/sizeof(int);
//基數排序
bucketSort3(a_p,size);
//列印排序後結果
inti;
for(i=0;i<size;i++)
{
printf("%d ",a[i]);
}
intt;
scanf("%d",t);
}
//基數排序
voidbucketSort3(int*p,intn)
{
//獲取數組中的最大數
intmaxNum=findMaxNum(p,n);
//獲取最大數的位數，次數也是再分配的次數。
intloopTimes=getLoopTimes(maxNum);
inti;
//對每一位進行桶分配
for(i=1;i<=loopTimes;i++)
{
sort2(p,n,i);
}
}
//獲取數字的位數
intgetLoopTimes(intnum)
{
intcount=1;
inttemp=num/10;
while(temp!=0)
{
count++;
temp=temp/10;
}
returncount;
}
//查詢數組中的最大數
intfindMaxNum(int*p,intn)
{
inti;
intmax=0;
for(i=0;i<n;i++)
{
if(*(p+i)>max)
{
max=*(p+i);
}
}
returnmax;
}
//將數字分配到各自的桶中，然後按照桶的順序輸出排序結果
voidsort2(int*p,intn,intloop)
{
//建立一組桶此處的20是預設的根據實際數情況修改
intbuckets[10][20]={};
//求桶的index的除數
//如798個位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum為上式中的1、10、100
inttempNum=(int)pow(10,loop-1);
inti,j;
for(i=0;i<n;i++)
{
introw_index=(*(p+i)/tempNum)%10;
for(j=0;j<20;j++)
{
if(buckets[row_index][j]==NULL)
{
buckets[row_index][j]=*(p+i);
break;
}
}
}
//將桶中的數，倒回到原有數組中
intk=0;
for(i=0;i<10;i++)
{
for(j=0;j<20;j++)
{
if(buckets[i][j]!=NULL)
{
*(p+k)=buckets[i][j];
buckets[i][j]=NULL;
k++;
}
}
}
}
桶排序
#include<stdio.h>
#defineMAXNUM100
voidbucksort(intarr[],intN,intM)
{
intcount[MAXNUM];
for(inti=0;i<=M;i++)
{
count[i]=0;
}
for(inti=0;i<N;i++)
{
++count[arr[i]];
}
for(inti=0;i<=M;i++)
{
for(intj=1;j<=count[i];j++)
{
printf("%d",i);
}
}
}
intmain()
{
inta[]={2,5,6,12,4,8,8,6,7,8,8,10,7,6};
bucksort(a,sizeof(a)/sizeof(a[0]),12);
return0;
}
Ⅳ 箱排序的介紹
箱排序也來稱桶排序(BucketSort)，其基本思想是源：設置若干個箱子，依次掃描待排序的記錄R[0]，R[1]，…，R[n-1]，把關鍵字等於k的記錄全都裝入到第k個箱子里(分配)，然後按序號依次將各非空的箱子首尾連接起來(收集)。
Ⅵ Java幾種簡單的排序源代碼
給你介紹4種排序方法及源碼，供參考
1.冒泡排序
主要思路： 從前往後依次交換兩個相鄰的元素，大的交換到後面，這樣每次大的數據就到後面，每一次遍歷，最大的數據到達最後面，時間復雜度是O(n^2)。
publicstaticvoidbubbleSort(int[]arr){
for(inti=0;i<arr.length-1;i++){
for(intj=0;j<arr.length-1;j++){
if(arr[j]>arr[j+1]){
arr[j]=arr[j]^arr[j+1];
arr[j+1]=arr[j]^arr[j+1];
arr[j]=arr[j]^arr[j+1];
}
}
}
}
2.選擇排序
主要思路：每次遍歷序列，從中選取最小的元素放到最前面，n次選擇後，前面就都是最小元素的排列了，時間復雜度是O(n^2）。
publicstaticvoidselectSort(int[]arr){
for(inti=0;i<arr.length-1;i++){
for(intj=i+1;j<arr.length;j++){
if(arr[j]<arr[i]){
arr[j]=arr[j]^arr[i];
arr[i]=arr[j]^arr[i];
arr[j]=arr[j]^arr[i];
}
}
}
}
3.插入排序
主要思路：使用了兩層嵌套循環，逐個處理待排序的記錄。每個記錄與前面已經排好序的記錄序列進行比較，並將其插入到合適的位置，時間復雜度是O(n^2）。
publicstaticvoidinsertionSort(int[]arr){
intj;
for(intp=1;p<arr.length;p++){
inttemp=arr[p];//保存要插入的數據
//將無序中的數和前面有序的數據相比，將比它大的數，向後移動
for(j=p;j>0&&temp<arr[j-1];j--){
arr[j]=arr[j-1];
}
//正確的位置設置成保存的數據
arr[j]=temp;
}
}
4.希爾排序
主要思路：用步長分組，每個分組進行插入排序，再慢慢減小步長，當步長為1的時候完成一次插入排序， 希爾排序的時間復雜度是：O（nlogn）～O（n2），平均時間復雜度大致是O(n^1.5)
publicstaticvoidshellSort(int[]arr){
intj;
for(intgap=arr.length/2;gap>0;gap/=2){
for(inti=gap;i<arr.length;i++){
inttemp=arr[i];
for(j=i;j>=gap&&temp<arr[j-gap];j-=gap){
arr[j]=arr[j-gap];
}
arr[j]=temp;
}
}
}
Ⅶ 排序的箱排序
已知一組無序正整數數據a[1]、[2]、……a[n]，需將其按升序排列。首先定義一個數組x[m],且m>=a[1]、a[2]、……a[n]，接著循環n次，每次x[a]++.
優點：快，效率達到O(1)
缺點：數據范圍必須為正整數並且比較小
箱排序(Bin Sort)
1、箱排序的基本思想
箱排序也稱桶排序(Bucket Sort)，其基本思想是：設置若干個箱子，依次掃描待排序的記錄R[0]，R[1]，…，R[n-1]，把關鍵字等於k的記錄全都裝入到第k個箱子里(分配)，然後按序號依次將各非空的箱子首尾連接起來(收集)。
【例】要將一副混洗的52張撲克牌按點數A<2<…<J<Q<K排序，需設置13個箱子，排序時依次將每張牌按點數放入相應的箱子里，然後依次將這些箱子首尾相接，就得到了按點數遞增序排列的一副牌。
2、箱排序中，箱子的個數取決於關鍵字的取值范圍。
若R[0..n-1]中關鍵字的取值范圍是0到m-1的整數，則必須設置m個箱子。因此箱排序要求關鍵字的類型是有限類型，否則可能要無限個箱子。
3、箱子的類型應設計成鏈表為宜
一般情況下每個箱子中存放多少個關鍵字相同的記錄是無法預料的，故箱子的類型應設計成鏈表為宜。
4、為保證排序是穩定的，分配過程中裝箱及收集過程中的連接必須按先進先出原則進行。
（1） 實現方法一
每個箱子設為一個鏈隊列。當一記錄裝入某箱子時，應做人隊操作將其插入該箱子尾部；而收集過程則是對箱子做出隊操作，依次將出隊的記錄放到輸出序列中。
（2） 實現方法二
若輸入的待排序記錄是以鏈表形式給出時，出隊操作可簡化為是將整個箱子鏈表鏈接到輸出鏈表的尾部。這只需要修改輸出鏈表的尾結點中的指針域，令其指向箱子鏈表的頭，然後修改輸出鏈表的尾指針，令其指向箱子鏈表的尾即可。
5、演算法簡析
分配過程的時間是O(n)；收集過程的時間為O(m) （採用鏈表來存儲輸入的待排序記錄）或O(m+n)。因此，箱排序的時間為O(m+n)。若箱子個數m的數量級為O(n)，則箱排序的時間是線性的，即O(n)。
注意：
箱排序實用價值不大，僅適用於作為基數排序的一個中間步驟。
歸並排序
歸並排序是多次將兩個或兩個以上的有序表合並成一個新的有序表。最簡單的歸並是直接將兩個有序的子表合並成一個有序的表。
歸並排序是穩定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括弧中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優勢的地方. program guibing;
type
arr=array[1..100] of integer;
var
a,b,c:arr;
i:integer;
procere gb(r:arr;l,m,n:integer;var r2:arr);
var
i,j,k,p:integer;
begin
i:=l;
j:=m+1;
k:=l-1;
while (i<=m)and (j<=n) do
begin
k:=k+1;
if r[i]<=r[j] then
begin
r2[k]:=r[i];
i:=i+1
end
else
begin
r2[k]:=r[j];
j:=j+1
end
end;
if i<=m then
for p:=i to m do
begin
k:=k+1;
r2[k]:=r[p]
end;
if j<=n then
for p:=j to n do
begin
k:=k+1;
r2[k]:=r[p]
end;
end;
procere gp( var r,r1:arr;s,t:integer);
var
k:integer;
c:arr;
begin
if s=t then r1[s]:=r[s]
else
begin
k:=(s+t) div 2;
gp(r,c,s,k);
gp(r,c,k+1,t);
gb(c,s,k,t,r1)
end;
end;
begin
readln(n);
for i:= 1 to n do
read(a[i]);
gp(a,b,1,n);
for i:=1 to n do
write(b[i],' ');
writeln;
end.
Ⅷ pascal桶排序的代碼！！！
const max = 100000; // 輸入數據的最大值
var
f:array [1..max] of boolean;
n,m,i:longint;
begin
readln(n);
fillchar(used,sizeof(used),false);
for i:=1 to n do
begin
read(m); // 讀入
used[m]:=true;
end;
for i:=1 to max do
if used[i] then write(i,' ');
end.
// 該程序適用於輸入元素都不相等的情況
const max = 100000; // 輸入數據的最大值
var
f:array [1..max] of longint;
n,m,i,j:longint;
begin
readln(n);
fillchar(used,sizeof(used),0);
for i:=1 to n do
begin
read(m); // 讀入
inc(used[m]);
end;
for i:=1 to max do
if used[i]>0 then
for j:=1 to used[i] do write(i,' ');
end.
// 該程序適用於輸入元素有相等的情況
Ⅸ 急求c語言寫的各種排序代碼
數據結構作業吧
1.簡單選擇排序
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define N 8
typedef int KeyType;
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */
typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */
int SelectMinKey(SqList L,int i)
{ /* 返回在L.r[i..L.length]中key最小的記錄的序號 */
KeyType min;
int j,k;
k=i; /* 設第i個為最小 */
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
if(L.r[j].key<min) /* 找到更小的 */
{
k=j;
min=L.r[j].key;
}
return k;
}
void SelectSort(SqList *L)
{ /* 對順序表L作簡單選擇排序。演算法10.9 */
int i,j;
RedType t;
for(i=1;i<(*L).length;++i)
{ /* 選擇第i小的記錄，並交換到位 */
j=SelectMinKey(*L,i); /* 在L.r[i..L.length]中選擇key最小的記錄 */
if(i!=j)
{ /* 與第i個記錄交換 */
t=(*L).r[i];
(*L).r[i]=(*L).r[j];
(*L).r[j]=t;
}
}
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(&l);
printf("排序後:\n");
print(l);
system("pause");
return 0;
}
2.冒泡排序
#include<stdio.h>
#include<stdlib.h>
#define N 8
void bubble_sort(int a[],int n)
{ /* 將a中整數序列重新排列成自小至大有序的整數序列(起泡排序) */
int i,j,t;
int change;
for(i=n-1,change=1;i>1&&change;--i)
{
change=0;
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=1;
}
}
}
void print(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}
int main()
{
int d[N]={49,38,65,97,76,13,27,49};
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序後:\n");
print(d,N);
system("pause");
return 0;
}
3.歸並排序
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define N 7
typedef int KeyType;
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */
typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */
void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ /* 將有序的SR[i..m]和SR[m+1..n]歸並為有序的TR[i..n] 演算法10.12 */
int j,k,l;
for(j=m+1,k=i;i<=m&&j<=n;++k) /* 將SR中記錄由小到大地並入TR */
if LQ(SR[i].key,SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++];
if(i<=m)
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; /* 將剩餘的SR[i..m]復制到TR */
if(j<=n)
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; /* 將剩餘的SR[j..n]復制到TR */
}
void MSort(RedType SR[],RedType TR1[],int s, int t)
{ /* 將SR[s..t]歸並排序為TR1[s..t]。演算法10.13 */
int m;
RedType TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; /* 將SR[s..t]平分為SR[s..m]和SR[m+1..t] */
MSort(SR,TR2,s,m); /* 遞歸地將SR[s..m]歸並為有序的TR2[s..m] */
MSort(SR,TR2,m+1,t); /* 遞歸地將SR[m+1..t]歸並為有序的TR2[m+1..t] */
Merge(TR2,TR1,s,m,t); /* 將TR2[s..m]和TR2[m+1..t]歸並到TR1[s..t] */
}
}
void MergeSort(SqList *L)
{ /* 對順序表L作歸並排序。演算法10.14 */
MSort((*L).r,(*L).r,1,(*L).length);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
MergeSort(&l);
printf("排序後:\n");
print(l);
system("pause");
return 0;
}
4.快速排序:
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define N 8
typedef int KeyType;
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */
typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */
int Partition(SqList *L,int low,int high)
{ /* 交換順序表L中子表L.r[low..high]的記錄，使樞軸記錄到位， */
/* 並返回其所在位置，此時在它之前(後)的記錄均不大(小)於它。演算法10.6(a) */
RedType t;
KeyType pivotkey;
pivotkey=(*L).r[low].key; /* 用子表的第一個記錄作樞軸記錄 */
while(low<high)
{ /* 從表的兩端交替地向中間掃描 */
while(low<high&&(*L).r[high].key>=pivotkey)
--high;
t=(*L).r[low]; /* 將比樞軸記錄小的記錄交換到低端 */
(*L).r[low]=(*L).r[high];
(*L).r[high]=t;
while(low<high&&(*L).r[low].key<=pivotkey)
++low;
t=(*L).r[low]; /* 將比樞軸記錄大的記錄交換到高端 */
(*L).r[low]=(*L).r[high];
(*L).r[high]=t;
}
return low; /* 返回樞軸所在位置 */
}
void QSort(SqList *L,int low,int high)
{ /* 對順序表L中的子序列L.r[low..high]作快速排序。演算法10.7 */
int pivotloc;
if(low<high)
{ /* 長度大於1 */
pivotloc=Partition(L,low,high); /* 將L.r[low..high]一分為二 */
QSort(L,low,pivotloc-1); /* 對低子表遞歸排序，pivotloc是樞軸位置 */
QSort(L,pivotloc+1,high); /* 對高子表遞歸排序 */
}
}
void QuickSort(SqList *L)
{ /* 對順序表L作快速排序。演算法10.8 */
QSort(L,1,(*L).length);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
QuickSort(&l);
printf("排序後:\n");
print(l);
system("pause");
return 0;
}