名称：内部排序算法比较
内容：在教科书中，各种内部排序算法的时间复杂的分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各种算法的关键字比较次数和关键字移动次数，以取得直观感受。
任务：(1)对以下7中常会用的内部排序算法进行比较：冒泡排序、直接插入排序、简单选择排序、希尔排序、堆排序、归并排序、快速排序。(2)待排序表的表不小于2000；其中的数据要用伪随机数程序产生；至少要用到5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为3次)。(3)最后要对结果做出简单分析，包括对各组数据得出结果波动大小的解释。
人狠话不多，直接上代码！！！
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAX 2000
typedef struct SORTTYPE
{
char name[30]; //排序名称
double num_compare[6]; //比较的次数 前5个为五次不同表排序的结果，第6次为平均次数
double num_move[6]; //移动的次数 前5个为五次不同表排序的结果，第6次为平均次数
} ST; //存储排序算法效率的数据
double num_compare = 0, num_move = 0; //关键字比较和移动的次数
ST st[7]; //七种算法的分析数据
void InsertSort(int a[], int n); //直接插入排序算法
void ShellSort(int a[], int n); //希尔排序算法
void BubbleSort(int a[], int n); //冒泡排序算法
void QuickSort(int a[], int left, int right); //快速排序算法
void SelectSort(int a[],int len); //简单选择排序算法
void HeapSort(int a[], int size); //堆排序算法
void MergeSort(int a[],int left,int right); //归并排序算法
void Merge(int a[],int left,int right,int mid); //将分开的数组合并
void Down(int a[], int i, int n); //将数组调整为大根堆
void BuildHeap(int a[], int size); //初始化大根堆
int partition(int a[], int s, int t); //快速排序一趟划分
void menu(); //菜单
void printArray(int a[]); //打印数组数据
void GetrandArray(int a[]); //给数组生成随机数
void resetData(); //重置num_compare,num_move为 0
void option1(int a[]); //直接插入排序操作
void option2(int a[]); //希尔排序操作
void option3(int a[]); //冒泡排序操作
void option4(int a[]); //快速排序操作
void option5(int a[]); //简单选择排序操作
void option6(int a[]); //堆排序操作
void option7(int a[]); //归并排序操作
void option8(); //效率比较
int main () {
int a[MAX]; //列表数组
int option; //操作
srand((unsigned)time(NULL)); //随机种子
do {
system("cls");
menu();
scanf("%d", &option);
switch (option) {
case 1:
option1(a);
break;
case 2:
option2(a);
break;
case 3:
option3(a);
break;
case 4:
option4(a);
break;
case 5:
option5(a);
break;
case 6:
option6(a);
break;
case 7:
option7(a);
break;
case 8:
option8();
break;
default:
break;
}
system("pause");
} while(option != 9);
return 0;
}
/*
菜单
*/
void menu() {
printf("***************************************************\n");
printf("\t\t1.直接插入排序法\n");
printf("\t\t2.希尔排序法\n");
printf("\t\t3.冒泡排序法\n");
printf("\t\t4.快速排序法\n");
printf("\t\t5.简单选择排序法\n");
printf("\t\t6.堆排序法\n");
printf("\t\t7.归并排序法\n");
printf("\t\t8.效率比较\n");
printf("\t\t9.退出\n");
printf("***************************************************\n");
printf("请选择操作：");
}
/*
为数组生成随机数
*/
void GetrandArray(int a[]) {
int i;
for (i = 0; i < MAX; i++)
a[i] = rand() % 2000;
}
/*
重置num_compare,num_move为 0
*/
void resetData() {
num_compare = 0;
num_move = 0;
}
/*
显示数组数据
*/
void printArray(int a[]) {
int i;
for (i = 0; i < MAX; i++) {
printf("%d ",a[i]);
}
printf("\n");
}
/*
直接插入排序操作
*/
void option1(int a[]){
int i;
for (i = 0; i < 5; i++) {
resetData();
GetrandArray(a);
printf("\n");
printf("************************************第%d次排序前：************************************\n\n", i+1);
printArray(a);
InsertSort(a, MAX);
printf("\n");
printf("************************************第%d次排序后：************************************\n\n",i+1);
printArray(a);
st[0].num_compare[i] = num_compare;
st[0].num_move[i] = num_move;
}
double sum_num_compare = 0, sum_num_move = 0;
for(i = 0; i < 5; i++){
sum_num_compare += st[0].num_compare[i];
sum_num_move += st[0].num_move[i];
}
st[0].num_compare[5] = sum_num_compare / 5;
st[0].num_move[5] = sum_num_move / 5;
printf("直接插入排序算法的比较与移动次数的对比：\n\n");
printf("次序 比较次数 移动次数\n");
for(i = 0; i < 5; i++){
printf("%d\t\t%-18.2f %.2f\n",i+1, st[0].num_compare[i], st[0].num_move[i]);
}
printf("\n\n直接插入排序法：\n一共比较了%.2f次，移动了%.2f次\n", st[0].num_compare[5], st[0].num_move[5]);
strcpy(st[0].name, "直接插入排序");
}
/*
希尔排序操作
*/
void option2(int a[]){
int i;
for (i = 0; i < 5; i++) {
resetData();
GetrandArray(a);
printf("\n");
printf("************************************第%d次排序前：************************************\n\n", i+1);
printArray(a);
ShellSort(a, MAX);
printf("\n");
printf("************************************第%d次排序后：************************************\n\n",i+1);
printArray(a);
st[1].num_compare[i] = num_compare;
st[1].num_move[i] = num_move;
}
double sum_num_compare = 0, sum_num_move = 0;
for(i = 0; i < 5; i++){
sum_num_compare += st[1].num_compare[i];
sum_num_move += st[1].num_move[i];
}
st[1].num_compare[5] = sum_num_compare / 5;
st[1].num_move[5] = sum_num_move / 5;
printf("希尔排序算法的比较与移动次数的对比：\n\n");
printf("次序 比较次数 移动次数\n");
for(i = 0; i < 5; i++){
printf("%d\t\t%-18.2f %.2f\n",i+1, st[1].num_compare[i], st[1].num_move[i]);
}
printf("\n\n希尔排序法：\n一共比较了%.2f次，移动了%.2f次\n", st[1].num_compare[5], st[1].num_move[5]);
strcpy(st[1].name, "希尔排序");
}
/*
冒泡排序操作
*/
void option3(int a[]){
int i;
for (i = 0; i < 5; i++) {
resetData();
GetrandArray(a);
printf("\n");
printf("************************************第%d次排序前：************************************\n\n", i+1);
printArray(a);
BubbleSort(a, MAX);
printf("\n");
printf("************************************第%d次排序后：************************************\n\n",i+1);
printArray(a);
st[2].num_compare[i] = num_compare;
st[2].num_move[i] = num_move;
}
double sum_num_compare = 0, sum_num_move = 0;
for(i = 0; i < 5; i++){
sum_num_compare += st[2].num_compare[i];
sum_num_move += st[2].num_move[i];
}
st[2].num_compare[5] = sum_num_compare / 5;
st[2].num_move[5] = sum_num_move / 5;
printf("冒泡排序算法的比较与移动次数的对比：\n\n");
printf("次序 比较次数 移动次数\n");
for(i = 0; i < 5; i++){
printf("%d\t\t%-18.2f %.2f\n",i+1, st[2].num_compare[i], st[2].num_move[i]);
}
printf("\n\n冒泡排序法：\n一共比较了%.2f次，移动了%.2f次\n", st[2].num_compare[5], st[2].num_move[5]);
strcpy(st[2].name, "冒泡排序");
}
/*
快速排序操作
*/
void option4(int a[]){
int i;
for (i = 0; i < 5; i++) {
resetData();
GetrandArray(a);
printf("\n");
printf("************************************第%d次排序前：************************************\n\n", i+1);
printArray(a);
QuickSort(a, 0, MAX-1);
printf("\n");
printf("************************************第%d次排序后：************************************\n\n",i+1);
printArray(a);
st[3].num_compare[i] = num_compare;
st[3].num_move[i] = num_move;
}
double sum_num_compare = 0, sum_num_move = 0;
for(i = 0; i < 5; i++){
sum_num_compare += st[3].num_compare[i];
sum_num_move += st[3].num_move[i];
}
st[3].num_compare[5] = sum_num_compare / 5;
st[3].num_move[5] = sum_num_move / 5;
printf("快速排序算法的比较与移动次数的对比：\n\n");
printf("次序 比较次数 移动次数\n");
for(i = 0; i < 5; i++){
printf("%d\t\t%-18.2f %.2f\n",i+1, st[3].num_compare[i], st[3].num_move[i]);
}
printf("\n\n快速排序法：\n一共比较了%.2f次，移动了%.2f次\n", st[3].num_compare[5], st[3].num_move[5]);
strcpy(st[3].name, "快速排序");
}
/*
简单选择排序操作
*/
void option5(int a[]){
int i;
for (i = 0; i < 5; i++) {
resetData();
GetrandArray(a);
printf("\n");
printf("************************************第%d次排序前：************************************\n\n", i+1);
printArray(a);
SelectSort(a, MAX);
printf("\n");
printf("************************************第%d次排序后：************************************\n\n",i+1);
printArray(a);
st[4].num_compare[i] = num_compare;
st[4].num_move[i] = num_move;
}
double sum_num_compare = 0, sum_num_move = 0;
for(i = 0; i < 5; i++){
sum_num_compare += st[4].num_compare[i];
sum_num_move += st[4].num_move[i];
}
st[4].num_compare[5] = sum_num_compare / 5;
st[4].num_move[5] = sum_num_move / 5;
printf("简单选择排序算法的比较与移动次数的对比：\n\n");
printf("次序 比较次数 移动次数\n");
for(i = 0; i < 5; i++){
printf("%d\t\t%-18.2f %.2f\n",i+1, st[4].num_compare[i], st[4].num_move[i]);
}
printf("\n\n简单选择排序法：\n一共比较了%.2f次，移动了%.2f次\n", st[4].num_compare[5], st[4].num_move[5]);
strcpy(st[4].name, "简单选择排序");
}
/*
堆排序操作
*/
void option6(int a[]){
int i;
for (i = 0; i < 5; i++) {
resetData();
GetrandArray(a);
printf("\n");
printf("************************************第%d次排序前：************************************\n\n", i+1);
printArray(a);
HeapSort(a, MAX);
printf("\n");
printf("************************************第%d次排序后：************************************\n\n",i+1);
printArray(a);
st[5].num_compare[i] = num_compare;
st[5].num_move[i] = num_move;
}
double sum_num_compare = 0, sum_num_move = 0;
for(i = 0; i < 5; i++){
sum_num_compare += st[5].num_compare[i];
sum_num_move += st[5].num_move[i];
}
st[5].num_compare[5] = sum_num_compare / 5;
st[5].num_move[5] = sum_num_move / 5;
printf("堆排序算法的比较与移动次数的对比：\n\n");
printf("次序 比较次数 移动次数\n");
for(i = 0; i < 5; i++){
printf("%d\t\t%-18.2f %.2f\n",i+1, st[5].num_compare[i], st[5].num_move[i]);
}
printf("\n\n堆排序法：\n一共比较了%.2f次，移动了%.2f次\n", st[5].num_compare[5], st[5].num_move[5]);
strcpy(st[5].name, "堆排序");
}
/*
归并排序操作
*/
void option7(int a[]){
int i;
for (i = 0; i < 5; i++) {
resetData();
GetrandArray(a);
printf("\n");
printf("************************************第%d次排序前：************************************\n\n", i+1);
printArray(a);
MergeSort(a, 0, MAX-1);
printf("\n");
printf("************************************第%d次排序后：************************************\n\n",i+1);
printArray(a);
st[6].num_compare[i] = num_compare;
st[6].num_move[i] = num_move;
}
double sum_num_compare = 0, sum_num_move = 0;
for(i = 0; i < 5; i++){
sum_num_compare += st[6].num_compare[i];
sum_num_move += st[6].num_move[i];
}
st[6].num_compare[5] = sum_num_compare / 5;
st[6].num_move[5] = sum_num_move / 5;
printf("归并排序算法的比较与移动次数的对比：\n\n");
printf("次序 比较次数 移动次数\n");
for(i = 0; i < 5; i++){
printf("%d\t\t%-18.2f %.2f\n",i+1, st[6].num_compare[i], st[6].num_move[i]);
}
printf("\n\n归并排序法：\n一共比较了%.2f次，移动了%.2f次\n", st[6].num_compare[5], st[6].num_move[5]);
strcpy(st[6].name, "归并排序");
}
/*
效率比较
*/
void option8() {
int i;
printf("各种排序算法的比较与移动次数的对比：\n\n");
printf(" 名称 比较次数 移动次数\n");
for (i = 0; i < 7; i++) {
printf("%-18s%-18.2f %.2f\n", st[i].name, st[i].num_compare[5], st[i].num_move[5]);
}
int max_num_compare, max_num_move, min_num_compare, min_num_move;
max_num_compare = st[0].num_compare[5];
max_num_move = st[0].num_move[5];
min_num_compare = st[0].num_compare[5];
min_num_move = st[0].num_move[5];
int index_max_num_compare, index_max_num_move, index_min_num_compare, index_min_num_move;
index_max_num_compare = 0;
index_max_num_move = 0;
index_min_num_compare = 0;
index_min_num_move = 0;
for (i = 1; i < 7; i++) {
if (max_num_compare < st[i].num_compare[5]) {
max_num_compare = st[i].num_compare[5];
index_max_num_compare = i;
}
if (min_num_compare > st[i].num_compare[5]) {
min_num_compare = st[i].num_compare[5];
index_min_num_compare = i;
}
if (max_num_move < st[i].num_move[5]) {
max_num_move = st[i].num_move[5];
index_max_num_move = i;
}
if (min_num_move > st[i].num_move[5]) {
min_num_move = st[i].num_move[5];
index_min_num_move = i;
}
}
printf("\n");
printf("平均移动次数的最多的排序法是%s，次数为%.2f。\n",st[index_max_num_move].name,st[index_max_num_move].num_move[5]);
printf("平均移动次数的最少的排序法是%s，次数为%.2f。\n",st[index_min_num_move].name,st[index_min_num_move].num_move[5]);
printf("平均比较次数的最多的排序法是%s，次数为%.2f。\n",st[index_max_num_compare].name,st[index_max_num_compare].num_compare[5]);
printf("平均比较次数的最少的排序法是%s，次数为%.2f。\n",st[index_min_num_compare].name,st[index_min_num_compare].num_compare[5]);
}
/*
直接插入排序算法
*/
void InsertSort(int a[], int n) {
int i, j;
int tmp;
for (i = 1; i < n; i++) //for循环内一定比较了n-1次，if判断语句
{
if (a[i] < a[i - 1]) //一旦出现了逆序的关键字，就进行插入
{
tmp = a[i];
j = i - 1;
num_compare++;
/*
往后移动一个位置，腾空间给tmp
*/
do {
a[j + 1] = a[j];
num_move++; //移动加一
j--;
num_compare++; //比较次数加一
}
while (j >= 0 && a[j] > tmp);
a[j + 1] = tmp; //最后把tmp放在对应的位置
num_move += 2; //移动的temp
}
}
}
/*
希尔排序算法
*/
void ShellSort(int a[], int n) {
int i, j, d;
int tmp;
d = n / 2;
while (d > 0) {
for (i = d; i < n; i++) {
tmp = a[i];
j = i - d;
while (j >= 0 && tmp < a[j]) {
num_compare++;
num_move++;
a[j + d] = a[j];
j = j - d;
}
a[j + d] = tmp;
num_move += 2; //tmp进行两次操作
}
d = d / 2;
}
}
/*
冒泡排序算法
*/
void BubbleSort(int a[], int n) {
int i, j;
for (i = 0; i < n - 1; i++){
for (j = n - 1; j > i; j--) {
if (a[j] < a[j - 1]) {
num_compare++; //比较次数加 1
num_move += 3; //移动次数增加 3
int tmp = a[j - 1];
a[j - 1] = a[j];
a[j] = tmp;
}
}
}
}
/*
快速排序算法
*/
int partition(int a[], int s, int t) { //一趟划分
int i = s, j = t;
int tmp = a[i]; //以a[i]为基准
while (i < j) {
//从两端交替向中间扫描,直至i=j为止
while (j > i && a[j] >= tmp) {
j--; //从右向左扫描,找一个小于tmp的a[j]
num_compare++; //进行比较
}
a[i] = a[j]; //找到这样的a[j],放入a[i]处
num_move++; //移动+1
while (i < j && a[i] <= tmp) {
i++; //从左向右扫描,找一个大于tmp的a[i]
num_compare++; //比较加一
}
a[j] = a[i]; //找到这样的a[i],放入a[j]处
num_move++; //移动加一
}
a[i] = tmp;
num_move += 2; //temp的交换
return i;
}
void QuickSort(int a[], int s, int t) {
//对a[s..t]的元素进行快速排序
int i;
if (s < t) {
//区间内至少存在两个元素的情况
i = partition(a, s, t);
QuickSort(a, s, i - 1); //对左区间递归排序
QuickSort(a, i + 1, t); //对右区间递归排序
}
}
/*
简单选择排序
*/
void SelectSort(int a[],int len){
int min; //用于存放最小值的下标
int i,j;
for (i = 0; i<len; i++){
min = i; //初始化选取假设的最小值
for (j = i+1; j<len; j++){
num_compare++; //a[min]要与a[i]之后的每个数都要进行比较
if (a[j]<a[min]){
min = j; //如果遇见更小值，则记录最小值下标
}
}
//内循环退出，确定了最小值
//将最小值移动到已排序序列末尾
if(min != i){
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
num_move += 3; //移动次数增加 3
}
}
}
/*
堆排序
*/
// 调整为大顶堆
void Down(int a[], int i, int n) {
int parent = i; // 父节点下标
int child = 2 * i + 1; // 子节点下标
while (child < n) {
if (child + 1 < n){
num_compare++; // 判断子节点那个大，大的与父节点比较 比较次数+1
if(a[child] < a[child + 1])
child++;
}
num_compare++;
if (a[parent] < a[child]) { // 判断父节点是否小于子节点如果小于就交换
int key = a[parent];
a[parent] = a[child];
a[child] = key;
num_move +=3; //移动次数 + 3
parent = child; // 子节点下标 赋给 父节点下标
}
child = child * 2 + 1; // 换行，比较下面的父节点和子节点
}
}
//初始化堆，使其成为大根堆
void BuildHeap(int a[], int size) {
int i;
for (i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
Down(a, i, size); // 否则有的不符合大顶堆定义
}
}
//堆排序
void HeapSort(int a[], int size) {
BuildHeap(a, size); // 初始化堆
int i;
for (i = size - 1; i > 0; i--) {
// 交换顶点和第 i 个数据
int key = a[0];
a[0] = a[i];
a[i] = key;
num_move +=3; //移动次数 + 3
Down(a, 0, i); // 重新建立大顶堆
}
}
/*
归并排序
*/
void Merge(int a[],int left,int right,int mid) {
int s[MAX];//一个新数组用来存储排序好的数组
int i = left, j = mid + 1;//两个变量分别指向左边和右边两组数的第一个数
int sor = left;
while (i <= mid && j <= right) {
num_compare++;
if (a[i] < a[j]) { //归并的过程
s[sor++] = a[i++];
num_move++;
}
else {
s[sor++] = a[j++];
num_move++;
}
}
while (i <= mid) {
s[sor++] = a[i++];//当一组数已经全部排进去之后，再将另外一组数的全部数字都排进去
num_move++;
}
while (j <= right){
s[sor++] = a[j++];
num_move++;
}
sor = left;
while (sor <= right) {//把排好序的新数组全部放回原数组里
a[sor] = s[sor];
num_move++;
sor++;
}
}
void MergeSort(int a[],int left,int right){
if(left<right){
int mid = (left + right) / 2;//从中间截开
MergeSort(a,left, mid);//把左边沿中间截开
MergeSort(a, mid + 1, right);//把右边沿中间截开
Merge(a, left, right, mid);//合并
}
}
版权声明：本文为博主作者：T1ngSh0w原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/weixin_52635170/article/details/127503974
