c排序算法

‘壹’ C语言，快速排序算法

0和N-1表示的是数组下标。快排每一趟排序的目的是使值比设定的key值小的数都排到数组前部分，大的都排到后部分；然后对这两部分用新的关键值key分别重复上一步的操作；递归，直到数组有序。
其中关键值key=a[low]。
用题目给定的数组模拟第一趟排序如下：
下标0123456789
值91647824661232551
low=0high=9
part_element=a[low]=9
进入for循环
进入第一个while
part_element<51，于是high--,high=8;
part_element<25，high--,high=7;
part_element>3,不满足，结束while
a[low]=a[0]=a[high]=a[7]=3,low++,low=1;
进入第二个while
part_element<16,不满足，结束while
a[high]=a[7]=a[low]=a[1]=16,high--,high=6
for第一个循环结束，数组如下
316478246612162551
low=1,high=6
for第二个循环同上，结束时数组如下
344782476612162551
low=2,high=3
for第三个循环，第一个while中high--以后，low==high，直接break跳出for循环，此时
344782476612162551
low=2,high=2
结束for以后
a[high]=a[2]=part_element=9,得到
34982476612162551
split函数returnhigh=2

quicksort函数中middle=2;
下面两句递归，仍然是调用split函数，对数组
0-2,3-9两部分分别重复上述操作

最后直到数组数据有序

‘贰’ C语言 排序算法综合系统

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<iostream>
using namespace std;
void find(int *a,int n);
void input(int pIn[], int n);
void del(int *a,int n);
void Swap(int *a, int *b);
int Partition(int a[], int p, int r);
void arrange(int *c,int length);
template <class Type>
/* 为了便于维护，现在把排序封装在类ArraySort内
*/
class ArraySort
{
private: int elem; //elem的值决定按升序还是降序
int len; //排序数组的长度
Type *b; //排序时用与交换的数组
Type *a; //用来存放要排序的数组；
public:
void set(Type c[],int k); //接收要排序的数组及数组长度
void Sort(); //进行排序
void MergeSort(int ,int );
void Merge(int ,int ,int); //进行合并
void Copy(int ,int); //复制一个数组到另一个数组
void ArPrint(); //输出数组元素
void ReturnCopy(Type c[]); //把已经排序数组返回给原数组
~ArraySort();
ArraySort(int k=0){
elem=k;
len=0;
a=NULL;
b=NULL;
}
};
template<class Type>
void ArraySort<Type>::set(Type c[],int k )
{ int m;
len=k;
//len=c.length;
a=new Type[len];
b=new Type[len];
if((a==NULL)||(b==NULL))
{ cout<<"can't allocate more memory,terminating."<<endl;
exit(1);
}
else{
for(int i=0;i<len;i++)
a[i]=c[i];
}
cout<<" input the number 0 or 1:"<<endl;
cout<<"0 min to max:"<<endl;
cout<<"1 max to min"<<endl;
cin>>m;
if(m>=0&&m<=1)
elem=m;
else {
cout<<"You input a illegal number!!";
cout<<" input the number 0 or 1:"<<endl;
cout<<"0 min to max:"<<endl;
cout<<"1 max to min"<<endl;
}
}
template <class Type>
void ArraySort<Type>::Sort()
{
MergeSort(0,len-1);
}
template <class Type>
void ArraySort<Type>::Merge(int left,int m,int right)
{
int i=left,
j=m+1,
k=left;
if(elem==0){
while((i<=m)&&(j<=right))
if(a[i]<=a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
}
else{
while((i<=m)&&(j<=right))
if(a[i]>=a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=m)
b[k++]=a[i++];
while(j<=right)
b[k++]=a[j++];
}
template <class Type>
void ArraySort<Type>::Copy(int left,int right)
{
for(int i=left;i<=right;i++)
a[i]=b[i];
}
template <class Type>
void ArraySort<Type>::ArPrint()
{
// int len=this.a.length;
cout<<"The length of array is :"<<len<<endl;
cout<<"The elements of array is :"<<endl;
for(int i=0;i<len;i++)
cout<<" "<<a[i];
if(i/5==0)
cout<<endl;
}
template <class Type>
void ArraySort<Type>::MergeSort(int left,int right)
{
if(left<right){
int i=(left+right)/2;
MergeSort(left,i);
MergeSort(i+1,right);
Merge(left,i,right);
Copy(left,right);
}
}
template <class Type>
void ArraySort<Type>::ReturnCopy(Type c[])
{
for(int i=0;i<len;i++)
c[i]=a[i];
}
template <class Type>
ArraySort<Type>::~ArraySort()
{
delete a;
delete b;
}

void qSort(int pIn[], int p/*0*/, int r/*r = N - 1*/);
main()
{ char c;
int i,a[12]={6,11,12,5,1,13,8,9,14,7,10},exit=1;
do
{
system("cls");
for(i=0;i<80;i++)
printf("*");
printf("\t 1:选择排序法\n");
printf("\t 2:冒泡排序法\n");
printf("\t 3:插入排序法\n");
printf("\t 4:合并排序法\n");
printf("\t 5:退出\n");
printf("\t 请选择输入选项【1\\2\\3\\4\\5】:\n");
do
{
c=getch();
}while(c!='1'&&c!='2'&&c!='3'&&c!='4'&&c!='5');

switch(c)
{ case '1':input(a,11);
cout<<endl;
for(i=0;i<11;i++)
cout<<a[i]<<" ";
cout<<endl;
break;
case '2':del(a,11);
cout<<endl;
for(i=0;i<11;i++)
cout<<a[i]<<" ";
cout<<endl;break;
case '3':find(a,11); break;
case '4':arrange(a,11); break;
case '5':exit=0;
}
printf("按任意键返回主菜单:\n");
getche();

}while(exit);
}
void input(int pIn[], int n)
{
qSort(pIn, 0, n-1);
}
void Swap(int *a, int *b){
int c = *a;
*a = *b;
*b = c;
}

int Partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];

while(1){
while (i <= r && a[++i] < x); // 如果你要从大到小排序就改x前的<为>
while (j >= p && a[--j] > x); //同时这的>也要改为<
if (i >= j) break;
Swap(&a[i], &a[j]);
}

if (i == j) {
j --;
}

a[p] = a[j];
a[j] = x;
return j;
}

