大话数据结构 之排序算法

目录

• 1、冒泡法排序（从前往后循环，将所有值与第一个值作比较，使得第一个值能获得最小值）
• 2、冒泡法排序升级版（从后往前排序，将最小值放置最前面）
• 3、堆排序
• 4、快速排序
• 5、快速排序优化
• 6、插入排序
• 7、希尔排序
• 整体排序算法

1、冒泡法排序（从前往后循环，将所有值与第一个值作比较，使得第一个值能获得最小值）

基本思想：(初级版)
冒泡排序是一种交换排序，基本思想是两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录位置。
算法描述：

1、for i =1 to L->length
2、
for j = i+1 to L->length
3、
if 将所有值与第i个值比较
4、
如果比第i个值小，则将其与第i个值交换，即swap(L, i, j)

代码实现

#include <stdio.h>
//#define MAXSIZE 10000
/* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct
{
int r[10001];
/* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
int length;
/* 用于记录顺序表的长度 */
}SqList;
/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}
/* 对顺序表L作交换排序（冒泡排序初级版） */
void BubbleSort0(SqList *L)
{
int i,j;
for(i=1;i<L->length;i++)
{
/* 第一次循环是将最大值放在了最后面 */
for(j=i+1;j<=L->length;j++)/* 从前往后循环 */
{
if(L->r[i]>L->r[j])/* 如果前者大于后者 */
{
swap(L,i,j);/* 交换L->r[i]与L->r[j]的值 */
}
}
}
}
/* 打印顺序表 */
void print(SqList L)
{
int i;
for(i=1;i<L.length;i++)
printf("%d,",L.r[i]);
printf("%d",L.r[i]);
printf("n");
}
int main()
{
int d[9]={50,10,90,30,70,40,80,60,20};
SqList a;
//将需要排序的数组递给顺序表中的int型数组
int i;
for(i=0;i<9;i++)
a.r[i+1]=d[i];
a.length=9;
printf("排序前:n");
print(a);
printf("初级冒泡排序:n");
BubbleSort0(&a);
print(a);
return 0;
}

2、冒泡法排序升级版（从后往前排序，将最小值放置最前面）

基本思想：（正宗的冒泡排序）
冒泡排序是一种交换排序，基本思想是两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录位置。
算法描述：

1、for i = i to L->length
2、
for j = L->length-1 to 1
3、
if 第j个值比第j+1个值大
4、
如果打，则交换两者的值，即swap(L, j, j+1)

代码实现：

/* 对顺序表L作冒泡排序 */
void BubbleSort(SqList *L)
{
int i,j;
for(i=1;i<L->length;i++)
{
/* 第一次循环的是将最小值放在了最前面 */
for(j=L->length-1;j>=i;j--)
/* 注意j是从后往前循环 */
{
if(L->r[j]>L->r[j+1]) /* 若前者大于后者（注意这里与上一算法的差异）———— L-r[j+1]才是最后一个值 */
{
swap(L,j,j+1);/* 交换L->r[j]与L->r[j+1]的值 */
}
}
}
}

3、堆排序

堆是具有下列性质的完全二叉树：
（1）每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
（2）或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆；
因此可以将顺序表调整为大顶堆或者小顶堆；
堆排序就是利用堆进行排序的方法。
基本思想：
将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列。
算法描述：

