【数据结构实验】排序（一）冒泡排序改进算法 Bubble及其性能分析

文章目录

1. 引言
2. 冒泡排序算法原理
- 2.1 传统冒泡排序
- 2.2 改进的冒泡排序
3. 实验内容
- 3.1 实验题目
- - （一）输入要求
  - （二）输出要求
- 3.2 算法实现
4. 实验结果
5. 实验结论

1. 引言

排序算法是计算机科学中一个重要而基础的研究领域，不同的排序算法在不同场景下有着不同的优劣势。冒泡排序是最简单直观的排序算法之一，其核心思想是通过反复交换相邻元素，将未按次序排列的元素移到正确位置。本文将着重介绍改进的冒泡排序算法，探讨其原理、实现细节以及在不同情境下的性能表现。

2. 冒泡排序算法原理

2.1 传统冒泡排序

冒泡排序的基本思想是通过反复比较相邻的两个元素，并将较大的元素交换到右侧，逐步将最大的元素移到最右端。这个过程类似于气泡上浮，因此得名冒泡排序，其ADL语言表示如下：
在这里插入图片描述

2.2 改进的冒泡排序

改进的冒泡排序在传统冒泡排序的基础上，通过记录每一趟排序中最后一次交换的位置，减少了比较的次数。这一改进可以提高算法的效率，特别是在序列基本有序的情况下，其ADL语言表示如下：在这里插入图片描述

3. 实验内容

3.1 实验题目

实现冒泡排序改进算法 Bubble.

（一）输入要求

第一组输入数据：
{1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20}
第二组输入数据：
{20，19，18，17，16，15，14，13，12，11，10，9，8，7，6，5，4，3，2，1}
第三组输入数据：
{1，2，3，4，5，8，7，6，9，10，11，18，13，14，15，16，17，12，19，20}
第四组输入数据：
{1，3，2，5，4，7，6，9，8，11，10，13，12，15，14，17，16，19，18，20}

（二）输出要求

对每组输入数据，输出以下信息（要求必须要有关于输出数据的明确的提示信息）：

输出冒泡的总趟数；
输出每趟冒泡的记录区间；
输出每趟冒泡关键词的比较次数和记录移动次数；
输出整个排序过程总的关键词比较次数和总的记录移动次数

3.2 算法实现

#include <stdio.h>
#include <stdlib.h>void Bubble(int R[20],int n){int bound,i,j,t,e,Compare=0,Move=0,times=0;bound=n;while(bound){int compare=0,move=0;t=0;for(j=0;j<bound-1;j++){if(R[j]>R[j+1]){compare++;e=R[j];R[j]=R[j+1];R[j+1]=e;t=j;}move++;}times++;printf("该趟冒泡的记录区间为:0—%d",bound);printf("\n关键词比较次数是%d，记录移动次数是%d\n",compare,move);bound=t;Compare+=compare;Move+=move;}printf("冒泡的总趟数:%d\n",times);printf("关键词的总比较次数是%d，总的记录移动次数是%d\n",Compare,Move);
}
int main(){int i;//int R[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};//int R[20]={20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};int R[20]={1,2,3,4,5,8,7,6,9,10,11,18,13,14,15,16,17,12,19,20};//int R[20]={1,3,2,5,4,7,6,9,8,11,10,13,12,15,14,17,16,19,18,20};Bubble(R,20);for(i=0;i<20;i++)printf("%d ",R[i]);return 0;
}