基数排序算法代码

A. C语言（简单的）编写程序输入一维整形数组a[10],将其按由小到大排序后输出

这个链稿首应该用起泡法排序算法。

#include<stdio.h>

intmain(){

inta[10];inti,j,k;

printf("input10numbers: ");

for(i=0;i<10;i++）{//输入十个数，一次循环输入10次

scanf("%d",&a[i]);

printf(" ");//换行

for(j=0;j<9;j++)//从小到大换行经典方法四行敬肆

for(i=0;i<9;i++)

if(a[i]>a[i+1])

{t=a[i];a[i]=a[i+1];a[i+1]=t;}

printf(”thesortednumbers: ”）；

for（i=0;i<10;i++）

printf("%d",a[i]);

printf(" ");

}

}

结果棚数演示：

B. C语言排序

//总共给你整理了7种排序算法：希尔排序，链式基数排序，归并排序
//起泡排序，简单选择排序，树形选择排序，堆排序,先自己看看吧，
//看不懂可以再问身边的人或者查资料,既然可以上网，我相信你所在的地方信息流通方式应该还行,所有的程序全部在VC++6.0下编译通过
//希尔排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};

struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
void ShellInsert(SqList &L,int dk)
{ // 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比，
// 作了以下修改：
// 1.前后记录位置的增量是dk,而不是1;
// 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。算法10.4
int i,j;
for(i=dk+1;i<=L.length;++i)
if LT(L.r[i].key,L.r[i-dk].key)
{ // 需将L.r[i]插入有序增量子表
L.r[0]=L.r[i]; // 暂存在L.r[0]
for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j]; // 记录后移，查找插入位置
L.r[j+dk]=L.r[0]; // 插入
}
}

void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
printf("\n");
}

void print1(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

void ShellSort(SqList &L,int dlta[],int t)
{ // 按增量序列dlta[0..t-1]对顺序表L作希尔排序。算法10.5
int k;
for(k=0;k<t;++k)
{
ShellInsert(L,dlta[k]); // 一趟增量为dlta[k]的插入排序
printf("第%d趟排序结果: ",k+1);
print(L);
}
}

#define N 10
#define T 3
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}};
SqList l;
int dt[T]={5,3,1}; // 增量序列数组
for(int i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前: ");
print(l);
ShellSort(l,dt,T);
printf("排序后: ");
print1(l);
}

/*****************************************************************/
//链式基数排序
typedef int InfoType; // 定义其它数据项的类型
typedef int KeyType; // 定义RedType类型的关键字为整型
struct RedType // 记录类型(同c10-1.h)
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项
};
typedef char KeysType; // 定义关键字类型为字符型
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
#define MAX_NUM_OF_KEY 8 // 关键字项数的最大值
#define RADIX 10 // 关键字基数，此时是十进制整数的基数
#define MAX_SPACE 1000
struct SLCell // 静态链表的结点类型
{
KeysType keys[MAX_NUM_OF_KEY]; // 关键字
InfoType otheritems; // 其它数据项
int next;
};

struct SLList // 静态链表类型
{
SLCell r[MAX_SPACE]; // 静态链表的可利用空间，r[0]为头结点
int keynum; // 记录的当前关键字个数
int recnum; // 静态链表的当前长度
};

typedef int ArrType[RADIX];
void InitList(SLList &L,RedType D[],int n)
{ // 初始化静态链表L（把数组D中的数据存于L中）
char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
int i,j,max=D[0].key; // max为关键字的最大值
for(i=1;i<n;i++)
if(max<D[i].key)
max=D[i].key;
L.keynum=int(ceil(log10(max)));
L.recnum=n;
for(i=1;i<=n;i++)
{
L.r[i].otheritems=D[i-1].otherinfo;
itoa(D[i-1].key,c,10); // 将10进制整型转化为字符型,存入c
for(j=strlen(c);j<L.keynum;j++) // 若c的长度<max的位数,在c前补'0'
{
strcpy(c1,"0");
strcat(c1,c);
strcpy(c,c1);
}
for(j=0;j<L.keynum;j++)
L.r[i].keys[j]=c[L.keynum-1-j];
}
}

