35｜冒泡排序：大数下沉，小数上浮

【思考题回答】 1、两种方式的区别就是两个数交换的条件不同，从大到小排序是前面的数比后面的小的时候交换，而从小到大排序是前面的数比后面的数大的时候交换 2、进一步优化冒泡排序算法的方法： 记录最后一次交换的索引，作为下一次冒泡的比较次数。 这样操作可以让某个数组中后面“大部分”已经有序的情况下，无需再比较额外的次数。 基于该篇文章给出来的代码，修改如下 //冒泡排序（从小到大） template<typename T> void BubbleSort(T myarray[], int length) { if (length <= 1) //不超过1个元素的数组，没必要排序 return; int num = length - 1; //外层循环只控制排序的趟数 while (true) { int last = 0; //最后一次交换索引问题 //内层循环控制元素的大小比较和交换位置 for (int j = 0; j < num; ++j) //每趟比较的次数都会减少 { if (myarray[j] > myarray[j + 1]) //前面的数据如果比后面的数据大 { //交换元素位置 T temp = myarray[j + 1]; myarray[j + 1] = myarray[j]; myarray[j] = temp; last = j; // 发生最后交换的索引 } } //end for j num = last; //最后交换的索引当做下次遍历时比较次数 if(num == 0) { // 没有发生交换，退出循环 break; } } return; }