箱排序代码
Ⅰ 谁能帮我把希尔排序·箱排序等等之类的排序都加上去我目前只写了快速排序，冒泡排序，选择排序上去
太晚了明天吧我先去睡了
Ⅱ 桶排序的算法
桶排序算法要求，数据的长度必须完全一样，程序过程要产生长度相同的数据，使用下面的方法：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;
}