int ord(char c)
{ // 返回k的映射(个位整数)
return c-'0';
}

void Distribute(SLCell r[],int i,ArrType f,ArrType e) // 算法10.15
{ // 静态键表L的r域中记录已按(keys[0],…,keys[i-1])有序。本算法按
// 第i个关键字keys[i]建立RADIX个子表,使同一子表中记录的keys[i]相同。
// f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录
int j,p;
for(j=0;j<RADIX;++j)
f[j]=0; // 各子表初始化为空表
for(p=r[0].next;p;p=r[p].next)
{
j=ord(r[p].keys[i]); // ord将记录中第i个关键字映射到[0..RADIX-1]
if(!f[j])
f[j]=p;
else
r[e[j]].next=p;
e[j]=p; // 将p所指的结点插入第j个子表中
}
}

int succ(int i)
{ // 求后继函数
return ++i;
}

void Collect(SLCell r[],ArrType f,ArrType e)
{ // 本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成
// 一个链表，e[0..RADIX-1]为各子表的尾指针。算法10.16
int j,t;
for(j=0;!f[j];j=succ(j)); // 找第一个非空子表，succ为求后继函数
r[0].next=f[j];
t=e[j]; // r[0].next指向第一个非空子表中第一个结点
while(j<RADIX-1)
{
for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j)); // 找下一个非空子表
if(f[j])
{ // 链接两个非空子表
r[t].next=f[j];
t=e[j];
}
}
r[t].next=0; // t指向最后一个非空子表中的最后一个结点
}

void printl(SLList L)
{ // 按链表输出静态链表
int i=L.r[0].next,j;
while(i)
{
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" ");
i=L.r[i].next;
}
}

void RadixSort(SLList &L)
{ // L是采用静态链表表示的顺序表。对L作基数排序，使得L成为按关键字
// 自小到大的有序静态链表，L.r[0]为头结点。算法10.17
int i;
ArrType f,e;
for(i=0;i<L.recnum;++i)
L.r[i].next=i+1;
L.r[L.recnum].next=0; // 将L改造为静态链表
for(i=0;i<L.keynum;++i)
{ // 按最低位优先依次对各关键字进行分配和收集
Distribute(L.r,i,f,e); // 第i趟分配
Collect(L.r,f,e); // 第i趟收集
printf("第%d趟收集后:\n",i+1);
printl(L);
printf("\n");
}
}

void print(SLList L)
{ // 按数组序号输出静态链表
int i,j;
printf("keynum=%d recnum=%d\n",L.keynum,L.recnum);
for(i=1;i<=L.recnum;i++)
{
printf("keys=");
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" otheritems=%d next=%d\n",L.r[i].otheritems,L.r[i].next);
}
}

void Sort(SLList L,int adr[]) // 改此句(类型)
{ // 求得adr[1..L.length]，adr[i]为静态链表L的第i个最小记录的序号
int i=1,p=L.r[0].next;
while(p)
{
adr[i++]=p;
p=L.r[p].next;
}
}

void Rearrange(SLList &L,int adr[]) // 改此句(类型)
{ // adr给出静态链表L的有序次序，即L.r[adr[i]]是第i小的记录。
// 本算法按adr重排L.r，使其有序。算法10.18(L的类型有变)
int i,j,k;
for(i=1;i<L.recnum;++i) // 改此句(类型)
if(adr[i]!=i)
{
j=i;
L.r[0]=L.r[i]; // 暂存记录L.r[i]
while(adr[j]!=i)
{ // 调整L.r[adr[j]]的记录到位直到adr[j]=i为止
k=adr[j];
L.r[j]=L.r[k];
adr[j]=j;
j=k; // 记录按序到位
}
L.r[j]=L.r[0];
adr[j]=j;
}
}

