算法-排序-冒泡排序

2019-11-06 06:20:39

字体：大中小

来源：转载

供稿：网友

原理

　　所谓冒泡排序法，就是对一组数字进行从大到小或者从小到大排序的一种算法（因为越大或越小的元素会经由交换慢慢“浮”到数列的顶端，故名）。具体方法是，从第一个数值开始，如果相邻两个数的排列顺序与我们的期望不同，则将两个数的位置进行交换；如果其与我们的期望一致，则不用交换。一般地，如果有N个数需要排序，则需要进行（N-1）趟起泡，改进版的冒泡排序需要排序的次数可能会有所减少。　　下面这个算法是我们很容易想到的：

void bubble_sort1(int a[],int n) { int i, j; for (i = n - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (a[j] > a[j+1]) { swap(a[j], a[j+1]); } } }}

　　根据上面排序的算法，我们以{1，3，6，5，8，4}为例进行分析。首先这样的算法对六个数来说需要排5趟，每一趟的结果如下：　　第一趟：{1，3，5，6，4，8} 　　第二趟：{1，3，5，4，6，8} 　　第三趟：{1，3，4，5，6，8} 　　第四趟：{1，3，4，5，6，8} 　　第五趟：{1，3，4，5，6，8} 　　像上面这种情况，其实我们只用了三趟数据就已经有序了，那怎样改进才能不用每次都要排（N-1）趟呢？　　其实我们可以在每次发生数据交换的地方做一个标记，如果发生了数据交换，我们就继续排下去，如果没有发生数据交换，那就说明数据已经是有序的了，此时我们就可以不用再排下去了。从而使排序更高效一些。我们可以使用下面的改进版本的冒牌排序：

void bubble_sort2(int a[], int n) { int i, j, flag; for (i = n - 1; i > 0; i--) { flag = 0; for (j = 0; j < i; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); flag = 1; } } if (flag==0) { //若没有发生交换，说明数据已经有序 break; } }}

冒泡排序的时间复杂度

　　冒泡排序的时间复杂度是O(N2)。　　假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1次！因此，冒泡排序的时间复杂度是O(N2)。

冒泡排序的稳定性

　　冒泡排序是稳定的算法，它满足稳定算法的定义。　　算法稳定性 – 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。所以这个排序算法是稳定的！

一个完整的示例

#include<stdio.h>//求数组的长度#define LEN(array) (sizeof(array))/(sizeof(array[0]))//交换两个数#define swap(a,b) (a^=b,b^=a,a^=b)// 使用时要传址//void swap(int* x, int* y) {// int tep = *x;// *x = *y;// *y = tep;//}void bubble_sort1(int a[],int n) { int i, j; for (i = n - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (a[j] > a[j+1]) { swap(a[j], a[j+1]); } } }}void bubble_sort2(int a[], int n) { int i, j, flag; for (i = n - 1; i > 0; i--) { flag = 0; for (j = 0; j < i; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); flag = 1; } } if (flag==0) { //若没有发生交换，说明数据已经有序 break; } }}void main() { int i; int a[] = { 1,3,2,8,5,7}; int len = LEN(a); PRintf("Before sort:"); for (i = 0; i < len; i++) { printf("%d/t", a[i]); } printf("/n"); bubble_sort1(a, len); //bubble_sort2(a, len); printf("After sort:"); for (i = 0; i < len; i++) { printf("%d/t", a[i]); } printf("/n");}

　　　运行结果如下：　　　冒泡排序运行结果