135-1821-9792
最简单的办法：再增加一个数组int d0[13]={0,1,2,3,4,5,6,7,8,9,10,11,12}
创新互联建站坚持“要么做到，要么别承诺”的工作理念，服务领域包括：网站建设、做网站、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的和静网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！
当交换data数组中data[i]和data[j]时，同步地交换d0数组中d0[i]和d0[j]就可以了。这样当排序完成后，数据data[k]的排序前序号就是d0[k]。
#includestdio.h
#includestdlib.h
#include math.h
#define L 8 //排序元素个数
#define FALSE 0
#define TRUE 1
typedef struct
{
int key;
char otherinfo;
}RecType;
typedef RecType Seqlist[L+1];
int num; //定义排序趟数的全局变量
Seqlist R;
//直接插入排序
void Insertsort()
{
int i,j,k,m=0;
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t");
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=2;i=L;i++)
{
if(R[i].keyR[i-1].key)
{
R[0]=R[i];
j=i-1;
while(R[0].keyR[j].key)
{
R[j+1]=R[j];
j--;
}
R[j+1]=R[0];
}
m++;
printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",m);
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序最终结果是：\n\t\t");
for(i=1;i=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//希尔排序
void Shellsort()
{
int i,j,gap,x,m=0,k;
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t");
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
gap=L/2;
while(gap0)
{
for(i=gap+1;i=L;i++)
{
j=i-gap;
while(j0)
{
if(R[j].keyR[j+gap].key)
{
x=R[j].key;
R[j].key=R[j+gap].key;
R[j+gap].key=x;
j=j-gap;
}
else
{
j=0;
}
}
}
gap=gap/2;
m++;
printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",m);
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序最终结果是：\n\t\t");
for(i=1;i=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//冒泡排序
void Bubblesort()
{
int i,j,k;
int exchange;
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t");
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=1;iL;i++)
{
exchange=FALSE;
for(j=L;j=i+1;j--)
{
if(R[j].keyR[j-1].key)
{
R[0].key=R[j].key;
R[j].key=R[j-1].key;
R[j-1].key=R[0].key;
exchange=TRUE;
}
}
if(exchange)
{
printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",i);
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
}
printf("\n\t\t排序最终结果是：\n\t\t");
for(i=1;i=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
int Partition(int i,int j) //i和j为形式参数，分别代表low和high
{
RecType pirot=R[i];
while(ij)
{
while(ijR[j].key=pirot.key)
{
j--;
}
if(ij)
{
R[i++]=R[j];
}
while(ijR[j].key=pirot.key)
{
i++;
}
if(ij)
{
R[j--]=R[i];
}
}
R[i]=pirot;
return i;
}
//递归排序
void Quicksort(int low,int high)
{
int pirotpos,k;
if(lowhigh)
{
pirotpos=Partition(low,high);
num++;
printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",num);
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
Quicksort(low,pirotpos-1);
Quicksort(pirotpos+1,high);
}
}
//选择排序
void Selectsort()
{
int i,j,k,h;
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t");
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=1;iL;i++)
{
h=i;
for(j=i+1;j=L;j++)
{
if(R[j].keyR[h].key)
{
h=j;
}
}
if(h!=j)
{
R[0]=R[i];
R[i]=R[h];
R[h]=R[0];
}
printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",i);
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序最终结果是：\n\t\t");
for(i=1;i=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
void Merge(int low,int mm,int high)
{
int i=low,j=mm+1,p=0;
RecType *R1;
R1=new RecType[high-low+1];
if(!R1)
{
printf("内存不足！");
}
while(i=mmj=high)
{
R1[p++]=(R[i].key=R[j].key)?R[i++]:R[j++];
}
while(i=mm)
{
R1[p++]=R[i++];
}
while(j=high)
{
R1[p++]=R[j++];
}
for(p=0,i=low;i=high;p++,i++)
{
R[i]=R1[p];
}
}
void MergePass(int length)
{
int i;
for(i=1;i+2*length-1=L;i=i+2*length)
{
Merge(i,i+length-1,i+2*length-1);
}
if(i+length-1L)
{
Merge(i,i+length-1,L);
}
}
//归并排序
void Mergesort()
{
int length,k,m=0,i;
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t");
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(length=1;lengthL;length*=2)
{
MergePass(length);
m++;
printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",m);
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序最终结果是：\n\t\t");
for(i=1;i=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//堆建
void CreateHeap(int root,int index)
{
int j,temp,finish;
j=2*root;
temp=R[root].key;
finish=0;
while(j=indexfinish==0)
{
if(jindex)
{
if(R[j].keyR[j+1].key)
{
j++;
}
}
if(temp=R[j].key)
{
finish=1;
}
else
{
R[j/2].key=R[j].key;
j=j*2;
}
}
R[j/2].key=temp;
}
//堆排序
void Heapsort()
{
int i,j,temp,k;
for(i=(L/2);i=1;i--)
{
CreateHeap(i,L);
}
for(i=L-1,k=1;i=1;i--,k++)
{
temp=R[i+1].key;
R[i+1].key=R[1].key;
R[1].key=temp;
CreateHeap(1,i);
printf("\t\t第%d趟排序的结果为（按回车键开始排序）：\n\t\t",k);
for(j=1;j=L;j++)
{
printf("%5d",R[j].key);
}
getchar();
printf("\n");
}
}
void Heap()
{
int i;
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t");
for(i=1;i=L;i++)
{
printf("%5d",R[i].key);
}
getchar();
printf("\n");
Heapsort();
printf("\n\t\t排序最终结果是：\n\t\t");
for(i=1;i=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
main()
{
Seqlist S;
int i,k;
char ch1,ch2,q;
printf("\n\t\t请输入%d个待排序的数据（按回车键分隔）：\n\t\t",L);
for(i=1;i=L;i++)
{
scanf("%d",S[i].key);
getchar();
printf("\t\t");
}
printf("\n\t\t数据输入完毕！");
ch1='y';
while(ch1=='y'||ch1=='Y')
{
printf("\n");
printf("\n\t\t 排 序 子 系 统 \n");
printf("\n\t\t*******************************************\n");
printf("\n\t\t* 1--------更新排序数据 *\n");
printf("\n\t\t* 2--------直接插入排序 *\n");
printf("\n\t\t* 3--------希 尔 排 序 *\n");
printf("\n\t\t* 4--------冒 泡 排 序 *\n");
printf("\n\t\t* 5--------快 速 排 序 *\n");
printf("\n\t\t* 6--------选 择 排 序 *\n");
printf("\n\t\t* 7--------归 并 排 序 *\n");
printf("\n\t\t* 8--------堆 排 序 *\n");
printf("\n\t\t* 0--------退 出 *\n");
printf("\n\t\t*******************************************\n");
printf("\n\t\t请选择菜单号（0到8）");
scanf("%c",ch2);
getchar();
for(i=1;i=L;i++)
{
R[i].key=S[i].key;
}
switch(ch2)
{
case '1':
printf("\n\t\t请输入%d个待排序数据（按回车键分隔）\n\t\t",L);
for(i=1;i=L;i++)
{
scanf("%d",S[i].key);
getchar();
printf("\t\t");
}
printf("\n\t\t数据输入完毕！");
break;
case '2':
Insertsort();
break;
case '3':
Shellsort();
break;
case '4':
Bubblesort();
break;
case '5':
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t");
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
num=0;
Quicksort(1,L);
printf("\n\t\t排序最终结果是：\n\t\t");
for(k=1;k=L;k++)
{
printf("%5d",R[k].key);
}
printf("\n");
break;
case '6':
Selectsort();
break;
case '7':
Mergesort();
break;
case '8':
Heap();
break;
case '0':
ch1='n';
break;
default:
system("cls");
printf("\n\t\t对不起，您输入有误，请重新输入！\n");
break;
}
if(ch2!='0')
{
if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')
{
printf("\n\n\t\t排序完毕！");
printf("\n\t\t按回车键继续！");
q=getchar();
if(q!='\xA')
{
getchar();
ch1='n';
}
}
}
}
}
哥们，这是严蔚敏的数据结构书上的堆排序算法，代码如下，试一下吧
堆排序heapsort（第26行至37行）首先调用建堆函数buildheap，将n个待排序记录建立一个初始堆，然后重复执行n-1次元素交换（第32行至34行）和siftdown进行堆排序。init和print函数与图8.1相同。为节约篇幅，只给出其函数原型，略去其实现。
1 #include stdlib.h
2 #define N 8
3 int a[N];
4 void init()
5 void print()
6 int siftdown(int i,int n)
7 {
8 int t;
9 int j = 2*i + 1;
10 while (j n) {
11 if ((j (n-1)) (a[j] a[j+1])) j++;
12 if (a[i] = a[j]) return 0;
13 t = a[i];
14 a[i] = a[j];
15 a[j] = t;
16 i = j;
17 j = 2*i + 1;
18 }
19 }
20 void buildheap(int n)
21 {
22 int i;
23 for (i = n/2-1;i = 0;i--)
24 siftdown(i,n);
25 }
26 void heapsort(int n)
27 {
28 int i,t,j;
29 buildheap(n);
30 for (i = 0;i n;i++) {
31 print(N);
32 t = a[0];
33 a[0] = a[n-i-1];
34 a[n-i-1] = t;
35 siftdown(0,n-i-1);
36 }
37 }
38 void main()
39 {
40 init(N);
41 print(N);
42 heapsort(N);
43 print(N);
44 }
#include stdio.h
#include stdlib.h
#include string.h
int sort_function( const void *a, const void *b);
char list[5][4] = { "cat", "car", "cab", "cap", "can" };
int main(void)
{
int x;
qsort((void *)list, 5, sizeof(list[0]), sort_function); // 调用快速排序
for (x = 0; x 5; x++)
printf("%s\n", list[x]);
return 0;
}
int sort_function( const void *a, const void *b)
{ //自已要定义一个简单的比较函数就可
return( strcmp((char *)a,(char *)b) );
}
// C++中自身有一个通用的快速 qsort,可以用它 ,自已要定义一个简单的比较函数就可
Copyright © 2009-2022 www.kswsj.com 成都快上网科技有限公司 版权所有 蜀ICP备19037934号
在线咨询
在线咨询
