起泡排序算法演示

全国青少年信息学奥林匹克联赛排序算法一、插入排序(Insertion Sort)1. 基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

2. 排序过程：【示例】：[初始关键字] [49] 38 65 97 76 13 27 49J=2(38) [38 49] 65 97 76 13 27 49J=3(65) [38 49 65] 97 76 13 27 49J=4(97) [38 49 65 97] 76 13 27 49J=5(76) [38 49 65 76 97] 13 27 49J=6(13) [13 38 49 65 76 97] 27 49J=7(27) [13 27 38 49 65 76 97] 49J=8(49) [13 27 38 49 49 65 76 97]Procedure InsertSort(Var R : FileType);//对R[1..N]按递增序进行插入排序, R[0]是监视哨//Beginfor I := 2 To N Do //依次插入R[2],...,R[n]//beginR[0] := R[I]; J := I - 1;While R[0] < R[J] Do //查找R[I]的插入位置//beginR[J+1] := R[J]; //将大于R[I]的元素后移//J := J - 1endR[J + 1] := R[0] ; //插入R[I] //endEnd; //InsertSort //二、选择排序1. 基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2. 排序过程：【示例】：初始关键字 [49 38 65 97 76 13 27 49]第一趟排序后 13 ［38 65 97 76 49 27 49]第二趟排序后 13 27 ［65 97 76 49 38 49]第三趟排序后 13 27 38 [97 76 49 65 49]第四趟排序后 13 27 38 49 [49 97 65 76]第五趟排序后 13 27 38 49 49 [97 97 76]第六趟排序后 13 27 38 49 49 76 [76 97]第七趟排序后 13 27 38 49 49 76 76 [ 97]最后排序结果 13 27 38 49 49 76 76 97Procedure SelectSort(Var R : FileType); //对R[1..N]进行直接选择排序//Beginfor I := 1 To N - 1 Do //做N - 1趟选择排序//beginK := I;For J := I + 1 To N Do //在当前无序区R[I..N]中选最小的元素R[K]//beginIf R[J] < R[K] Then K := Jend;If K <> I Then //交换R[I]和R[K] //begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end;endEnd. //SelectSort //三、冒泡排序(BubbleSort)1. 基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

双重循环排序与冒泡排序算法双重循环排序双重循环排序算法是⼀种⾮常简单的排序算法，这种算法很容易让⼈理解，也很实⽤，但是排序的效率很低。

基本思路是⽤第⼀个数与后⾯的所有数进⾏⽐较，然后把最⼩的数放到第⼀个位置，然后⽤第⼆个数与后⾯的所有数进⾏⽐较，然后把第⼆个最⼩的数放到第⼆个位置，然后⽤第三个数....最后⽤倒数第⼆个数进⾏⽐较，这样最终形成从⼩到⼤的排列顺序。

C语⾔源代码：1 #include<stdio.h>23int main()4 {5int i, j, t;6int a[10] = {2, 5, 8, 1, 3, 4, 7, 9, 0, 6}; // 共10个数据7// 双重for循环排序8for(i=0; i<9; i++) // 从第1个到第9个9 {10for(j=i+1; j<10; j++) // 将a[i]和后⾯的所有数进⾏⽐较11 {12if(a[i]>a[j]) // 如果a[i]⼤于后⾯的数则进⾏交换13 {14 t=a[i];15 a[i]=a[j];16 a[j]=t;17 }18 }19 }20 printf("排序后：\n");21for(i=0; i<10; i++)22 {23 printf("%d ", a[i]);24 }25return0;26 }冒泡排序算法：基本思路：假设有10个数，则需要进⾏10-1趟(即9趟)⽐较，每趟从第⼀个数开始与后⾯相邻的⼀个数⽐较，如果前⾯的数⽐后⾯相邻的数⼤则相互交换，经过⼀趟⽐较之后，最⼤的那个数被放在最后⾯。

然后进⾏下⼀趟⽐较，⼜从第⼀个数开始⽐较，但不包括前⾯⼀趟已经找出来的那个最⼤的数，因此下⼀趟要⽐前⼀趟⽐较的次数少⼀次。

可见这种算法每进⾏⼀趟后会把本趟最⼤的数“升到”末尾，如⽓泡⼀样逐步升出⽔⾯，故称为“冒泡法”或“起泡法”。

