一、实验目的
掌握快速排序算法的基本思想
掌握快速排序的实现方法
掌握快速排序的时间性能
二、实验要求
熟悉C++语言编程
掌握快速排序的原理
三、实验内容
1、问题描述
用快速排序实现对无序序列的排序。
2、算法
基本思想：
任取待排序记录序列中的某个记录（例如取第一个记录）作为基准（枢），按照该记录的关键字大小，将整个记录序列划分为左右两个子序列：
左侧子序列中所有记录的关键字都小于或等于基准记录的关键字
右侧子序列中所有记录的关键字都大于基准记录的关键字
算法：
1、取序列第一个记录为枢轴记录，其关键字为Pivotkey；指针low指向序列第一个记录位置（low=1），指针high指向序列最后一个记录位置（High=SeqList.Len）
2、从high指向的记录开始，向前找到第一个关键字的值小于Pivotkey的记录，将其放到low指向的位置，low++
3、从low指向的记录开始，向后找到第一个关键字的值大于Pivotkey的记录，将其放到high指向的位置，high--
4、重复2、3，知道low==high，将枢轴记录放在low（high）指向的位置
3、输入
共一行：第一个数字n表示样本数目，其后跟n个样本
4、输入样本
8 5 6 7 9 3 4 8 2
5、输出
第一行：原始样本序列
第二行：第一趟快速排序结果
第三行：最终排序结果
6、输出样本
5 6 7 9 3 4 8 2
2 4 3 5 9 7 8 6
2 3 4 5 6 7 8 9
四、实验步骤
1、顺序表的定义
2、快速排序函数
3、顺序表显示函数
4、主函数
#define MAXLISTLEN 20
struct List
{
int Key[MAXLISTLEN];
int Len;
}SeqList;
int FirstQuick = 'T';
void ShowSeqList();
void QuickSort(int low, int high);
int main()
{
int i;
printf("请输入顺序表的序列个数");
scanf("%d", &SeqList.Len);
printf("请输入顺序表序列并以空格分隔");
for(i = 1; i<= SeqList.Len; i++)
scanf("%d", &SeqList.Key[i]);
printf("显示原始输入序列\n");
ShowSeqList();
QuickSort(1, SeqList.Len);
printf("显示最终排序结果:\n ");
ShowSeqList();
return 1;
}
//显示顺序表显示函数
void ShowSeqList()
{
int i;
for(i = 1; i< SeqList.Len; i++)
printf("%d ", SeqList.Key[i]);
printf("%d\n", SeqList.Key[i]);
}
void QuickSort(int low, int high)
{
int i, j, Pivotkey;
i = low;
j = high;
Pivotkey = SeqList.Key[low]; //记录顺序表的上、下界
while(i< j)
{
// 当high>low的时候循环
while(i< j && SeqList.Key[j] >= Pivotkey)
{
j--;
}
if(i< j)
SeqList.Key[i++] = SeqList.Key[j];
//将比基准小的数扔向前面
while(i< j && SeqList.Key[i]< Pivotkey)
{
i++;
}
if(i< j)
{
SeqList.Key[j--] = SeqList.Key[i];
}
}
SeqList.Key[i] = Pivotkey;
//显示第一趟快速排序结果
if(FirstQuick == 'T')
{
printf("显示第一次排序结果\n");
ShowSeqList();
}
FirstQuick = 'F';
//对子序列数组进行递归快速排序
if(low< i - 1)QuickSort(low , i- 1);
if(j +1< high)QuickSort(j + 1, high);
}你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