void qSort(int pIn[], int p/*0*/, int r/*r = N - 1*/)
{
if (p < r) {
int q = Partition(pIn, p, r);
qSort(pIn, p, q - 1);
qSort(pIn, q + 1, r);
}
}
void del(int *a,int n)//冒泡
{
int i,j,k;
for(i=0;i<=n-2;i++)
for(j=0;j<=n-2-i;j++)
if(a[j]>a[j+1])//如果你要从大到小排序就改>为<
{
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
}

void find(int *a,int n)//插入
{
int i, j, x;
for(i = 1;i < n;i++)
{
x = a[i];
j = i - 1;

while(j >= 0 && a[j] > x){
a[j+1] = a[j];
j--;
}

a[j+1] = x;
}
for(i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void arrange(int *c,int length)//组合
{
int i;

ArraySort<int > as;
as.set(c,length);
cout<<"排序前的数组元素序列："<<endl;
for( i=0;i<length;i++)
cout<<" "<<c[i];
cout<<endl;
as.Sort();

as.ReturnCopy(c);

cout<<"排序后的数组元素序列："<<endl;
for( i=0;i<length;i++)
cout<<" "<<c[i];
cout<<endl;
}
楼主做了我2个多小时啊。。TC不能识别有的头文件哈，我已经用VC6.0测试过了

‘叁’ C语言，排序算法

对数组中的10个元数前几个进行排序，安从小到大的顺序。设n=5
如：10个元数是1，9，8，7，5
i=1时。temp=v[1]=9；j=0 v[j]=v[0]=1；不符合循环条件，不做；
i=2时。temp=v[2]=8；j=1 v[j]=v[1]=9；符合循环条件，做循环体；
v[1]=8；v[2]=9；这时数组为1，8，9，7，5
i=3时。temp=v[3]=7，j=2 v[j]=v[2]=9；符号循环条件。做循环体
v[1]=7,v[2]=8,v[3]=9。数组为1，7，8，9，5。
i=4时。做法是一样的
最后结果为1，5，7，8，9
不知道对不对，我是这么认为的

‘肆’ C语言排序算法一共多少种

1. 选择排序
   

#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;
}

排序方法基本就这些，还有双向冒泡这种拓展的排序方法，还有直接排序如桶排序

‘伍’ c/c++排序算法的比较

快速排序是最快的，我曾经试过的，记得好像是o(n)。
另外两个在网络文库里找找吧，以前看过的，算法分析和代码都有

‘陆’ C程序设计题--排序算法比较

只能帮你这么多了````你修改下就可以用了
/*
Note:Your
choice
is
C
IDE
*/
#include
"stdio.h"
#include<stdlib.h>
typedef
struct
bitnode
{
int
data;
struct
bitnode
*lchild,*rchild;
}bitnode,*bittree;
bittree
cre_tree()
{
int
x;
bittree
root;
scanf("%d",&x);
if(x==-1)root=NULL;
else
{
root=(bittree)malloc(sizeof(bitnode));
root->data=x;
root->lchild=cre_tree();
root->rchild=cre_tree();
}
return
root;
}
void
preorder(bittree
root)
{
if(root)
{
printf("%d",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}
void
inorder(bittree
root)
{
if(root)
{
inorder(root->lchild);
printf("%d",root->data);
inorder(root->rchild);
}
}
void
postorder(bittree
root)
{
if(root)
{
postorder(root->lchild);
postorder(root->rchild);
printf("%d",root->data);
}
}
bittree
exchang(bittree
root)
{
bittree
t;
if(root)
{
if(root->lchild!=NULL&&root->rchild!=NULL)
{
t=root->lchild;
root->lchild=root->rchild;
root->rchild=t;
}
root->lchild=exchang(root->lchild);
root->rchild=exchang(root->rchild);
}
return
root;
}
int
hightree(bittree
root)
{
int
H,H1,H2;
if(root==NULL)H=0;
else
{
H1=hightree(root->lchild);
H2=hightree(root->rchild);
H=(H1>H2?H1:H2)+1;
}
return
H;
}
int
fine=0;
void
searchtree(bittree
root,int
x,bittree
*p)
{
if(root&&!fine)
if(root->data==x)
{
fine=1;*p=root;
}
//若找到,则通过p带回该结点的指针
else
{
*p=NULL;
searchtree(root->lchild,x,p);
searchtree(root->rchild,x,p);
}
}
int
n=0;
void
leafcount(bittree
root)
{
if(root)
{
if(root->lchild==NULL&&root->rchild==NULL)
n++;
leafcount(root->lchild);
leafcount(root->rchild);
}
}
void
main()
{
int
H,x;
bittree
root,p;
root=cre_tree();
preorder(root);printf("\n\n");
inorder(root);printf("\n\n");
postorder(root);printf("\n\n");
root=exchang(root);preorder(root);printf("\n\n");
H=hightree(root);
printf("二叉树的深度为:");printf("%d\n",H);
scanf("%d",&x);searchtree(root,x,&p);
printf("要找的数据为:");
printf("%d",p->data);printf("\n");
leafcount(root);
printf("叶子的结点个数为:");printf("%d",n);
}
--------------------------------------------------------------------------
/*
Note:Your
choice
is
C
IDE
*/
#include
"stdio.h"
#include<stdlib.h>
typedef
struct
bitnode
{
char
ch;
struct
bitnode
*lchild,*rchild;
}bitnode,*bittree;
typedef
struct
stacknode
{
bitnode
*data;
struct
stacknode
*next;
}linkstack;
void
initstack(linkstack
*s)
{
s->next=NULL;
}
void
push(linkstack
*s,bittree
x)
{
linkstack
*p;
p=(linkstack
*)malloc(sizeof(linkstack));
p->data=x;
p->next=s->next;
s->next=p;
}
bittree
pop(linkstack
*s)
{
bittree
x;
linkstack
*p;
p=s->next;
if(s->next==0)return
0;
x=p->data;
s->next=p->next;
free(p);
return
x;
}
bittree
cre_tree()
{
bittree
root;
char
ch;
ch=getchar();
if(ch=='#')root=NULL;
else
{
root=(bittree)malloc(sizeof(bitnode));
root->ch=ch;
root->lchild=cre_tree();
root->rchild=cre_tree();
}
return
root;
}
void
preorder(bittree
root)
{
linkstack
s;
bittree
p;
initstack(&s);
push(&s,root);
while(s.next)
{
p=pop(&s);
while(p)
{
printf("%c",p->ch);
if(p->rchild)push(&s,p->rchild);
p=p->lchild;
}
}
}
void
inorder(bittree
root)
{
bittree
p;
linkstack
s;
initstack(&s);
p=root;
while(p||s.next)
//注意还有右子树也要判断
{
while(p)
{
push(&s,p);
p=p->lchild;
}
p=pop(&s);
printf("%c",p->ch);
p=p->rchild;
}
}
void
main()
{
bittree
root;
root=cre_tree();
preorder(root);printf("\n\n");
inorder(root);printf("\n\n");
}

‘柒’ c语言排序算法

#include<stdio.h>
#defineN100000//定义最多输入的数据
intsort(int*a,intn){
	inti,j,m;
	for(i=0;i<n-1;i++)
	for(j=i+1;j<n;j++)
		if(a[i]>a[j]){
			m=a[i];a[i]=a[j];a[j]=m;
		}
	return0;
}
intmain(){
	inta[N];
	inti=0,n,ii;
	while(1){
		//printf("输入n
");
		scanf("%d",&n);
		a[i++]=n;
		if(n==0)break;
		ii=i;
		for(;i<n+ii;i++)
			scanf("%d",&a[i]);
	}
	i=0;
	while(a[i]!=0){
		sort(a+i+1,a[i]);
		for(n=1;n<=a[i];n++)
			printf("%d",a[i+n]);
		printf("
");
		i=i+a[i]+1;
	}
}

‘捌’ 一个C语言排序算法问题

这个还是属于冒泡吧·
你可能是没把程序看清楚。
下面给你把这个程序一步一步操作一片，你就知道了。

b[0]=5,b[1]=6,b[2]=3,b[3]=2,b[4]=1
i=0
j=1
if(b[i]>b[j]) //if(b[0]>b[1])
显然false;
然后j++
if(b[i]>b[j]) //if(b[0]>b[2]) 注意它的i的值是不变的。
true;
数组就变成
b[0]=3,b[1]=6,b[2]=5b[3]=2,b[4]=1
然后j++
if(b[i]>b[j]) //if(b[0]>b[3]) 注意它的i的值是不变的。
true;
数组就变成
b[0]=2,b[1]=6,b[2]=5b[3]=3,b[4]=1
·····
在i++前数组变成
1，6，5，3，2
这就相当于把最小的移到最前面了。以此类推，i++后对1后面得数进行移动。
-----------------------------------
楼主要是还不懂的话，可以来问我。

‘玖’ c语言 比较法排序区别

1、稳定排序和非稳定排序的不同

简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。

比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。

2、内排序和外排序的不同

在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；

在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

3、算法的时间复杂度和空间复杂度不同

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

‘拾’ 数据结构排序算法（C描述）

看看可以不#include<stdio.h>#include<stdlib.h> #define TRUE 1#define FALSE 0#define OK 1#define ERROR#define OVERFLOW -2#define MAXSIZE 20 //一个用作示例的小顺序表的最大长度#define LT(a,b) ((a)<(b))#define LQ(a,b) ((a)<=(b)) 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 InitList_Sq(SqList &L){//构造一个空的顺序表L。 int i; printf("请输入待排序的记录的个数："); scanf("%d",&L.length); printf("请输入待排序的记录的关键字（整型数）："); for(i=1;i<=L.length;i++) scanf("%d",&L.r[i]); return OK;} void Print_Sq(SqList &L) //输出{ int i; for(i=1;i<=L.length;i++) { printf("%4d",L.r[i]); } printf("\n");} //------------插入排序---void InsertSort(SqList &L){//对顺序表L作直接插入排序。 int i,j; for(i=2;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-1].key))//“<”，需将L.r[i]插入有序子表 { L.r[0]=L.r[i];//复制为哨兵 L.r[i]=L.r[i-1]; for(j=i-2;LT(L.r[0].key,L.r[j].key);--j) L.r[j+1]=L.r[j];//记录后移 L.r[j+1]=L.r[0];//插入到正确位置 }}//--------------冒泡排序---void BubbleSort(SqList &L){//L.r是待排序的文件，采用自下向上扫描，对L.r做冒泡排序 int i,j; int exchange; // 交换标志 for(i=1;i<L.length;i++) {// 最多做 n-1 趟排序 exchange=FALSE; // 本趟排序开始前，交换标志应为假 for(j=L.length-1;j>=i;j--) // 对当前无序区 R[i..n] 自下向上扫描 if(LT(L.r[j+1].key,L.r[j].key)) { // 交换记录 L.r[0]=L.r[j+1]; //L.r[0]不是哨兵，仅做暂存单元 L.r[j+1]=L.r[j]; L.r[j]=L.r[0]; exchange=TRUE; // 发生了交换，故将交换标志置为真 } if(!exchange) // 本趟排序未发生交换，提前终止算法 return; } }//-----------快速排序---int Partition(SqList &L,int low,int high){//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时 //在它之前（后）的记录均不大（小）于它。 KeyType pivotkey; L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录 pivotkey=L.r[low].key;//枢轴记录关键字 while(low<high) {//从表的两端交替地向中间扫描 while (low<high&&L.r[high].key>=pivotkey) --high; L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端 while (low<high&&L.r[low].key<=pivotkey) ++low; L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端 } L.r[low]=L.r[0];//枢轴记录到位 return low;//返回枢轴位置} void QSort(SqList &L,int low,int high){//对顺序表L中的子序列L.r[low..high]进行快速排序 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作快速排序。 QSort(L,1,L.length);}//----------归并排序---void Merge(RedType SR[],RedType TR[],int i,int m,int n){//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] int j,k; 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)//TR[k..n]=SR[i..m];将剩余的SR[i..m]复制到TR while(k<=n&&i<=m) TR[k++]=SR[i++]; if(j<=n)//将剩余的SR[j..n]复制到TR while(k<=n&&j<=n) TR[k++]=SR[j++];} void MSort(RedType SR[],RedType TR1[],int s,int t){//将SR[s..t]归并排序为TR1[s..t]。 int m; RedType TR2[20]; if(s==t) TR1[t] = 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作归并排序。 MSort(L.r, L.r, 1, L.length);}//-----------堆排序---void HeapAdjust(SqList &H,int s,int m){//已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义， //本函数调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆 //（对其中记录的关键字而言） int j; RedType rc; 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(rc.key>=H.r[j].key) break;//rc应插入在位置s上 H.r[s]=H.r[j]; s=j; } H.r[s]=rc;//插入} void HeapSort(SqList &H){//对顺序表H进行堆排序。 int i; RedType temp; 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) { temp=H.r[i]; H.r[i]=H.r[1]; H.r[1]=temp;//将堆顶记录和当前未经排序子序列Hr[1..i]中 //最后一个记录相互交换 HeapAdjust(H,1,i-1);//将H.r[1..i-1]重新调整为大顶堆 }} void main(){ SqList S; printf("---------- 五种排序算法 ----------\n"); InitList_Sq(S); printf(" 1.简单插入排序\n"); InsertSort(S); Print_Sq(S); printf(" 2.冒泡排序\n"); BubbleSort(S); Print_Sq(S); printf(" 3.快速排序\n"); QuickSort(S); Print_Sq(S); printf(" 4.归并排序\n"); MergeSort(S); Print_Sq(S); printf(" 5.堆排序\n"); HeapSort(S); Print_Sq(S);}