|
这篇文章是对上一篇文章中的冒泡排序进行优化 先来说说，冒泡排序哪些地方需要优化： 根据上一篇文章的内容，可以知道冒泡排序的核心是两两对比进行交换。如果有一个无序数列（2，1，3，4，5，6，7，8，9，10） 按照上一篇文章的代码，从第一次循环交换后的操作，可以说都是没必要的。所以，这些操作就是我们需要优化的地方。 那么如何优化？ 通过观察可以看到，造成没必要的操作主要原因是后面8个数的顺序都已经是有序。所以，我们可以通过设置一个标记变量，标记数列中的数是否在循环结束前就已经排好序 代码： #include void swap(int *a, int *b);int main(){ int array[10] = {2, 1, 3, 4, 5, 6, 7, 8, 9, 10}; int i, j; int flag = 1; //设置标记变量 for (i = 0; i < 10 && flag; i++) { flag = 0; //只要flag在下一次外循环条件检测的时候值为0，就说明已经排好序，不用继续循环 for (j = 9; j > i; j--) { if (array[j] < array[j-1]) { swap(&array[j], &array[j-1]); flag = 1; //如果有交换，就将标记变量赋1 } } } for (i = 0; i < 10; i++) { printf('%d\n', array[i]); } return 0;}void swap(int *a, int *b){ int temp; temp = *a; *a = *b; *b = temp;} 根据优化过的代码，当最好情况的时候，冒泡排序的时间复杂度是O(n)
|