#define N 10
void main()
{
RedType d[N]={{278,1},{109,2},{63,3},{930,4},{589,5},{184,6},{505,7},{269,8},{8,9},{83,10}};
SLList l;
int *adr;
InitList(l,d,N);
printf("排序前(next域还没赋值):\n");
print(l);
RadixSort(l);
printf("排序后(静态链表):\n");
print(l);
adr=(int*)malloc((l.recnum)*sizeof(int));
Sort(l,adr);
Rearrange(l,adr);
printf("排序后(重排记录):\n");
print(l);
}
/*******************************************/
//归并排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};

struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
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");
}

#define N 7
void 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);
}
/**********************************************/
//起泡排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
#define N 8
void bubble_sort(int a[],int n)
{ // 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序)
int i,j,t;
Status change;
for(i=n-1,change=TRUE;i>1&&change;--i)
{
change=FALSE;
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=TRUE;
}
}
}

void print(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}

void 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);
}
/****************************************************/
//简单选择排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};

struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
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");
}

#define N 8
void 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);
}
/************************************************/
//树形选择排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int InfoType; // 定义其它数据项的类型
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};

struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
void TreeSort(SqList &L)
{ // 树形选择排序
int i,j,j1,k,k1,l,n=L.length;
RedType *t;
l=(int)ceil(log(n)/log(2))+1; // 完全二叉树的层数
k=(int)pow(2,l)-1; // l层完全二叉树的结点总数
k1=(int)pow(2,l-1)-1; // l-1层完全二叉树的结点总数
t=(RedType*)malloc(k*sizeof(RedType)); // 二叉树采用顺序存储结构
for(i=1;i<=n;i++) // 将L.r赋给叶子结点
t[k1+i-1]=L.r[i];
for(i=k1+n;i<k;i++) // 给多余的叶子的关键字赋无穷大
t[i].key=INT_MAX;
j1=k1;
j=k;
while(j1)
{ // 给非叶子结点赋值
for(i=j1;i<j;i+=2)
t[i].key<t[i+1].key?(t[(i+1)/2-1]=t[i]):(t[(i+1)/2-1]=t[i+1]);
j=j1;
j1=(j1-1)/2;
}
for(i=0;i<n;i++)
{
L.r[i+1]=t[0]; // 将当前最小值赋给L.r[i]
j1=0;
for(j=1;j<l;j++) // 沿树根找结点t[0]在叶子中的序号j1
t[2*j1+1].key==t[j1].key?(j1=2*j1+1):(j1=2*j1+2);
t[j1].key=INT_MAX;
while(j1)
{
j1=(j1+1)/2-1; // 序号为j1的结点的双亲结点序号
t[2*j1+1].key<=t[2*j1+2].key?(t[j1]=t[2*j1+1]):(t[j1]=t[2*j1+2]);
}
}
free(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");
}

#define N 8
void 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);
TreeSort(l);
printf("排序后:\n");
print(l);
}
/****************************/
//堆排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};

struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};

typedef SqList HeapType; // 堆采用顺序表存储表示
void HeapAdjust(HeapType &H,int s,int m) // 算法10.10
{ // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数
// 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言)
RedType rc;
int j;
rc=H.r[s];
for(j=2*s;j<=m;j*=2)
{ // 沿key较大的孩子结点向下筛选
if(j<m&<(H.r[j].key,H.r[j+1].key))
++j; // j为key较大的记录的下标
if(!LT(rc.key,H.r[j].key))
break; // rc应插入在位置s上
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc; // 插入
}

void HeapSort(HeapType &H)
{ // 对顺序表H进行堆排序。算法10.11
RedType t;
int i;
for(i=H.length/2;i>0;--i) // 把H.r[1..H.length]建成大顶堆
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{ // 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换
t=H.r[1];
H.r[1]=H.r[i];
H.r[i]=t;
HeapAdjust(H,1,i-1); // 将H.r[1..i-1]重新调整为大顶堆
}
}

void print(HeapType H)
{
int i;
for(i=1;i<=H.length;i++)
printf("(%d,%d)",H.r[i].key,H.r[i].otherinfo);
printf("\n");
}

#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
HeapType h;
int i;
for(i=0;i<N;i++)
h.r[i+1]=d[i];
h.length=N;
printf("排序前:\n");
print(h);
HeapSort(h);
printf("排序后:\n");
print(h);
}