1、首先进行堆调整，比如形成一个大顶堆；
2、for i=L->length/2
to 1
/* 之所以从`length/2 ~1`是因为1,2,3,4都是有孩子的节点，都可以是父节点*/
3、
进行堆调整，HeapAdjust(L, i, L->length)
4、for i=L->length to 2
5、
首先交换一下堆顶个堆尾，即swap(L, 1, i);
6、
然后进行堆调整，重新生成大顶堆，即HeapAdjust(L, 1, i-1)
7、大顶堆算法为：void HeapAdjust(Sqlist *L, int s, int m)
8、首先将父节点赋给一个temp，即`temp=L->r[s]
9、for
j=2*s to m
(以j = j*2的方式找出每个父节点对应的两个子节点)
10、
找到该父节点下的两个子节点中较大值的下标
11、
if
该下标对应子节点比父节点下，则退出循环
12、
否则，将该子节点的值与父节点的值进行交换

代码实现：

/* 堆排序********************************** */
/* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义， */
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */
void HeapAdjust(SqList *L,int s,int m)
{
int temp,j;
temp=L->r[s];
for(j=2*s;j<=m;j*=2) /* 沿关键字较大的孩子结点向下筛选 */
{
if(j<m && L->r[j]<L->r[j+1])
++j; /* j为关键字中较大的记录的下标 */
if(temp>=L->r[j])
break; /* rc应插入在位置s上 */
L->r[s]=L->r[j];
s=j;
}
L->r[s]=temp; /* 插入 */
}
/*
对顺序表L进行堆排序 */
void HeapSort(SqList *L)
{
int i;
for(i=L->length/2;i>0;i--) /*
把L中的r构建成一个大根堆 */
HeapAdjust(L,i,L->length);
for(i=L->length;i>1;i--)
{
swap(L,1,i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
HeapAdjust(L,1,i-1); /*
将L->r[1..i-1]重新调整为大根堆 */
}
}
/* **************************************** */

4、快速排序

快速排序的基本思想：
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
枢轴：选择数组中的一个关键字，想尽办法将它放到一个位置，使得它左边的值比它小，右边的值比它大
算法描述：

1、对顺序表L中的子序列做一次划分，low=1，high=L->Length
2、if low<high
3、
（ 则做第一次划分，返回枢轴所在位置，将待排记录划分为两个部分，第3~11行是划分算法，与冒泡排序相似）
4、
用子表的第一个记录作枢轴记录；pivotkey = L-r[row]
5、
while
low<hign ( 做第一次划分，划分过程是从表的两端向中间扫描）
6、
if low<high 并且 数组/顺序表的最后一个值大于等于枢轴记录
7、
符合排序要求，仅仅将high的下标前移一位，即high--
8、
swap(L, low, high)，将比枢轴记录小的记录交换到低端（如果第high值小于枢轴，则交换正好可以将较大值放在后面）
9、
if low<high 并且 数组/顺序表的第一个值小于等于枢轴记录
10、
符合排序要求，仅仅将low的下标后移一位，即low++
11、
swap(L, low, high)，将比枢轴记录大的位置交换到高端（如果第low值比枢轴大，则放置高端）
12、
返回枢轴所在位置，即low下标（经过两边与枢轴记录的比较，low的下标已经发生改变）
13、
对低字表进行递归排序（即再做一次划分）
14、
对高子表进行递归排序（也再做一次划分）

代码实现：

/* 快速排序******************************** */
/* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
while(low<high) /*
从表的两端交替地向中间扫描 */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */
while(low<high&&L->r[low]<=pivotkey)
low++;
swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */
}
return low; /* 返回枢轴所在位置 */
}
/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high)
{
pivot=Partition(L,low,high); /*
将L->r[low..high]一分为二，算出枢轴值pivot */
QSort(L,low,pivot-1);
/*
对低子表递归排序 */
QSort(L,pivot+1,high);
/*
对高子表递归排序 */
}
}
/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}
/* **************************************** */

5、快速排序优化

基本思想：

算法描述：

代码实现：

/* 改进后快速排序******************************** */
/* 快速排序优化算法 */
int Partition1(SqList *L,int low,int high)
{
int pivotkey;
int m = low + (high - low) / 2; /* 计算数组中间的元素的下标 */
if (L->r[low]>L->r[high])
swap(L,low,high);
/* 交换左端与右端数据，保证左端较小 */
if (L->r[m]>L->r[high])
swap(L,high,m);
/* 交换中间与右端数据，保证中间较小 */
if (L->r[m]>L->r[low])
swap(L,m,low);
/* 交换中间与左端数据，保证左端较小 */
pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
L->r[0]=pivotkey;
/* 将枢轴关键字备份到L->r[0] */
while(low<high) /*
从表的两端交替地向中间扫描 */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
L->r[low]=L->r[high];
while(low<high&&L->r[low]<=pivotkey)
low++;
L->r[high]=L->r[low];
}
L->r[low]=L->r[0];
return low; /* 返回枢轴所在位置 */
}
void QSort1(SqList *L,int low,int high)
{
int pivot;
if((high-low)>7) /* 用于快速排序时判断是否选用插入排序阙值 */
{
while(low<high)
{
pivot=Partition1(L,low,high); /*
将L->r[low..high]一分为二，算出枢轴值pivot */
QSort1(L,low,pivot-1);
/*
对低子表递归排序 */
/* QSort(L,pivot+1,high);
/*
对高子表递归排序 */
low=pivot+1;
/* 尾递归 */
}
}
else
InsertSort(L);
}
/* 对顺序表L作快速排序 */
void QuickSort1(SqList *L)
{
QSort1(L,1,L->length);
}
/* **************************************** */

6、插入排序

直接插入排序的基本操作（基本思想）：
直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
算法描述：

1、for i=2 to L->length
2、
if 链表的第 i 个值小于第 i-1 个值
3、
将将i个值设置为哨兵
4、
for j=i-1 to 1
5、
将所有的值与哨兵进行比较，如果比哨兵大，则后移一位；
6、
将哨兵插入到正确位置（即比左侧大，比右侧大）

代码实现：

/* 对顺序表L作直接插入排序 */
void InsertSort(SqList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
{
if (L->r[i]<L->r[i-1]) /* 需将L->r[i]插入有序子表 */
{
L->r[0]=L->r[i]; /* 设置哨兵 */
for(j=i-1;L->r[j]>L->r[0];j--)
L->r[j+1]=L->r[j]; /* 记录后移 */
L->r[j+1]=L->r[0]; /* 插入到正确位置 */
}
}
}

7、希尔排序

（1）基本思想：
通过将大量记录分割成多个子序列，然后在这些子序列内分别进行直接插入排序，当整个序列基本有序时，再对全体记录进行一次直接插入排序。
其中，我们需要采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内进行直接插入排序后得到的结果是基本有序而不是局部有序。
（2）算法描述：

1、首先将分割增量设置为顺序表长度，即`increment = L->length`;
2、repeat
3、
将增量设置为`increment = increment/3 + 1`;
4、
repeat（做一个增量循环，从increment一直到链表长度做一个循环；假设循环变量为i，即{i | increment <= i <= L->length}）
5、
如果第 i 个值 小于 第 i - increment个值，则做一个直接增量插入排序；（直接增量插入排序不是相邻位置插入，而是以增量increment进行插入）
6、
until i > L->length
7、until 增量increment等于1（或者小于1，实际上必须让增量等于1

（3）代码实现：

/* 对顺序表L作希尔排序 */
void ShellSort(SqList *L)
{
int i,j,k=0;
int increment=L->length;
do
{
increment=increment/3+1;/* 增量序列 */
for(i=increment+1;i<=L->length;i++)
{
if (L->r[i]<L->r[i-increment])/*
需将L->r[i]插入有序增量子表 */
{
L->r[0]=L->r[i]; /*
暂存在L->r[0] */
for(j=i-increment;j>0 && L->r[0]<L->r[j];j-=increment)
L->r[j+increment]=L->r[j]; /*
记录后移，查找插入位置 */
L->r[j+increment]=L->r[0]; /*
插入 */
}
}
printf("
第%d趟排序结果: ",++k);
print(*L);
}
while(increment>1);
}

整体排序算法

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <io.h>
#include <math.h>
#include <time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAX_LENGTH_INSERT_SORT 7 /* 用于快速排序时判断是否选用插入排序阙值 */
typedef int Status;
#define MAXSIZE 10000
/* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct
{
int r[MAXSIZE+1];
/* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
int length;
/* 用于记录顺序表的长度 */
}SqList;
/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}
void print(SqList L)
{
int i;
for(i=1;i<L.length;i++)
printf("%d,",L.r[i]);
printf("%d",L.r[i]);
printf("n");
}
/* 对顺序表L作交换排序（冒泡排序初级版） */
void BubbleSort0(SqList *L)
{
int i,j;
for(i=1;i<L->length;i++)
{
for(j=i+1;j<=L->length;j++)
{
if(L->r[i]>L->r[j])
{
swap(L,i,j);/* 交换L->r[i]与L->r[j]的值 */
}
}
}
}
/* 对顺序表L作冒泡排序 */
void BubbleSort(SqList *L)
{
int i,j;
for(i=1;i<L->length;i++)
{
for(j=L->length-1;j>=i;j--)
/* 注意j是从后往前循环 */
{
if(L->r[j]>L->r[j+1]) /* 若前者大于后者（注意这里与上一算法的差异）*/
{
swap(L,j,j+1);/* 交换L->r[j]与L->r[j+1]的值 */
}
}
}
}
/* 对顺序表L作改进冒泡算法 */
void BubbleSort2(SqList *L)
{
int i,j;
Status flag=TRUE;
/* flag用来作为标记 */
for(i=1;i<L->length && flag;i++) /* 若flag为true说明有过数据交换，否则停止循环 */
{
flag=FALSE;
/* 初始为False */
for(j=L->length-1;j>=i;j--)
{
if(L->r[j]>L->r[j+1])
{
swap(L,j,j+1);
/* 交换L->r[j]与L->r[j+1]的值 */
flag=TRUE;
/* 如果有数据交换，则flag为true */
}
}
}
}
/* 对顺序表L作简单选择排序 */
void SelectSort(SqList *L)
{
int i,j,min;
for(i=1;i<L->length;i++)
{
min = i;
/* 将当前下标定义为最小值下标 */
for (j = i+1;j<=L->length;j++)/* 循环之后的数据 */
{
if (L->r[min]>L->r[j])
/* 如果有小于当前最小值的关键字 */
min = j;
/* 将此关键字的下标赋值给min */
}
if(i!=min)
/* 若min不等于i，说明找到最小值，交换 */
swap(L,i,min);
/* 交换L->r[i]与L->r[min]的值 */
}
}
/* 对顺序表L作直接插入排序 */
void InsertSort(SqList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
{
if (L->r[i]<L->r[i-1]) /* 需将L->r[i]插入有序子表 */
{
L->r[0]=L->r[i]; /* 设置哨兵 */
for(j=i-1;L->r[j]>L->r[0];j--)
L->r[j+1]=L->r[j]; /* 记录后移 */
L->r[j+1]=L->r[0]; /* 插入到正确位置 */
}
}
}
/* 对顺序表L作希尔排序 */
void ShellSort(SqList *L)
{
int i,j,k=0;
int increment=L->length;
do
{
increment=increment/3+1;/* 增量序列 */
for(i=increment+1;i<=L->length;i++)
{
if (L->r[i]<L->r[i-increment])/*
需将L->r[i]插入有序增量子表 */
{
L->r[0]=L->r[i]; /*
暂存在L->r[0] */
for(j=i-increment;j>0 && L->r[0]<L->r[j];j-=increment)
L->r[j+increment]=L->r[j]; /*
记录后移，查找插入位置 */
L->r[j+increment]=L->r[0]; /*
插入 */
}
}
printf("
第%d趟排序结果: ",++k);
print(*L);
}
while(increment>1);
}
/* 堆排序********************************** */
/* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义， */
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */
void HeapAdjust(SqList *L,int s,int m)
{
int temp,j;
temp=L->r[s];
for(j=2*s;j<=m;j*=2) /* 沿关键字较大的孩子结点向下筛选 */
{
if(j<m && L->r[j]<L->r[j+1])
++j; /* j为关键字中较大的记录的下标 */
if(temp>=L->r[j])
break; /* rc应插入在位置s上 */
L->r[s]=L->r[j];
s=j;
}
L->r[s]=temp; /* 插入 */
}
/*
对顺序表L进行堆排序 */
void HeapSort(SqList *L)
{
int i;
for(i=L->length/2;i>0;i--) /*
把L中的r构建成一个大根堆 */
HeapAdjust(L,i,L->length);
for(i=L->length;i>1;i--)
{
swap(L,1,i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
HeapAdjust(L,1,i-1); /*
将L->r[1..i-1]重新调整为大根堆 */
}
}
/* **************************************** */
/* 归并排序********************************** */
/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[],int TR[],int i,int m,int n)
{
int j,k,l;
for(j=m+1,k=i;i<=m && j<=n;k++)
/* 将SR中记录由小到大地并入TR */
{
if (SR[i]<SR[j])
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 */
}
}
/* 递归法 */
/* 将SR[s..t]归并排序为TR1[s..t] */
void MSort(int SR[],int TR1[],int s, int t)
{
int m;
int 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] */
}
}
/* 对顺序表L作归并排序 */
void MergeSort(SqList *L)
{
MSort(L->r,L->r,1,L->length);
}
/* 非递归法 */
/* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
void MergePass(int SR[],int TR[],int s,int n)
{
int i=1;
int j;
while(i <= n-2*s+1)
{/* 两两归并 */
Merge(SR,TR,i,i+s-1,i+2*s-1);
i=i+2*s;
}
if(i<n-s+1) /* 归并最后两个序列 */
Merge(SR,TR,i,i+s-1,n);
else /* 若最后只剩下单个子序列 */
for(j =i;j <= n;j++)
TR[j] = SR[j];
}
/* 对顺序表L作归并非递归排序 */
void MergeSort2(SqList *L)
{
int* TR=(int*)malloc(L->length * sizeof(int));/* 申请额外空间 */
int k=1;
while(k<L->length)
{
MergePass(L->r,TR,k,L->length);
k=2*k;/* 子序列长度加倍 */
MergePass(TR,L->r,k,L->length);
k=2*k;/* 子序列长度加倍 */
}
}
/* **************************************** */
/* 快速排序******************************** */
/* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
while(low<high) /*
从表的两端交替地向中间扫描 */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */
while(low<high&&L->r[low]<=pivotkey)
low++;
swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */
}
return low; /* 返回枢轴所在位置 */
}
/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high)
{
pivot=Partition(L,low,high); /*
将L->r[low..high]一分为二，算出枢轴值pivot */
QSort(L,low,pivot-1);
/*
对低子表递归排序 */
QSort(L,pivot+1,high);
/*
对高子表递归排序 */
}
}
/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}
/* **************************************** */
/* 改进后快速排序******************************** */
/* 快速排序优化算法 */
int Partition1(SqList *L,int low,int high)
{
int pivotkey;
int m = low + (high - low) / 2; /* 计算数组中间的元素的下标 */
if (L->r[low]>L->r[high])
swap(L,low,high);
/* 交换左端与右端数据，保证左端较小 */
if (L->r[m]>L->r[high])
swap(L,high,m);
/* 交换中间与右端数据，保证中间较小 */
if (L->r[m]>L->r[low])
swap(L,m,low);
/* 交换中间与左端数据，保证左端较小 */
pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
L->r[0]=pivotkey;
/* 将枢轴关键字备份到L->r[0] */
while(low<high) /*
从表的两端交替地向中间扫描 */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
L->r[low]=L->r[high];
while(low<high&&L->r[low]<=pivotkey)
low++;
L->r[high]=L->r[low];
}
L->r[low]=L->r[0];
return low; /* 返回枢轴所在位置 */
}
void QSort1(SqList *L,int low,int high)
{
int pivot;
if((high-low)>MAX_LENGTH_INSERT_SORT)
{
while(low<high)
{
pivot=Partition1(L,low,high); /*
将L->r[low..high]一分为二，算出枢轴值pivot */
QSort1(L,low,pivot-1);
/*
对低子表递归排序 */
/* QSort(L,pivot+1,high);
/*
对高子表递归排序 */
low=pivot+1;
/* 尾递归 */
}
}
else
InsertSort(L);
}
/* 对顺序表L作快速排序 */
void QuickSort1(SqList *L)
{
QSort1(L,1,L->length);
}
/* **************************************** */
#define N 9
int main()
{
int i;
/* int d[N]={9,1,5,8,3,7,4,6,2}; */
int d[N]={50,10,90,30,70,40,80,60,20};
/* int d[N]={9,8,7,6,5,4,3,2,1}; */
SqList l0,l1,l2,l3,l4,l5,l6,l7,l8,l9,l10;
for(i=0;i<N;i++)
l0.r[i+1]=d[i];
l0.length=N;
l1=l2=l3=l4=l5=l6=l7=l8=l9=l10=l0;
printf("排序前:n");
print(l0);
printf("初级冒泡排序:n");
clock_t start, finish;
double totaltime;
start = clock();
BubbleSort0(&l0);
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
printf("n运行的时间为：%en", totaltime);
print(l0);
//
system("pause");
printf("冒泡排序:n");
start = clock();
BubbleSort(&l1);
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
printf("n运行的时间为：%en", totaltime);
print(l1);
//
getchar();
printf("改进冒泡排序:n");
BubbleSort2(&l2);
print(l2);
printf("选择排序:n");
SelectSort(&l3);
print(l3);
printf("直接插入排序:n");
InsertSort(&l4);
print(l4);
printf("希尔排序:n");
ShellSort(&l5);
print(l5);
printf("堆排序:n");
HeapSort(&l6);
print(l6);
printf("归并排序（递归）:n");
MergeSort(&l7);
print(l7);
printf("归并排序（非递归）:n");
MergeSort2(&l8);
print(l8);
printf("快速排序:n");
QuickSort(&l9);
print(l9);
printf("改进快速排序:n");
QuickSort1(&l10);
print(l10);
/*大数据排序*/
/*
srand(time(0));
int Max=10000;
int d[10000];
int i;
SqList l0;
for(i=0;i<Max;i++)
d[i]=rand()%Max+1;
for(i=0;i<Max;i++)
l0.r[i+1]=d[i];
l0.length=Max;
MergeSort(l0);
print(l0);
*/
return 0;
}