冒泡排序:
首先引入两个概念:
顺序:如果两个数据的位置符合排序的需要,则称它们是顺序的。
逆序:如果两个数据的位置不符合排序需要,则称它们是逆序的。
冒泡排序基于这样一种简单的思路:从头到尾让每两个相邻的元素进行比较,顺序就保持位置不变,逆序就交换位置。可以预料,经过一轮比较,序列中具有“极值”的数据,将被挪至序列的末端。
假如序列中有n个数据,那么在最极端的情况下,只需要经过n−1轮的比较,则一定可以将所有的数据排序完毕。冒泡法排序的时间复杂度是O(n2)
最好:12345678
最坏(完全逆序): 87654321
总体思路:先把最大的往右边挤,把第二大往最右边第二位置挤…
逐对比较,并交换
代码:
void swap(int *m, int *n) { int temp; temp = *m; *m = *n; *n = temp; } int BubbleSort(int data[], int len) { //要冒泡len-1轮 int i, j; int temp = 0; int flag = 0; int count = 0; for (i = 0; i < len - 1; i++) { flag = 0; //要交换len-1-i次 for (j = 0; j < len - 1 - i; j++) { if (data[j] > data[j + 1]) { swap(&data[j], &data[j+1]); flag = 1; //表示交换过 count++; } } //表示未交换 if (flag == 0) break; } return count; }