C. c++几种常见的排序程序

（1）“冒泡法”

冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：

void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/

{

int i,j,temp;

for(i=0;i<n-1;i++)

for(j=i+1;j<n;j++) /*注意循环的上下限*/

if(a[i]>a[j]) {

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

冒泡法原理简单，但其缺点是交换次数多，效率低。

下面介绍一种源自冒泡法但更有效率的方法“选择法”。

（2）“选择法”

选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换，提高了效率。

void choise(int *a,int n)

{

int i,j,k,temp;

for(i=0;i<n-1;i++) {

k=i; /*给记号赋值*/

for(j=i+1;j<n;j++)

if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/

if(i!=k) { /*当k!=i是才交换，否则a[i]即为最小*/

temp=a[i];

a[i]=a[k];

a[k]=temp;

}

}

}

选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。

（3）“快速法”

快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。下面分析其代码：

void quick(int *a,int i,int j)

{

int m,n,temp;

int k;

m=i;

n=j;

k=a[(i+j)/2]; /*选取的参照*/

do {

while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/

while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/

if(m<=n) { /*若找到且满足条件，则交换*/

temp=a[m];

a[m]=a[n];

a[n]=temp;

m++;

n--;

}

}while(m<=n);

if(m<j) quick(a,m,j); /*运用递归*/

if(n>i) quick(a,i,n);

}

（4）“插入法”

插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。

void insert(int *a,int n)

{

int i,j,temp;

for(i=1;i<n;i++) {

temp=a[i]; /*temp为要插入的元素*/

j=i-1;

while(j>=0&&temp<a[j]) { /*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/

a[j+1]=a[j];

j--;

}

a[j+1]=temp; /*插入*/

}

}

（5）“shell法”

shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序，再缩小k值（一般取其一半），再排序，直到k=1时完成排序。下面让我们来分析其代码：

void shell(int *a,int n)

{

int i,j,k,x;

k=n/2; /*间距值*/

while(k>=1) {

for(i=k;i<n;i++) {

x=a[i];

j=i-k;

while(j>=0&&x<a[j]) {

a[j+k]=a[j];

j-=k;

}

a[j+k]=x;

}

k/=2; /*缩小间距值*/

}

}

上面我们已经对几种排序法作了介绍，现在让我们写个主函数检验一下。

#include<stdio.h>

/*别偷懒，下面的"..."代表函数体，自己加上去哦！*/

void bubble(int *a,int n)

{

...

}

void choise(int *a,int n)

{

...

}

void quick(int *a,int i,int j)

{

...

}

void insert(int *a,int n)

{

...

}

void shell(int *a,int n)

{

...

}

/*为了打印方便，我们写一个print吧。*/[code]

void print(int *a,int n)

{

int i;

for(i=0;i<n;i++)

printf("%5d",a[i]);

printf("\n");

}

main()

{ /*为了公平，我们给每个函数定义一个相同数组*/

int a1[]={13,0,5,8,1,7,21,50,9,2};

int a2[]={13,0,5,8,1,7,21,50,9,2};

int a3[]={13,0,5,8,1,7,21,50,9,2};

int a4[]={13,0,5,8,1,7,21,50,9,2};

int a5[]={13,0,5,8,1,7,21,50,9,2};

printf("the original list:");

print(a1,10);

printf("according to bubble:");

bubble(a1,10);

print(a1,10);

printf("according to choise:");

choise(a2,10);

print(a2,10);

printf("according to quick:");

quick(a3,0,9);

print(a3,10);

printf("according to insert:");

insert(a4,10);

print(a4,10);

printf("according to shell:");

shell(a5,10);

print(a5,10);

}

D. 想问您一些排序算法的伪代码，谢啦

冒泡排序：网页链派皮接

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

C++自带的algorithm库函数中提供了排序算法。

稳定的

冒泡排序（bubble sort） — O(n^2）

鸡尾酒排序(Cocktail sort，双向的冒泡排序) — O(n^2）

插掘羡友入排序（insertion sort）— O(n^2)

桶排序（bucket sort）— O(n); 需要 O(k) 额外空间

计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外空间

合并排序（merge sort）— O(nlogn); 需要 O(n) 额外空间

原地合并排序— O(n^2)

二叉排序树排序 （Binary tree sort） — O(nlogn)期望判槐时间； O(n^2)最坏时间； 需要 O(n) 额外空间

鸽巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间

基数排序（radix sort）— O(n·k); 需要 O(n) 额外空间

Gnome 排序— O(n^2)

图书馆排序— O(nlogn) with high probability，需要 （1+ε)n额外空间

不稳定的

选择排序（selection sort）— O(n^2)

希尔排序（shell sort）— O(nlogn) 如果使用最佳的现在版本

组合排序— O(nlogn)

堆排序（heapsort）— O(nlogn)

平滑排序— O(nlogn)

快速排序（quicksort）— O(nlogn) 期望时间，O(n^2) 最坏情况； 对于大的、乱数列表一般相信是最快的已知排序

Introsort— O(nlogn)

耐心排序— O(nlogn+k) 最坏情况时间，需要 额外的 O(n+k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）

不实用的

Bogo排序— O(n×n!) 期望时间，无穷的最坏情况。

Stupid sort— O(n^3); 递归版本需要 O(n^2) 额外存储器

珠排序（Bead sort） — O(n) or O（√n)，但需要特别的硬件

Pancake sorting— O(n)，但需要特别的硬件

stooge sort——O（n^2.7）很漂亮但是很耗时

E. 如何实现 快速排序/基数排序/归并排序 ，任意一个的实现代码（8086汇编语言）

字节数组快排
.MODEL SMALL
.STACK
.DATA
ARRAY DB 12,45,13,9,45,48,68,32,5,11,121,122,125,255
COUNT EQU $-ARRAY
.CODE
.startup
MOV AX,COUNT
SUB AX,1
XOR DX,DX
MOV BX,OFFSET ARRAY
CALL QSORT
MOV CX,COUNT
AGAIN:
XOR AX,AX
MOV AL,BYTE PTR[BX]
CALL DSPAL
INC BX
LOOP AGAIN
MOV AH,4CH
INT 21H
;===========================================
QSORT PROC NEAR
CMP DX,AX
JGE EXIT
CALL PARTION
PUSH AX
PUSH CX
SUB CX,1
MOV AX,CX
CALL QSORT
POP CX
POP AX
ADD CX,1
MOV DX,CX
CALL QSORT
EXIT:
RET
QSORT ENDP
;==============================================
PARTION PROC NEAR
PUSH AX
PUSH DX
MOV SI,DX
MOV DI,AX
MOV DL,BYTE PTR[BX][SI]
MOV DH,BYTE PTR[BX][DI]
CALL SWAP
SUB AX,SI
MOV CX,AX
MOV DI,SI
MOV AL,DH
NEXT:
MOV DL,BYTE PTR[BX][SI]
CMP DL,AL
JAE SIGN
MOV DH,BYTE PTR[BX][DI]
CALL SWAP
INC DI
SIGN:
INC SI
LOOP NEXT
MOV DH,BYTE PTR[BX][DI]
MOV DL,AL
CALL SWAP
MOV CX,DI
POP DX
POP AX
RET
PARTION ENDP
;===================================================
SWAP PROC NEAR
XCHG DL,DH
MOV BYTE PTR[BX][SI],DL
MOV BYTE PTR[BX][DI],DH
RET
SWAP ENDP

;===============================
DSPAL PROC NEAR
PUSH AX
PUSH BX
PUSH CX
PUSH DX
PUSHF
XOR AH,AH
XOR CX,CX
MOV BL,10
@DSPAL1:
DIV BL
INC CX
MOV DL,AH
XOR AH,AH
OR DX,30H
PUSH DX
CMP AL,0
JNE @DSPAL1
MOV AH,2
@DISPAL2:
POP DX
INT 21H
LOOP @DISPAL2
MOV DL,32
INT 21H
POPF
POP DX
POP CX
POP BX
POP AX
RET
DSPAL ENDP
;================================
END

F. java 编写一个程序,输入3个整数,然后程序将对这三个整数按照从大到小进行排列

可以实现比较器Comparator来定制排序方案，同时使用Colletions.sort的方式进行排序，代码如下：

public void sortDesc(List<Long> s){
Collections.sort(s, new Comparator<Long>() {
public int compare(Long o1, Long o2) {
Long result = o2 - o1;
return result.intValue();
}
});
s.forEach(item->{
System.out.print(item +" ");
});
}

同时常用的比较排序算法主要有：型团冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

java的冒泡排序实现如下：顷租拍

publicstaticvoidbubbleSort(int[]arr){for(inti=0;i<arr.length-1;i++){for(intj=0;j<arr.length-i-1;j++){//-1为了防止溢出if(arr[j]>arr[j+1]){inttemp=arr[j];雀羡arr[j]=arr[j+1];arr[j+1]=temp;}}}}

还有非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

G. java中基数排序算法代码

/**
*冒泡法排序<br/>

*<li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li>
*<li>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</li>
*<li>针对所有的元素重复以上的步骤，除了最后一个。</li>
*<li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li>

*
*@paramnumbers
*需要排序的整型数组
*/
publicstaticvoidbubbleSort(int[]numbers){
inttemp;//记录临时中间值
intsize=numbers.length;//数组大小
for(inti=0;i<size-1;i++){
for(intj=i+1;j<size;j++){
if(numbers[i]<numbers[j]){//交换两数的位置
temp=numbers[i];
numbers[i]=numbers[j];
numbers[j]=temp;
}
}
}
}

H. 基数排序怎么排

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:005px0;padding:5px;border:1pxsolid#d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc100px);background-image:linear-gradient(#fff,#e5eecc100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1pxsolid#d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1pxsolid#d4d4d4;width:98%}div.code{width:98%;border:1pxsolid#d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.codediv{font-size:110%}div.codediv,div.codep,div.example_codep{font-family:"couriernew"}pre{margin:15pxauto;font:12px/20pxMenlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1pxsolid#ddd;border-left-width:4px;padding:10px15px}排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是基数排序算法：
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
1.基数排序vs计数排序vs桶排序基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；计数排序：每个桶只存储单一键值；桶排序：每个桶存储一定范围的数值；2.LSD基数排序动图演示
代码实现JavaScript实例//LSDRadixSortvarcounter=[];functionradixSort(arr,maxDigit){varmod=10;vardev=1;for(vari=0;i<maxDigit;i++,dev*=10,mod*=10){for(varj=0;j<arr.length;j++){varbucket=parseInt((arr[j]%mod)/dev);if(counter[bucket]==null){counter[bucket]=[];}counter[bucket].push(arr[j]);}varpos=0;for(varj=0;j<counter.length;j++){varvalue=null;if(counter[j]!=null){while((value=counter[j].shift())!=null){arr[pos++]=value;}}}}returnarr;}Java实例/***基数排序*考虑负数的情况还可以参考：https://code.i-harness.com/zh-CN/q/e98fa9*/{@Overridepublicint[]sort(int[]sourceArray)throwsException{//对arr进行拷贝，不改变参数内容int[]arr=Arrays.Of(sourceArray,sourceArray.length);intmaxDigit=getMaxDigit(arr);returnradixSort(arr,maxDigit);}/***获取最高位数*/privateintgetMaxDigit(int[]arr){intmaxValue=getMaxValue(arr);returngetNumLenght(maxValue);}privateintgetMaxValue(int[]arr){intmaxValue=arr[0];for(intvalue:arr){if(maxValue<value){maxValue=value;}}returnmaxValue;}protectedintgetNumLenght(longnum){if(num==0){return1;}intlenght=0;for(longtemp=num;temp!=0;temp/=10){lenght++;}returnlenght;}privateint[]radixSort(int[]arr,intmaxDigit){intmod=10;intdev=1;for(inti=0;i<maxDigit;i++,dev*=10,mod*=10){//考虑负数的情况，这里扩展一倍队列数，其中[0-9]对应负数，[10-19]对应正数(bucket+10)int[][]counter=newint[mod*2][0];for(intj=0;j<arr.length;j++){intbucket=((arr[j]%mod)/dev)+mod;counter[bucket]=arrayAppend(counter[bucket],arr[j]);}intpos=0;for(int[]bucket:counter){for(intvalue:bucket){arr[pos++]=value;}}}returnarr;}/***自动扩容，并保存数据**@paramarr*@paramvalue*/privateint[]arrayAppend(int[]arr,intvalue){arr=Arrays.Of(arr,arr.length+1);arr[arr.length-1]=value;returnarr;}}PHP实例functionradixSort($arr,$maxDigit=null){if($maxDigit===null){$maxDigit=max($arr);}$counter=[];for($i=0;$i<$maxDigit;$i++){for($j=0;$j<count($arr);$j++){preg_match_all('/d/',(string)$arr[$j],$matches);$numArr=$matches[0];$lenTmp=count($numArr);$bucket=array_key_exists($lenTmp-$i-1,$numArr)?intval($numArr[$lenTmp-$i-1]):0;if(!array_key_exists($bucket,$counter)){$counter[$bucket]=[];}$counter[$bucket][]=$arr[$j];}$pos=0;for($j=0;$j<count($counter);$j++){$value=null;if($counter[$j]!==null){while(($value=array_shift($counter[$j]))!==null){$arr[$pos++]=$value;}}}}return$arr;}C++实例intmaxbit(intdata[],intn)//辅助函数，求数据的最大位数{intmaxData=data[0];///<最大数///先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。for(inti=1;i<n;++i){if(maxData<data[i])maxData=data[i];}intd=1;intp=10;while(maxData>=p){//p*=10;//MaybeoverflowmaxData/=10;++d;}returnd;/*intd=1;//保存最大的位数intp=10;for(inti=0;i<n;++i){while(data[i]>=p){p*=10;++d;}}returnd;*/}voidradixsort(intdata[],intn)//基数排序{intd=maxbit(data,n);int*tmp=newint[n];int*count=newint[10];//计数器inti,j,k;intradix=1;for(i=1;i<=d;i++)//进行d次排序{for(j=0;j<10;j++)count[j]=0;//每次分配前清空计数器for(j=0;j<n;j++){k=(data[j]/radix)%10;//统计每个桶中的记录数count[k]++;}for(j=1;j<10;j++)count[j]=count[j-1]+count[j];//将tmp中的位置依次分配给每个桶for(j=n-1;j>=0;j--)//将所有桶中记录依次收集到tmp中{k=(data[j]/radix)%10;tmp[count[k]-1]=data[j];count[k]--;}for(j=0;j<n;j++)//将临时数组的内容复制到data中data[j]=tmp[j];radix=radix*10;}delete[]tmp;delete[]count;}C实例#include<stdio.h>#defineMAX20//#defineSHOWPASS#defineBASE10voidprint(int*a,intn){inti;for(i=0;i<n;i++){printf("%d ",a[i]);}}voidradixsort(int*a,intn){inti,b[MAX],m=a[0],exp=1;for(i=1;i<n;i++){if(a[i]>m){m=a[i];}}while(m/exp>0){intbucket[BASE]={0};for(i=0;i<n;i++){bucket[(a[i]/exp)%BASE]++;}for(i=1;i<BASE;i++){bucket[i]+=bucket[i-1];}for(i=n-1;i>=0;i--){b[--bucket[(a[i]/exp)%BASE]]=a[i];}for(i=0;i<n;i++){a[i]=b[i];}exp*=BASE;#ifdefSHOWPASSprintf("
PASS:");print(a,n);#endif}}intmain(){intarr[MAX];inti,n;printf("Entertotalelements(n<=%d):",MAX);scanf("%d",&n);n=n<MAX?n:MAX;printf("Enter%dElements:",n);for(i=0;i<n;i++){scanf("%d",&arr[i]);}printf("
ARRAY:");print(&arr[0],n);radixsort(&arr[0],n);printf("
SORTED:");print(&arr[0],n);printf("
");return0;}Lua实例--获取表中位数localmaxBit=function(tt)localweight=10;--十_制localbit=1;fork,vinpairs(tt)dowhilev>=weightdoweight=weight*10;bit=bit+1;endendreturnbit;end--基数排序localradixSort=function(tt)localmaxbit=maxBit(tt);localbucket={};localtemp={};localradix=1;fori=1,maxbitdoforj=1,10dobucket[j]=0;---清空桶endfork,vinpairs(tt)dolocalremainder=math.floor((v/radix))%10+1;bucket[remainder]=bucket[remainder]+1;--每_桶_量自_增加1endforj=2,10dobucket[j]=bucket[j-1]+bucket[j];--每个桶的数量=以前桶数量和+自个数量end--按照桶的位置，排序--这个是桶式排序，必须使用倒序，因为排序方法是从小到大，顺序下来，会出现大的在小的上面清空。fork=#tt,1,-1dolocalremainder=math.floor((tt[k]/radix))%10+1;temp[bucket[remainder]]=tt[k];bucket[remainder]=bucket[remainder]-1;endfork,vinpairs(temp)dott[k]=v;endradix=radix*10;endend;参考地址：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md
https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
以下是热心网友对基数排序算法的补充，仅供参考：热心网友提供的补充1：
java代码里，mod每次循环会乘10，但counter的行数是不需要变的，能包含[-9,9]就可以了。


for(inti=0;i<maxDigit;i++,dev*=10,mod*=10){
//考虑负数的情况，这里扩展一倍队列数，其中[0-9]对应负数，[10-19]对应正数(bucket+10)
int[][]counter=newint[20][0];

for(intj=0;j<arr.length;j++){
intbucket=((arr[j]%mod)/dev)+10;
counter[bucket]=arrayAppend(counter[bucket],arr[j]);
}

intpos=0;
for(int[]bucket:counter){
for(intvalue:bucket){
arr[pos++]=value;
}
}
}热心网友提供的补充2：
艾孜尔江补充使用C#基数排序算法如下:


///基数排序
staticvoidRadixSort(List<int>list)
{
intmaxValue=list.Max();//列表内部方法拿过来用用（在Linq中）
intit=0;//需要几趟
//maxvalue9-199-2999-3
//10^0<=910^1>9it=1
//10^0<9910^1<9910^2>99it=2
while(Math.Pow(10,it)<=maxValue)
{
List<List<int>>buckets=newList<List<int>>(10);//分10个桶对应0-9
for(inti=0;i<10;i++)
{
buckets.Add(newList<int>());
}//列表初始化大小
for(inti=0;i<list.Count;i++)//入桶
{
//989it=0989/10^it=989989%10=9;
intdigit=(int)((list[i])/(Math.Pow(10,it))%10);//得到对应桶
buckets[digit].Add(list[i]);
}//全部入桶
list.Clear();//依次取出来
for(inti=0;i<buckets.Count;i++)
{

I. 基数排序问题

sort1被调用3次，每次的while循环中都有明郑宏个激册barrel[i][j]=0;，而i和j是遍历的丛梁，似乎最后都成0了。没细看，只是大致猜测。

J. 求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;
}