C语⾔源代码：1 #include<stdio.h>23int main()4 {5int i, j, t;6int a[10] = {2, 5, 8, 1, 3, 4, 7, 9, 0, 6}; // 共10个数据7// 冒泡排序8for(i=0; i<9; i++) // 总共需要⽐较9趟9 {10for(j=0; j<9-i; j++) // 只需⽐较前⾯的数，最后的是最⼤数，第⼀趟i为0时⽐较9次，第⼆趟⽐较8次，第三趟⽐较7次....11 {12if(a[j]>a[j+1]) // 如果a[j]⼤于后⾯相邻的⼀个数则进⾏交换13 {14 t=a[j];15 a[j]=a[j+1];16 a[j+1]=t;17 }18 }19 }20 printf("排序后：\n");21for(i=0; i<10; i++)22 {23 printf("%d ", a[i]);24 }25return0;26 }。

假设在排序过程中，记录序列无序序列R[1..n-i+1] 有序序列 R[n-i+2..n]比较相邻记录，将关键字最大的记第 i 趟起泡排序录交换到 n-i+1 的位置上无序序列R[1..n-i] 有序序列 R[n-i+1..n]49 38 65 97 7613 27 49 初始关键字3849657613274997第一趟排序后38496513274976第二趟排序后384913274965第三趟排序后3813274949第四趟排序后13273849第五趟排序后132738第六趟排序后图10.6起泡排序示例void BubbleSort(Elem R[ ], int n) {i = n;while (i >1) {lastExchangeIndex = 1;for (j = 1; j < i; j++)if (R[j+1].key < R[j].key) {Swap(R[j], R[j+1]);lastExchangeIndex = j; //记下进行交换的记录位置} //ifi = lastExchangeIndex; // 本趟进行过交换的// 最后一个记录的位置} // while} // BubbleSort起泡排序算法注意:1. 起泡排序的结束条件为，最后一趟没有进行“交换记录”。

2. 一般情况下，每经过一趟“起泡”，“i 减1”，但并不是每趟都如此。

例如:5 2 3 1 9 7 8 for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) …i=72 53515 7 98 9 i=61 3 i=2时间分析:最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡 “比较”的次数：n-1“移动”的次数：最坏的情况（关键字在记录序列中逆序有序）： 需进行n-1趟起泡“比较”的次数：2 ) 1 ( ) 1( 2- = - ∑ = n n i ni “移动”的次数：2 )1 ( 3 ) 1 ( 3 2- =- ∑ = n n i ni二、快速排序（Quick sort）目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。

输入10个数，用“起泡法”对10个数排序（由小到大）。

“起泡法”算法：以六个数9、8、5、4、2、0为例。

第1趟比较（p83，图6.1）第2趟比较（p84，图6.2）第1趟比较后，剩5个数未排好序；两两比较5次第2趟比较后，剩4个数未排好序；两两比较4次第3趟比较后，剩3个数未排好序；两两比较3次第4趟比较后，剩2个数未排好序；两两比较2次第5趟比较后，全部排好序；两两比较1次算法结论：对于n个数的排序，需进行n-1趟比较，第j趟比较需进行n-j次两两比较。

程序流程图：（用两层嵌套循环实现）程序：设需排序的数有10个，定义数组大小为11，使用a[1]～a[10]存放10个数，a[0]不用。

main()int a[11]; /* 用a[1]～a[10], a[0]不用*/int i,j,t；/* i,j作循环变量，t作两两比较的临时变量*/printf("input 10 numbers:\n");for(i=1;i<11;i++)scanf("%d",&a[i]);/* 输入10个整数*/printf("\n");for(j=1;j<=9;j++) /* 第j趟比较*/for(i=1;i<=10-j; i++) /* 第j趟中两两比较10-j次*/if (a[i] > a[i+1]) /* 交换大小*/{ t = a[i]; a[i] = a[i+1]; a[i+1] = t; }printf("the sorted numbers:\n");for(i=1;i<11;i++)printf("%d",a[i]);}。

8.11写‎一函数，用‎起泡法对输‎入的10个‎字符按由小‎到大顺序排‎列2008‎-01-0‎816:‎45/*运‎行结果为：‎请输入1‎个字符串：‎chin‎s ungl‎e排序后‎字符串为：‎c eghi‎l nnsu‎.*/‎#incl‎u de <‎s tdio‎.h>#‎i nclu‎d e <s‎t ring‎.h>#‎d efin‎e N 1‎0voi‎d sor‎t(cha‎r str‎[]){‎int ‎i,j,t‎;for‎(i=1;‎i<N;i‎++)//‎总共进行N‎-1次冒泡‎运算fo‎r(j=0‎;j<N-‎i;j++‎)//第一‎次N-1个‎回合，第二‎次N-2个‎回合，最后‎一次即第N‎-1次一个‎回合if‎(str[‎j]>st‎r[j+1‎]){‎t=str‎[j];‎s tr[j‎]=str‎[j+1]‎;str‎[j+1]‎=t;}‎}m‎a in()‎{ch‎a r st‎r[100‎];do‎{pr‎i ntf(‎"请输入1‎个字符串：‎\n");‎scan‎f("%s‎",str‎);}‎w hile‎(strl‎e n(st‎r)!=1‎0);s‎o rt(s‎t r);‎p rint‎f("排序‎后字符串为‎：%s.\‎n",st‎r);}‎#‎i nclu‎d e <s‎t dio.‎h>vo‎i d ma‎i n()‎{in‎t a[1‎0];‎i nt i‎,j,te‎m p;‎p rint‎f("请输‎入10个数‎：");‎for(‎i=0;i‎<10;i‎++)‎ sca‎n f("%‎d",&a‎[i]);‎for‎(i=0;‎i<10;‎i++)‎ fo‎r(j=i‎+1;j<‎10;j+‎+)‎ if‎(a[i]‎>a[j]‎)‎ {‎‎‎t emp=‎a[i];‎‎‎a[i]=‎a[j];‎‎‎a[j]=‎t emp;‎‎ }‎for(‎i=0;i‎<10;i‎++)‎ pri‎n tf("‎%d\t"‎,a[i]‎);} ‎#‎i nclu‎d e <s‎t dio.‎h>v‎o id m‎a in()‎{i‎n t i,‎j, t‎e mp;‎int ‎e leme‎n t[10‎];i‎n t *s‎t art,‎*end‎;‎‎prin‎t f("\‎n请输入1‎0个数：\‎n ");‎for‎(i = ‎0;i <‎10;i‎++)‎{‎ sca‎n f("%‎d", &‎e leme‎n t[i]‎);}‎‎s tart‎= el‎e ment‎; /* ‎s tart‎指针指向‎数组的第一‎个元素 *‎/en‎d = e‎l emen‎t + 1‎0; /*‎end ‎指针指向数‎组的最后一‎个元素 *‎/ pr‎i ntf(‎"\n原始‎数组：\n‎");‎/* 输‎出原始数组‎*/‎f or(;‎s tart‎< en‎d;sta‎r t++)‎{‎ pri‎n tf("‎%d "‎, *st‎a rt);‎}‎prin‎t f("\‎n\n排序‎后的数组：‎\n");‎/‎*输出排‎序后的数组‎*/‎s tart‎=elem‎e nt;‎for(‎i = 1‎0;i >‎0;i-‎-){‎fo‎r(j =‎10 -‎i;j ‎> 0;j‎--)‎{‎if(*‎(star‎t + j‎-1) >‎*(st‎a rt+j‎))‎{‎ tem‎p = *‎(star‎t + j‎-1);‎ *‎(star‎t + j‎-1) =‎*(st‎a rt+j‎);‎ *(s‎t art+‎j) = ‎t emp;‎}‎}‎}‎for(‎s tart‎= el‎e ment‎;star‎t < e‎n d;st‎a rt++‎) {‎ pri‎n tf("‎%d "‎, *st‎a rt);‎}‎p rint‎f("\n‎");}‎‎。

一、实验目的1. 理解起泡排序算法的基本原理和操作步骤。

2. 掌握C语言实现起泡排序算法的方法。

3. 通过实验验证起泡排序算法的效率，并与其他排序算法进行比较。

二、实验原理起泡排序是一种简单的排序算法，其基本思想是通过重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

走访数列的工作是重复地进行，直到没有再需要交换的元素，这意味着该数列已经排序完成。

起泡排序算法的步骤如下：1. 比较相邻的元素。

如果第一个比第二个大（升序排序），就交换它们两个。

2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。

这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

三、实验环境1. 编程语言：C语言2. 开发环境：Visual Studio Code3. 操作系统：Windows 10四、实验步骤1. 创建一个包含10个整数的数组。

2. 使用起泡排序算法对数组进行排序。

3. 输出排序前后的数组。

五、实验代码```c#include <stdio.h>void bubbleSort(int arr[], int n) {int i, j, temp;for (i = 0; i < n - 1; i++) {for (j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}int main() {int arr[10] = {64, 34, 25, 12, 22, 11, 90, 88, 76, 45}; int n = sizeof(arr) / sizeof(arr[0]);printf("Original array: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");bubbleSort(arr, n);printf("Sorted array: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;}```六、实验结果与分析1. 实验结果：程序输出了排序前后的数组，验证了起泡排序算法的正确性。