035
排序算法设计样本
(样本只提供该系统的基本情况介绍,若需要完整的设计和论文,建议您购买本系统,凡是购买本站系统的,本站均根据您的要求,把系统上的开发信息,题目等修改成符合您的要求)
本设计包含内容：源代码+毕业论文
论文大概：
一、 各种排序方法的说明：
1．直接插入排序
是一种最简单的排序方法,将待排序的记录集分成两部分,第一部分已排好序,第二部分未排好序。排序中,每次都是从第二部分中取出一条记录,就将其插入到第一部分,并使其保持有序。初始时,任取一条记录作为第一部分（一条记录总是有序的）,而其他记录作为第二部分。显然,随着排序过程的进行,第一部分不断扩大,第二部分不断缩小。总有一次,第二部分变为空,则第一部分包含了所有的记录,并且是有序的。
插入排序的程序：
int SortInsertion(int a[], long n)
{//插入排序：
int x,
i,j;
for (i=1; i<n; i++)
{
x=a[i];
j=i-1;
while (j>=0 &&
x<a[j])
{
a[j+1] =a[j];
j--;
}
a[j+1]
=x;
} //for
return 0;
}
2．希尔排序又称为“缩小增量排序”是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序,待整个序列中的元素基本有序（增量足够小）时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况）,效率是很高的。算法是三层循环,最外层循环为log2n数量级,中间的for循环是n数量级的,内循环远远低于n数量级,因为当分组较多时,组内元素较少；此循环次数少；当分组较少时,组内元素增多,但已接近有序,循环次数并不增加。因此,希尔排序的时间复杂性在O（nlog2n）和O（n2
）之间,大致为O（n1.
3）。希尔排序对每个子序列单独比较,在比较时进行元素移动,有可能改变相同排序码元素的原始顺序,因此希尔排序是不稳定的。
void shellsort(int *A,int n)
{//希尔排序
int
x;
int
i,j,d;
for(d=n/2;d>=1;d/=2)
{//按不同分量进行排序
for(i=d;i<n;i++)
{//将A[i]元素直接插入到对应分组的有序表中
x=A[i];
for(j=i-d;j>=0;j-=d)
{//在组内向前顺序进行比较和移动
if(x<A[j])
A[j+d]=A[j];
else
break;//查找到合适位置就退出j循环
}
A[j+d]=x;
}
}
}
3．直接选择排序是一种很简单的排序方法,它的做法是：首先在所有的记录中选出键值最小的记录,把它与第一个记录交换；然后在其余的记录中再选出键值最小的记录与第二个记录交换；依此类推,直至所有记录排序完成。在第i趟中,通过n-i次键值比较选出所需记录。
直接选择排序的时间复杂度为O(n2)数量级,所以当记录占用的字节数较多时,通常比直接插入排序的执行速度要快一些。由于在直接选择排序中存在着不相邻元素之间的互换,因此,直接选择排序是一种不稳定的排序方法。
void
xz_sort(int e[],int n)//选择排序
{
int
i,j,k,t;
for(i=0;i<n-1;i++)//控制n-1遍的选择步骤
{
for(k=i,j=i+1;j<n;j++)
{
if(e[k]>e[j])
k=j;//记录最小元素的下标
}
if(k!=i)
t=e[i],e[i]=e[k],e[k]=t;//交换
}
}
4．冒泡排序:一个最简单的交换排序方法是冒泡排序法（bubble
sort）,它和气泡从水中往上冒的情况有些类似。其具体做法是：先第一个记录的键值和第二个记录的键值进行比较,如a[0]＞a[1],则将两个记录交换。然后比较第二个和第三个记录的关键字,依同样的方法处理；接着同法处理第三个和第四个记录,等等,直到第n-1个记录和第n个记录进行比较交换,这称为一趟冒泡。这一趟明显的效果是将键值最大的记录传到了最后。然后,对前n-1个记录进行同样操作,则具有第二大键值的记录被安置在第n-1个位置上。重复以上过程,每次的移动都向最终排序的目标前进,直至没有记录需要交换为止。
冒泡排序程序：
void BubbleSort(int *A,int n)
{//气泡法排序
int x;
int
i,j,flag;
for(i=1;i<=n-1;i++)
{//i表示次数,最多进行n-1次
flag=0;//设标志 0表示不用换
for(j=n-1;j>=i;j--)//进行第i次排序
if(A[j]<A[j-1])
{
x=A[j-1];A[j-1]=A[j];A[j]=x;
flag=1;
}
if(flag==0)return;//若无交换
返回
}
}
5．快速排序（quicksort）是交换排序的另一种,实际上它是冒泡排序的另一种改进。快速排序的基本思想是：在待排序的n个记录中任取一个记录（例如就取第一个记录）,以该记录的键值为标准,将所有记录分为两组（一般都是无序的）,使得第一组中各记录的键值均小于或等于该键值,第二组中各记录的键值均大于该键值。然后把该记录就排在这两组的中间（这也是该记录最终的位置）。此称为一趟分割,对所分成的两组再分别重复上述方法,直到所有记录都排在适当位置为止。
快速排序算法
void QuickSort(int *A,int s,int t)
{// 快速排序
//
s,t的初值为0,n-1
int i=s,j=t+1;//给i,j 负值
int x=A[s];
//把基准的值暂存于x中
do{
do
i++;while(A[i]<x);
//从前先后顺序查找一个向后一区间交换的元素
do
j--;while(A[j]>x);
//以后先前序查找一个需向前一区间交换元素
if(i<j)
{//当条件成立时交换A[i]和A[j]的值
int
temp=A[i];
A[i]=A[j];A[j]=temp;
}
}while(i<j);//条件成立时
继续
A[s]=A[j];A[j]=x;//交换A[s],A[j]的值
if(s<j-1)
QuickSort(A,s,j-1);//递归左
if(j+1<t)
QuickSort(A,j+1,t);//递归右
}
6．堆排序是：首先对n个记录的键值进行两两比较。然后在其中[n/2]个较小者之间再进行两两比较。如此重复,直至选出最小键值的记录为止。可用一棵树来表示这一排序过程。树中的n个叶子代表待排序记录的键值。叶子上面一层是叶子两两比较的结果。依此类推,树根表示最后选择出来最小的关键字。在选择出最小键值后,将其输出,然后,再在剩余的树结点中,按同样的方法选择最小者,这样,也是经过n-1选择,就将记录按升序输出了。但不同的是,以前的比较结果,通过树记录下来了,使得后面的选择可以在它们的基础上进行。如果专门设立树,则造成存储浪费。堆排序是一种巧妙的树形选择排序,它不需要专门设立树。
堆排序程序如下：
void Heapsort(int A[],int
n)
{//利用堆排序的方法对数组A中的n个元素进行排序
int x;
int
i,j;
for(i=n/2-1;i>=0;i--)
Sift(A,n,i);//建立初始堆
for(i=1;i<=n-1;i++)
{
//进行n-1此循环,完成对排序
x=A[0];A[0]=A[n-i];A[n-i]=x;//将树根结点的值同当前区间内的最后一个结点的值对换
Sift(A,n-i,0);//
筛A[0]结点,得到n-i个结点堆
}
}
堆排序适合于待排序的记录数较大的情况,对于n个记录进行排序所需的时间是O（nlog2n）。在最坏情况下,其时间复杂性也为O（nlog2n）.相对于快速排序来说,这是堆排序最大的优点。此外,堆排序仅需一个记录大小的供交换用的辅助存贮空间。易知堆排序是不稳定的。
7．二路归并排序是：利用二个有序序列的合并来实现归并排序。如果序列中有n个记录,可以先把它看成n个子序列,每个子序列中只包含一个记录,因而都是排好序的。二路归并排序先将每相邻的两个子序列合并,得到[n/2]个较大的有序子序列,每个子序列包含2个记录。再将这些子序列两两合并,得到[[n/2]/2]个有序子序列。如此反复,直到最后合并成一个有序序列,排序即告完成。
二路归并排序算法如下：
void
Merge(int *e,int n)
{
int *a=(int
*)malloc(sizeof(int)*n);
int
len=1,f=0;
while(len<n)//轮换保存
{
if(f==0)
merge_pass(e,a,n,len);
else
merge_pass(a,e,n,len);
len*=2;
f=1-f;
}
if(f)
for(f=0;f<n;f++)
e[f]=a[f];
free(a);
}