本文共 1444 字,大约阅读时间需要 4 分钟。
起泡排序,别名“冒泡排序”,该算法的核心思想是将无序表中的所有记录,通过两两比较关键字,得出升序序列或者降序序列。
例如,对无序表{49,38,65,97,76,13,27,49}进行升序排序的具体实现过程如图 1 所示:
图 1 第一次起泡
如图 1 所示是对无序表的第一次起泡排序,最终将无序表中的最大值 97 找到并存储在表的最后一个位置。具体实现过程为:
由于 97 已经判断为最大值,所以第二次冒泡排序时就需要找出除 97 之外的无序表中的最大值,比较过程和第一次完全相同。
经过第二次冒泡,最终找到了除 97 之外的又一个最大值 76,比较过程完全一样,这里不再描述。
通过一趟趟的比较,一个个的“最大值”被找到并移动到相应位置,直到检测到表中数据已经有序,或者比较次数等同于表中含有记录的个数,排序结束,这就是起泡排序。
#include//交换 a 和 b 的位置的函数void swap(int *a, int *b);int main(){ int array[8] = {49,38,65,97,76,13,27,49}; int i, j; int key; //有多少记录,就需要多少次冒泡,当比较过程,所有记录都按照升序排列时,排序结束 for (i = 0; i < 8; i++){ key=0;//每次开始冒泡前,初始化 key 值为 0 //每次起泡从下标为 0 开始,到 8-i 结束 for (j = 0; j+1<8-i; j++){ if (array[j] > array[j+1]){ key=1; swap(&array[j], &array[j+1]); } } //如果 key 值为 0,表明表中记录排序完成 if (key==0) { break; } } for (i = 0; i < 8; i++){ printf("%d ", array[i]); } return 0;}void swap(int *a, int *b){ int temp; temp = *a; *a = *b; *b = temp;}
运行结果为:
13 27 38 49 49 65 76 97
使用起泡排序算法,其时间复杂度同实际表中数据的无序程度有关。
若表中记录本身为正序存放,则整个排序过程只需进行 n-1(n 为表中记录的个数)次比较,且不需要移动记录;
若表中记录为逆序存放(最坏的情况),则需要 n-1趟排序,进行 n(n-1)/2 次比较和数据的移动。所以该算法的时间复杂度为O(n2)。
转载地址:http://molxi.baihongyu.com/