希尔排序c语言算法
Ⅰ c语言希尔排序
voidShellInsertSort(inta[],intn,intdk)
{
for(inti=dk;i<n;++i){
if(a[i]<a[i-dk]){//若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
intj=i-dk;
intx=a[i];//复制为哨兵，即存储待排序元素
a[i]=a[i-dk];//首先后移一个元素
while(x<a[j]){//查找在有序表的插入位置
a[j+dk]=a[j];
j-=dk;//元素后移
}
a[j+dk]=x;//插入到正确位置
}
}
}
/**
*先按增量d（n/2,n为要排序数的个数进行希尔排序
*
*/
voidshellSort(inta[],intn){
intdk=n/2;
while(dk>=1){
ShellInsertSort(a,n,dk);
dk=dk/2;
}
}
Ⅱ 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);
}
Ⅲ 希尔排序怎么排啊
下标0123456789
数组4938659726132750554(原数组)
增量=5,[0]=49与[5]=13为一组,互换为1349(排序是从小到大)
[1]=38与[6]=27为一组,互换为2738
[2]=65与[7]=50为一组,互换为5065
[3]=97与[8]=55为一组,互换为5597
[4]=26与[9]=4为一组,互换为426
增量=5的排序结果是:1327505544938659726
下标0123456789
数组1327505544938659726(第一趟之后)
增量=2,[0]=13,[2]=50,[4]=4,[6]=38,[8]=97为一组,
互换之后,[0]=4,[2]=13,[4]=38,[6]=50,[8]=97
[1]=27,[3]=55,[5]=49,[7]=65,[9]=26为一组,
互换之后,[1]=26,[3]=27,[5]=49,[7]=55,[9]=65
增量=2的排序结果是:4261327384950559765
下标0123456789
数组4261327384950559765(第二趟之后)
增量=1,数组里的10个数据作为一组,其中,
[1]=26有[2]=13互换为1326
[8]=97与[9]=65互换为6597
增量=1的排序结果是:4132627384950556597
//C语言测试代码
//希尔排序法(自定增量)
#include<stdio.h>
#include<stdlib.h>
voidprintData(intdata[],intn)//打印数组
{
inti;
for(i=0;i<n;i++)
{
printf("%d",data[i]);
}
printf(" ");
}
//希尔排序(从小到大)
voidshell(intdata[],intcount)
{
intoffset_a[3]={5,2,1};//每一趟的增量
intlen;
intpos;
intoffset;
inti,j;
inttemp;
len=sizeof(offset_a)/sizeof(int);
for(i=0;i<len;i++)
{
offset=offset_a[i];
for(j=offset;j<count;j++)
{
temp=data[j];
pos=j-offset;
while(temp<data[pos]&&pos>=0&&j<=count)
{
data[pos+offset]=data[pos];
pos=pos-offset;
}
data[pos+offset]=temp;
}
printf("增量=%d,排序结果:",offset);
printData(data,count);
}
}
intmain(void)
{
intdata[]={49,38,65,97,26,13,27,50,55,4};
intcount;
count=sizeof(data)/sizeof(int);
printf("原数组:");
printData(data,count);
shell(data,count);
printf(" 最后的排序结果:");
printData(data,count);
return0;
}
Ⅳ 怎样用C语言对一串整行数从大到小排序
方法太多了，当然各种时间排序的时间复杂度和空间复杂度不同、稳定性也不同。最简单的我觉得就是冒泡排序了，也最形像。/*
================================================
功能：选择排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述： 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环
到倒数第二个数和最后一个数比较为止。 选择排序是不稳定的。算法复杂度O(n2)--[n的平方]
=====================================================
*/
void select_sort(int *x, int n)
{
int i, j, min, t; for (i=0; i<n-1; i++) /*要选择的次数：0~n-2共n-1次*/
{
min = i; /*假设当前下标为i的数最小，比较后再调整*/
for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/
{
if (*(x+j) < *(x+min))
{
min = j; /*如果后面的数比前面的小，则记下它的下标*/
}
}
if (min != i) /*如果min在循环中改变了，就需要交换数据*/
{
t = *(x+i);
*(x+i) = *(x+min);
*(x+min) = t;
}
}
}
/*
================================================
功能：直接插入排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述： 在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
也是排好顺序的。如此反复循环，直到全部排好顺序。
直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void insert_sort(int *x, int n)
{
int i, j, t; for (i=1; i<n; i++) /*要选择的次数：1~n-1共n-1次*/
{
/*
暂存下标为i的数。注意：下标从1开始，原因就是开始时
第一个数即下标为0的数，前面没有任何数，单单一个，认为
它是排好顺序的。
*/
t=*(x+i);
for (j=i-1; j>=0 && t<*(x+j); j--) /*注意：j=i-1，j--，这里就是下标为i的数，在它前面有序列中找插入位置。*/
{
*(x+j+1) = *(x+j); /*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小，它要放在最前面，j==-1，退出循环*/
} *(x+j+1) = t; /*找到下标为i的数的放置位置*/
}
}
/*
================================================
功能：冒泡排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述： 在要排序的一组数中，对当前还未排好序的范围内的全部数，自上
而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较
小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要
求相反时，就将它们互换。
下面是一种改进的冒泡算法，它记录了每一遍扫描后最后下沉数的
位置k，这样可以减少外层循环扫描的次数。 冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/void bubble_sort(int *x, int n)
{
int j, k, h, t;
for (h=n-1; h>0; h=k) /*循环到没有比较范围*/
{
for (j=0, k=0; j<h; j++) /*每次预置k=0，循环扫描后更新k*/
{
if (*(x+j) > *(x+j+1)) /*大的放在后面，小的放到前面*/
{
t = *(x+j);
*(x+j) = *(x+j+1);
*(x+j+1) = t; /*完成交换*/
k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
}
}
}
}
/*
================================================
功能：希尔排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为
增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中
记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成
一组，排序完成。
下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，
以后每次减半，直到增量为1。 希尔排序是不稳定的。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t; for (h=n/2; h>0; h=h/2) /*控制增量*/
{
for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/
{
t = *(x+j);
for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
}/*
================================================
功能：快速排序
输入：数组名称（也就是数组首地址）、数组中起止元素的下标
================================================
*/
/*
====================================================
算法思想简单描述： 快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟
扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次
扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只
减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）
的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理
它左右两边的数，直到基准点的左右只有一个元素为止。它是由
C.A.R.Hoare于1962年提出的。
显然快速排序可以用递归实现，当然也可以用栈化解递归实现。下面的
函数是用递归实现的，有兴趣的朋友可以改成非递归的。 快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)
=====================================================
*/
void quick_sort(int *x, int low, int high)
{
int i, j, t; if (low < high) /*要排序的元素起止下标，保证小的放在左边，大的放在右边。这里以下标为low的元素为基准点*/
{
i = low;
j = high;
t = *(x+low); /*暂存基准点的数*/ while (i<j) /*循环扫描*/
{
while (i<j && *(x+j)>t) /*在右边的只要比基准点大仍放在右边*/
{
j--; /*前移一个位置*/
} if (i<j)
{
*(x+i) = *(x+j); /*上面的循环退出：即出现比基准点小的数，替换基准点的数*/
i++; /*后移一个位置，并以此为基准点*/
} while (i<j && *(x+i)<=t) /*在左边的只要小于等于基准点仍放在左边*/
{
i++; /*后移一个位置*/
} if (i<j)
{
*(x+j) = *(x+i); /*上面的循环退出：即出现比基准点大的数，放到右边*/
j--; /*前移一个位置*/
}
} *(x+i) = t; /*一遍扫描完后，放到适当位置*/
quick_sort(x,low,i-1); /*对基准点左边的数再执行快速排序*/
quick_sort(x,i+1,high); /*对基准点右边的数再执行快速排序*/
}
}
/*
================================================
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述： 堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当
满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)
时称之为堆。在这里只讨论满足前者条件的堆。 由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以
很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，
使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点
交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点
的堆，并对它们作交换，最后得到有n个节点的有序序列。 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素
交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数
实现排序的函数。 堆排序是不稳定的。算法时间复杂度O(nlog2n)。*/
/*
功能：渗透建堆
输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始
*/
void sift(int *x, int n, int s)
{
int t, k, j; t = *(x+s); /*暂存开始元素*/
k = s; /*开始元素下标*/
j = 2*k + 1; /*右子树元素下标*/ while (j<n)
{
if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整。*/
{
j++;
} if (t<*(x+j)) /*调整*/
{
*(x+k) = *(x+j);
k = j; /*调整后，开始元素也随之调整*/
j = 2*k + 1;
}
else /*没有需要调整了，已经是个堆了，退出循环。*/
{
break;
}
}
*(x+k) = t; /*开始元素放到它正确位置*/
}
/*
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
*/
void heap_sort(int *x, int n)
{
int i, k, t;
int *p; for (i=n/2-1; i>=0; i--)
{
sift(x,n,i); /*初始建堆*/
}
for (k=n-1; k>=1; k--)
{
t = *(x+0); /*堆顶放到最后*/
*(x+0) = *(x+k);
*(x+k) = t;
sift(x,k,0); /*剩下的数再建堆*/
}
}
void main()
{
#define MAX 4
int *p, i, a[MAX];
/*录入测试数据*/
p = a;
printf("Input %d number for sorting :\n",MAX);
for (i=0; i<MAX; i++)
{
scanf("%d",p++);
}
printf("\n"); /*测试选择排序*/
p = a;
select_sort(p,MAX);
/**/
/*测试直接插入排序*/ /*
p = a;
insert_sort(p,MAX);
*/
/*测试冒泡排序*/ /*
p = a;
insert_sort(p,MAX);
*/ /*测试快速排序*/ /*
p = a;
quick_sort(p,0,MAX-1);
*/ /*测试堆排序*/ /*
p = a;
heap_sort(p,MAX);
*/ for (p=a, i=0; i<MAX; i++)
{
printf("%d ",*p++);
}
printf("\n");
system("pause");
}
Ⅳ C语言 各常见排序法的时间复杂度 急 请简单说明
选择排序算法复杂度是O(n^2)。
插入排序是O(n^2)
快速排序快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n^2)。
堆排序算法时间复杂度O(nlogn)。
归并排序的时间复杂度是O(nlog2n)。
Ⅵ 什么是希尔排序法
基本思想：
将整个无序序列分割成若干小的子序列分别进行插入排序。
序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般采用：ht=2t-1,1≤t≤[log2n]，其中n为待排序序列的长度。
void prshl(p,n)
int n;double p[];
{
int k,j,i;
double t;
k=n/2;
while(k>0)
{
for(j=k;j<=n-1;j++)
{
t=p[j];i=j-k;
while((i>=0)&&(p[i]>t))
{
p[i+k]=p[i];i=i-k;
}
p[i+k]=t;
}
k=k/2;
}
return;
}
希尔排序(缩小增量法)
属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止
初始：d＝5
49 38 65 97 76 13 27 49* 55 04
|---------------|
38 27
|--------------|
65 49*
|--------------|
97 55
|---------------|
|76-------------04|
一趟结果
d=3 13 27 49*55 04 49 38 65 97 76
|--------|--------|----------|
27 04 65
|--------|-------|
49* 49 97
|--------|---------|
二趟结果
13 04 49*38 27 49 66 65 97 76
d=1
三趟结果
04 13 27 38 49*49 55 65 76 97
Ⅶ C语言数据结构希尔排序
void main()
{
datatype R[MAXNUM];
int d[6]=[50,25,12,6,3,2,1];
for(int i=0;i<MAXNUM;i++)
scanf("%d",&R[i].key);
ShellSort(R,MAXNUM,d,6);
for(int i=0;i<MAXNUM;i++)
printf("%d",R[i].key);
}
Ⅷ C语言排序算法一共多少种
选择排序
#include<iostream>
usingnamespacestd;
voidselect_sort(intarr[],intnum);
voidoutput_array(intarr[],intnum);
intmain()
{
inta[10];
for(inti=0;i<10;i++)
{
cin>>a[i];
}
select_sort(a,10);
output_array(a,10);
return0;
}
voidselect_sort(intarray[],intn)//形参array是数组名
{
inti,j,k,t;
for(i=0;i<n-1;i++)
{
k=i;//先设第i个就为最小
for(j=i+1;j<n;j++)
if(array[j]<array[k])
k=j;//通过循环，得到k为最小
t=array[k];//交换a[i]和a[k]
array[k]=array[i];
array[i]=t;
}
return;
}
voidoutput_array(intarr[],intnum)
{
inti;
for(i=0;i<num;i++)
{
cout<<arr[i];
cout<<endl;
}
return;
}
2.冒泡排序
#include<stdio.h>
intmain()
{
inti,j,a[10],t;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
if(a[i]>a[j])
{
t=a[j];
a[j]=a[i];
a[i]=t;
}
for(i=0;i<10;i++)
printf("%d",a[i]);
return0;
}
3.堆排序
#include<iostream>
usingnamespacestd;
voidpaii(inta[20],inti,intm)
{
intk,t;
t=a[i];
k=2*i+1;
while(k<m)
{
if((k<m-1)&&(a[k]<a[k+1]))
k++;
if(t<a[k])
{
a[i]=a[k];
i=k;
k=2*i+1;
}
elsebreak;
}
a[i]=t;
}
voidipai(inta[20],intn)
{
inti,k;
for(i=n/2-1;i>=0;i--)
paii(a,i,n);
for(i=n-1;i>=1;i--)
{
k=a[0];
a[0]=a[i];
a[i]=k;
paii(a,0,i);
}}
intmain()
{
inta[10],i;
for(i=0;i<10;i++)
cin>>a[i];
ipai(a,10);
for(i=0;i<10;i++)
cout<<a[i]<<endl;
}
4.快速排序
#include<iostream>
usingnamespacestd;
voidQuicksort(inta[],intlow,inthigh)
{
if(low>=high)
{
return;
}
intfirst=low;
intlast=high;
intkey=a[first];
while(first<last)
{
while(first<last&&a[last]>=key)
--last;
a[first]=a[last];
while(first<last&&a[first]<=key)
++first;
a[last]=a[first];
}
a[first]=key;
Quicksort(a,low,first-1);
Quicksort(a,last+1,high);
}
intmain()
{
inti,a[100],x,n=0;
while(cin>>x)
{
a[n]=x;
n++;
}
n--;
Quicksort(a,0,n);
for(i=0;i<=n;i++)
cout<<a[i]<<"";
cout<<endl;
return0;
}
5. 基数排序
#include<stdio.h>
#include<stdlib.h>
intmain(){
intdata[10]={73,22,93,43,55,14,82,65,39,81};//对十个数进行排序
inttemp[10][10]={0};//构造一个临时二维数组，其值为0
intorder[10]={0};//构造一维数组，其值为0
inti,j,k,n,lsd;
k=0;n=1;
for(i=0;i<10;i++)printf("%d",data[i]);//在排序前，对这10个数打印一遍
putchar(' ');
while(n<=10){
for(i=0;i<10;i++){
lsd=((data[i]/n)%10);//lsd先对个位取余，然后再对十位取余，注意循环
temp[lsd][order[lsd]]=data[i];//temp[3][0]=73,temp[2][0]=22,temp[3][1]=93,temp[3][2]=43,⋯⋯
order[lsd]++;//需要区分的是lsd和order[lsd]，这两个不是一样的概念嗷
}
printf(" 重新排列:");
for(i=0;i<10;i++){
if(order[i]!=0)
for(j=0;j<order[i];j++){
data[k]=temp[i][j];
printf("%d",data[k]);
k++;
}
order[i]=0;
}
n*=10;//第二次用十位
k=0;
}
putchar(' ');
printf(" 排序后:");
for(i=0;i<10;i++)printf("%d",data[i]);
return0;
}
6.希尔排序
#include<iostream>
usingnamespacestd;
voidshell_sort(inta[],intn);
intmain()
{
intn,a[10000];
cin>>n;
for(inty=0;y<n;y++)
cin>>a[y];
shell_sort(a,n);
for(inti=0;i<n;i++)
cout<<a[i]<<"";
cout<<endl;
}
voidshell_sort(inta[],intn)
{
intgap,k,temp;//定义增量；
for(gap=3;gap>0;gap--)//设置初始增量，递减；
{
for(inti=0;i<gap;i++)//按增量分组；
{
for(intj=i+gap;j<n;j=j+gap)//每组分别比较大小；
{
if(a[j]<a[j-gap])
{
temp=a[j];
k=j-gap;
while(k>=0&&a[k]>temp)
{
a[k+gap]=a[k];
k=k-gap;
}
a[k+gap]=temp;
}
}
}
}
}
7.归并排序
#include<iostream>
usingnamespacestd;
voidMergeSort(intp[],ints,intm,intt)
{
intq[100];//q[100]用来存放排好的序列
inti=s;
intj=m+1;
intk=s;
while(i<=m&&j<=t)
{
if(p[i]<=p[j])
q[k++]=p[i++];
else
q[k++]=p[j++];
}
if(i<=m)
while(i<=m)
q[k++]=p[i++];
elsewhile(j<=t)
q[k++]=p[j++];
for(intn=s;n<=t;n++)
p[n]=q[n];
}
voidMerge(intp[],ints,intt)
{
if(s<t)
{
intm=(s+t)/2;//将数组分成两半
Merge(p,s,m);//递归拆分左数组
Merge(p,m+1,t);//递归拆分右数组
MergeSort(p,s,m,t);//合并数组
}
}
intmain()
{
intn;
intp[100];
cin>>n;
for(inti=0;i<n;i++)
cin>>p[i];
Merge(p,0,n-1);
for(intj=0;j<n;j++)
cout<<p[j]<<"";
cout<<endl;
return0;
}
排序方法基本就这些，还有双向冒泡这种拓展的排序方法，还有直接排序如桶排序