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