第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
数据结构综合课设排序算法时间.docx
排序算法时间
比较常用排序算法
[基本要求]
直接插入排序、希尔排序、直接选择排序、堆排序、起泡排序、快速排序。
（1）随机生成一组待排序数据，个数不少于 100 个；
（2）比较各种排序算法对同一组数据排序所需要的关键字比较次数和关键
字移动次数，至少使用 5 组数据进行比较；
（3）对比较结果进行简单分析。
[算法思想]
对于排序算法的比较采取关键字参加比较次数和关键字的移动次数还有利
用 time.h 中(int)GetTickCount()函数对 cpu 运用该排序算法所采用时间进行比
较。然后针对各种排序算法，写出函数，对算法进行实现。
例如 void ShellInsert（）//希尔排序（直接插入排序）
int Partition（）//快速排序
void HeapAdjust （）//堆排序
void BubbleSort（）//冒泡排序
int SelectMinKey（）//选择排序
增添了一个对所有算法进行一次实现的函数 void AllAbove（）
（1） 直接插入排序的思想：当插入第 i(i>=1)个元素时，前面的
L->r[0].key,…, L->r[i-1].key 等 i-1 个 元素已经有序。这时，将第 i 个元
素与前 i-1 个元素 V[i-1]，…，V[0]依次比较，找到插入位置即将 L->r[i].key
插入，同时原来位置上的元素向后顺移。在这里，插入位置的查找是顺序查找。
直接插入排序是一种稳定的排序算法
（2）希尔排序的思想：设待排序序列共 n 个元素，首先取一个整数
dkr[0].key->r[n-1].key
中选取最小值，与 L->r[0].key 交换，第二次从 L->r[1].key->r[n-1].key 中选
取最小值，与 L->r[1].key 交换，….，第 i 次从 L->r[i-1].key->r[n-1].key
中 选 取 最 小 值 ， 与 L->r[i-1].key 交 换 ， … .. ， 第 n-1 次 从
L->r[n-2].key->r[n-1].key 中选取最小值，与 L->r[n-2].key 交换，总共通过
n-1 次，得到一个按排序码从小到大排列的有序序列。直接选择排序是一种不稳
定的排序算法
（4）堆排序算法。首先根据初始输入数据，然后，将堆顶元素与堆尾
元素交换，缩小堆的范围并重新调整为堆，如此往复。堆排序是一种不稳定的排
序算法
（5）冒泡排序的思想：根据序列中两个元素的比较结果来对换这两
个记录在序列中的位置，将键值较大的记录向序列的尾部移动，键值较小的记录
向序列的前部移动。因此，每一趟都将较小的元素移到前面，较大的元素自然就
逐渐沉到最后面了，也就是说，最大的元素最后才能确定，这就是冒泡。冒泡排
序是一种稳定的排序算法
（6）快速排序的思想：通过一趟排序将要排序的数据分割成独立的
两部分，其中一部分的所有数据都比另外一部分的所有数据都要小(划分过程)，
然后再按此方法对这两部分数据分别进行快速排序(快速排序过程)，整个排序过
程可以递归进行，以此达到整个数据变成有序序列。快速排序是一种不稳定的排
序算法。
排序算法 算法复杂度
直接插入排序
O(n^2)
希尔排序
稳定性
稳定
不稳定
直接选择排序
O(n^2)
稳定
堆排序
O(n*log2n)
不稳定
快速排序
O(n*log2n)
不稳定
冒泡排序
O(n^2)
稳定
源程序：
#include
#include
#include
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
int MAXSIZE;
typedef int BOOL;
typedef struct{
int key;
} RedType;
typedef struct LinkList{
//记录关键字项
//记录类型
RedType r[50001];
int Length;
//顺序表长度
} LinkList;
int RandArray[50001];
//全局变量数组 便于内部操作
void RandomNum(){
int i;
srand(20000);
//标准库（被包含于中）提供两个帮助
生成伪随机数的函数：
//void srand(unsigned seed)；参数 seed 是 rand()的种子，
用来初始化 rand()的起始值。
printf("请输入要排序的个数 MAXSIZE=：");
scanf("%d",&MAXSIZE);
printf("\n");
for (i = 1; i <= MAXSIZE; i++)
RandArray[i] = (int)rand();
//函数一：int rand(void)；从 srand (seed)中指定的 seed 开始，返回一个
//构造随机序列
[seed, RAND_MAX（0x7fff）)间的随机整数
}
void InitLinkList(LinkList *L){
//构造线性表
int i;
memset(L, 0, sizeof(LinkList));
//memset:作用是在一段内存块中填
充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。
*s,int
c,size_t n) 总的作用：将已开辟内存空间 s 的首 n 个字节的值设为值 c。
*memset(void
//void
RandomNum();
for (i = 1; i <= MAXSIZE; i++)
//随机函数
L->r[i].key = RandArray[i];
//随机数赋值给
L->Length = i;
//赋值
}
int LT(int i, int j, int *CmpNum){
//比较关键字大小
//关键字比较次数
(*CmpNum)++;
if (i < j)
return 1;
else
return 0;
}
//希尔排序
void ShellInsert(LinkList *L, int dk, int *CmpNum, int *ChgNum)
{
int i, j;
RedType Temp;
for (i = dk; i < L->Length; i++){
if (LT(L->r[i].key, L->r[i - dk].key, CmpNum)){
memcpy(&Temp, &L->r[i], sizeof(RedType));
for (j = i - dk; j >= 0 && LT(Temp.key, L->r[j].key, CmpNum); j -=
//
(*ChgNum)++;
memcpy(&L->r[j + dk], &L->r[j], sizeof(RedType));
}
memcpy(&L->r[j + dk], &Temp, sizeof(RedType));
dk){
}
}
}
void ShellSort(LinkList *L, int dlta[], int t, int *CmpNum, int *ChgNum){
int k;
for (k = 0; k < t; k++)
ShellInsert(L, dlta[k], CmpNum, ChgNum);
}
//快速排序
int Partition(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){
RedType Temp;
int PivotKey;
memcpy(&Temp, &L->r[low], sizeof(RedType));
PivotKey = L->r[low].key;
while (low < high){
while (low < high && L->r[high].key >= PivotKey){
high--;
(*CmpNum)++;
}
(*ChgNum)++;
memcpy(&L->r[low], &L->r[high], sizeof(RedType));
while (low < high && L->r[low].key <= PivotKey){
low++;
(*CmpNum)++;
}
(*ChgNum)++;
memcpy(&L->r[high], &L->r[low], sizeof(RedType));
}
memcpy(&L->r[low], &Temp, sizeof(RedType));
return low;
}
void QSort(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){
int PivotLoc = 0;
if (low < high){
PivotLoc = Partition(L, low, high, CmpNum, ChgNum);
QSort(L, low, PivotLoc - 1, CmpNum, ChgNum);
QSort(L, PivotLoc + 1, high, CmpNum, ChgNum);
}
}
void QuickSort(LinkList *L, int *CmpNum, int *ChgNum){
QSort(L, 0, L->Length - 1, CmpNum, ChgNum);
}
//堆排序
void HeapAdjust(LinkList *L, int s, int m, int *CmpNum, int *ChgNum){
RedType Temp;
int j = 0;
s++;
memcpy(&Temp, &L->r[s - 1], sizeof(RedType));
for (j = 2 * s; j <= m; j *= 2){
if (j < m && LT(L->r[j - 1].key, L->r[j].key, CmpNum))
++j;
if (!LT(Temp.key, L->r[j - 1].key, CmpNum))
break;
(*ChgNum)++;
memcpy(&L->r[s - 1], &L->r[j - 1], sizeof(RedType));
s = j;
}
memcpy(&L->r[s - 1], &Temp, sizeof(RedType));
}
void HeapSort(LinkList *L, int *CmpNum, int *ChgNum){
int i = 0;
RedType Temp;
for (i = L->Length / 2-1; i >= 0; i--)
HeapAdjust(L, i, L->Length, CmpNum, ChgNum);
for (i = L->Length; i > 1; i--){
memcpy(&Temp, &L->r[0], sizeof(RedType));
(*ChgNum)++;
memcpy(&L->r[0], &L->r[i - 1], sizeof(RedType));
memcpy(&L->r[i - 1], &Temp, sizeof(RedType));
HeapAdjust(L, 0, i - 1, CmpNum, ChgNum);
}
}
//冒泡排序
void BubbleSort(LinkList *L, int *CmpNum, int *ChgNum){
int i, j;
RedType temp;
for (i = 1; i <= MAXSIZE; i++){
for (j = 1; j <= MAXSIZE - i; j++){
if (!LT(L->r[j].key, L->r[j + 1].key, CmpNum)){
(*ChgNum)++;
memcpy(&temp, &L->r[j], sizeof(RedType));
memcpy(&L->r[j], &L->r[j + 1], sizeof(RedType));
memcpy(&L->r[j + 1], &temp, sizeof(RedType));
}
}
}
}
//选择排序
int SelectMinKey(LinkList *L, int k, int *CmpNum)
{
int Min = k;
for (; k < L->Length; k++){
if (!LT(L->r[Min].key, L->r[k].key, CmpNum))
Min = k;
}
return Min;
}
void SelSort(LinkList *L, int *CmpNum, int *ChgNum){
int i, j;
RedType temp;
for (i = 0; i < L->Length; i++){
j = SelectMinKey(L, i, CmpNum);
if (i != j){
(*ChgNum)++;
memcpy(&temp, &L->r[i], sizeof(RedType));
memcpy(&L->r[i], &L->r[j], sizeof(RedType));
memcpy(&L->r[j], &temp, sizeof(RedType));
}
}
}
void SelectSort(){
printf("
printf("
printf("
printf("
printf("
printf("
printf("
printf("
printf("
printf("
printf("Please Select the Operate:");
----------------------------\n");
0. 下一组测试数据 *\n");
*
*
1. 插入排序
*\n");
* \n");
2. 希尔排序
*
* \n");
3. 快速排序
*
*
4. 堆排序
* \n");
*\n");
5. 冒泡排序
*
*\n");
6. 选择排序
*
*
7. 退出程序
*\n");
----------------------------\n\n ");
}
void AllAbove(LinkList *L, int *CmpNum, int *ChgNum){
int TempTime, i,j;
int SpendTime;
int dlta[3] = {
7, 3, 1
};
int Indata[1] = {
1
};
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n 插入排序:\n");
TempTime = (int)GetTickCount();
ShellSort(L, Indata, 1, &CmpNum[0], &ChgNum[0]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\n 关键字比较次数=%d\t 关键字移动次数=%d\t 运行时间=%dms\n",
//cpu 运行初始时间
CmpNum[0], ChgNum[0],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n 希尔排序:\n");
TempTime = (int)GetTickCount();
ShellSort(L, dlta, 3, &CmpNum[1], &ChgNum[1]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\n 关键字比较次数=%d\t 关键字移动次数=%d\t 运行时间=%dms\n",
CmpNum[1], ChgNum[1],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n 快速排序:\n");
TempTime = (int)GetTickCount();
QuickSort(L, &CmpNum[2], &ChgNum[2]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\n 关键字比较次数=%d\t 关键字移动次数=%d\t 运行时间=%dms\n",
CmpNum[2], ChgNum[2],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n 堆排序:\n");
TempTime = (int)GetTickCount();
HeapSort(L, &CmpNum[3], &ChgNum[3]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\n 关键字比较次数=%d\t 关键字移动次数=%d\t 运行时间=%dms\n",
CmpNum[3], ChgNum[3],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n 冒泡排序:\n");
TempTime = (int)GetTickCount();
BubbleSort(L, &CmpNum[4], &ChgNum[4]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\n 关键字比较次数=%d\t 关键字移动次数=%d\t 运行时间=%dms\n",
CmpNum[4], ChgNum[4],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i];
//随机数列复位
printf("\n 选择排序:\n");
TempTime = (int)GetTickCount();
SelSort(L, &CmpNum[5], &ChgNum[5]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\n 关键字比较次数=%d\t 关键字移动次数=%d\t 运行时间=%dms\n",
CmpNum[5], ChgNum[5],SpendTime);
}
int main()
{
int i,j;
int select = 0;
int dlta[3] = {7, 3, 1};
int Indata[1] = {1};
int CmpNum[8], ChgNum[8];
int SpendTime = 0;
int TempTime;
//记录比较次数 移动次数
//cpu 运行初始时间
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
