算法思想
起泡排序又称冒泡排序。它是通过一系列的“交换”动作完成的。首先第-个关键字和第二个关键字比较,如果第一个大,则二者交换,否则不交换:然后第二个关键字和第三个关键字比较,如果第二个大,则二者交换,否则不交换....一直按这种方式进行下去,最终最大的那个关键字被交换到了最后,-趟起泡排序完成。经过多趟这样的排序,最终使整个序列有序。这个过程中,大的关键字像石头-样“沉底”,小的关键字像气泡一样逐渐向上“浮动”,起泡排序的名字由此而来。
执行流程
参考书上的执行流程如下:
详细展示下每趟的执行流程
代码
参考书上的代码如下:
void sort(int nums[],int n) {
int i,j,flag;
int temp;
for(int i=n-1; i>=1; i--) { // 最多执行n-1趟,如果每趟执行的序列如果还有关键字交换就继续执行
flag=0;// 变量flag用来标记本趟排序是否发生了交换
for(j=1; j<=i; j++) { // 循环遍历数组中的元素
// 为什么是j<=i呢? 因为每次冒泡排序都将数组中最大的数排到最底去了,所以只需要对前i+1个元素进行冒泡排序就可以了
if(nums[j-1]>nums[j]) {
temp=nums[j];
nums[j]=nums[j-1];
nums[j-1]=temp;
flag=1;// 如果没有发生交换,则flag的值为0;如果发生了交换,则flag的值为1
}
}
if(flag==0) { // 一趟排序过程中没有发生关键字交换,则证明序列有序,排序结束
return;
}
}
}
自己写的代码:
/* 冒泡排序 */
/* nums[]指的是要进行冒泡排序的数组;n指的是数组长度 */
void bubbleSort(int nums[],int n) {
int count=0;// 计数器,统计没有发生交换的次数
for(int i=0; i<n-1; i++) { // 遍历循环数组中的元素
// 为什么要i<n-1而不是i<n呢?因为下面会对nums[i]>nums[i+1]进行判断,当i<n时,nums[i+1]=nums[n]会发生溢出
if(nums[i]>nums[i+1]) { // 对数组中的第i个元素和第i+1个元素进行比较判断
int temp=nums[i];// 如果nums[i]>nums[i+1]则交换两个元素的值
nums[i]=nums[i+1];
nums[i+1]=temp;
} else {
count++;// 如果没有发生交换则统计“没有交换”的次数
}
}
if(count==n-1) { // 当“没有交换”的次数等于n-1时,则排序完成
return;
} else {
bubbleSort(nums,n);// 否则递归循环进行排序
}
}
完整代码如下:
#include<stdio.h>
/* 打印数组元素 */
void print(int nums[],int n) {
printf("\n");
for(int i=0; i<n; i++) {
printf("%d\t",nums[i]);
}
printf("\n");
}
/* 冒泡排序 */
/* nums[]指的是要进行冒泡排序的数组;n指的是数组长度 */
void bubbleSort(int nums[],int n) {
int count=0;// 计数器,统计没有发生交换的次数
for(int i=0; i<n-1; i++) { // 遍历循环数组中的元素
// 为什么要i<n-1而不是i<n呢?因为下面会对nums[i]>nums[i+1]进行判断,当i<n时,nums[i+1]=nums[n]会发生溢出
if(nums[i]>nums[i+1]) { // 对数组中的第i个元素和第i+1个元素进行比较判断
int temp=nums[i];// 如果nums[i]>nums[i+1]则交换两个元素的值
nums[i]=nums[i+1];
nums[i+1]=temp;
} else {
count++;// 如果没有发生交换则统计“没有交换”的次数
}
}
if(count==n-1) { // 当“没有交换”的次数等于n-1时,则排序完成
return;
} else {
bubbleSort(nums,n);// 否则递归循环进行排序
}
}
int main() {
int nums[]= {49,38,65,97,76,13,27,49};
int n=8;// nums数组的长度
printf("排序前:");
print(nums,n);
bubbleSort(nums,n);// 进行希尔排序
printf("排序后:");
print(nums,n);
return 0;
}
运行结果如下: