冒泡算法及改进（属于交换排序）

本文主要是介绍冒泡算法及改进（属于交换排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

冒泡排序（Bubble Sort）是一种交换排序，快速排序也属于一种交换排序。冒泡排序的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

假设一共共有 n 个数，则会进行 (n-1)趟比较，由1，2......n-1这么多趟，第一趟进行 (n-1)次比较，.......第n-1趟进行1次比较，故有公式：第i趟 +  第i趟的比较次数 = n       时间复杂度为：O(n*n)

#define  MAXSIZE  10
typedef struct{int r[MAXSIZE+1];int length;
}SqList;

void swap(SqList *L,int i,int j){int temp = L->r[i];L->r[i] = L->r[j];L->r[j] = temp;
}

一共共有三种形式的排序：

第一种不是属于严格意义上的冒泡排序算法（不是相邻之间的交换）

void BubbleSort0(){int i,j;for(i=1;i<L->length;i++){for(j=i+1;j<=L->length;j++){if(L->r[i]>L->r[j]){swap(L,i,j);}}}
}

第二种是真正的冒泡排序算法（相邻之间的交换）

基本思路是：每次都是相邻之间的比较，将小的调到前头

void BubbleSort1(){int i,j;for(i=1;i<L->length;i++){for(j=1;j<=L->length-i;j++){if(L->r[ j ]>L->r[ j+1 ]){swap(L,j,j+1);}}}
}

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define SIZE 8
using namespace std;void bubble_sort(int a[], int n)
{int i, j, temp;for (j = 0; j < n - 1; j++)for (i = 0; i < n - 1 - j; i++){if(a[i] > a[i + 1]){temp = a[i];a[i] = a[i + 1];a[i + 1] = temp;}}
}int main()
{int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};int i;for (i = 0; i < SIZE; i++){printf("%d ", number[i]);}printf("\n");bubble_sort(number, SIZE);for (i = 0; i < SIZE; i++){printf("%d ", number[i]);}printf("\n");
}

第三种是对第二种的改进型，  isSwaped  true代表进行了交换操作，如果是false代表没有进行交换操作。

void BubbleSort2(){int i,j;bool  isSwaped = true;for(i=1;i<L->length;i++){for(j=1;j<=L->length-i;j++){isSwaped = false;if(L->r[ j ]>L->r[ j+1 ]){swap(L,j,j+1);isSwaped = true;}if(!isSwaped){break;}}}
}

这篇关于冒泡算法及改进（属于交换排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---