【冒泡排序】详解以及优化

2026/8/7 22:36:44

一、冒泡排序的核心思想

二、代码演示

1.常规思路

2.优化版本（减少了非必要排序）

3.利用冒泡原理模拟qsort函数

一、冒泡排序的核心思想

两两相邻的元素进行比较。

形象化理解：每一趟冒泡排序就像水底冒泡泡一样，将要排序的数字逐对逐对比较，从底部移动到顶端，可结合下图进行体会。

注：

①若有n个数字,则进行n-1趟冒泡排序
②每一趟排序若未排的数字为n，则需进行n-1对数字比较
③冒泡排序局限;一般只用来排序整型数据
④两个整型元素可以直接使用>或<比较
但是两个字符串、两个结构体元素是不能使用>或<比较的。
字符串可以使用strcmp函数比较

二、代码演示

1.常规思路

void bubble_sort(int arr[], int sz)//参数接收数组元素个数 { for(int i = 0; i < sz-1; i++) { for(int j = 0; j<sz-i-1; j++) { if(arr[j] > arr[j+1]) { int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } } int main() { int arr[] = {3,1,7,5,8,9,0,2,4,6}; int sz = sizeof(arr)/sizeof(arr[0]); bubble_sort(arr, sz); for(i=0; i<sz; i++) { printf("%d ", arr[i]); } return 0; }

2.优化版本（减少了非必要排序）

void bubble_sort(int arr[], int sz)//参数接收数组元素个数 { for(int i = 0; i<sz-1; i++) { int flag = 1;//假设这⼀趟已经有序了 for(int j = 0; j < sz-i-1; j++) { if(arr[j] > arr[j+1]) { flag = 0;//发⽣交换就说明，⽆序 int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } if(flag == 1) break; //这⼀趟没交换就说明已经有序，后续⽆序排序 } } int main() { int arr[] = {3,1,7,5,8,9,0,2,4,6}; int sz = sizeof(arr)/sizeof(arr[0]); bubble_sort(arr, sz); for(i=0; i<sz; i++) { printf("%d ", arr[i]); } return 0; }

3.利用冒泡原理模拟qsort函数

此时不再有数据类型的限制

#include<stdio.h> int my_cmp(const void* p1, const void* p2)//冒泡交换的判断条件 { return (*(int*)p1 - *(int*)p2);//*p1>*p2则返回大于0的数字，以此类推 } void exch(void* p1, void* p2, int size)//交换过程，将数据分成一份份交换。 { int i = 0; for (i = 0; i < size; i++) { char tmp = *((char*)p1 + i); *((char*)p1 + i) = *((char*)p2 + i); *((char*)p2 + i) = tmp; } } void my_qsort(void* base, int num, int width, int (*cmp)(void*, void*))//模拟的qsort函数，利用函数指针间接利用判断函数 { int i = 0; for (i = 0; i < (num - 1); i++)//冒泡排序趟数 { int j = 0; for (j = 0; j < (num - 1 - i); j++)//一趟冒泡排序 { if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)//判断 { exch((char*)base + j * width, (char*)base + (j + 1) * width, width);//排序 } } } } int main() { int arr[] = { 0,7,6,4,3,5,9,8,2 }; int i = 0; my_qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(int), my_cmp); for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }