1. 设需要对5个不同的记录关键字进行排序，则至少需要比较_____4________次，至多需要比较_____10________次。

做题时查了一下排序的时间复杂度，发现冒泡排序的最好时间复杂度是O(n),如下图

但平时在写冒泡排序算法时，完成没有体现出最好时间复杂度的情况。

代码如下（一般都是用双重for来实现，没有最好时间复杂度的体现）

void bubble_sort(int* arr, int sz) //数组传的指针,参数中还需传递一个数组大小

{

  int i = 0;

  //趟数

  for (i = 0; i < sz - 1; i++) //总共趟数只有n-1趟

   {

    int j = 0;

    for (j = 0; j < sz - 1 - i; j++) //每轮里面排的数要依次递减

      {

       if (arr[j] > arr[j + 1])

         {

          int temp = arr[j];

          arr[j] = arr[j + 1];

          arr[j + 1] = temp;

         }

      }

   }

}

原来是我们在写代码时，根本没有考虑最好的情况，即数组本身就有序。

那么如果需要数组本身是有序列的呢？

只要第一趟比较时，没有任何数据需要进行交换，就说明数组本身有序，不用再继续比较了。

所以对代码可以进行优化。

在代码中设立一个标志位,来提示我们排序是否已经排好

void bubble_sort(int* arr, int sz) //数组传递一定是指针

{

int i = 0;

//趟数

for (i = 0; i < sz - 1; i++)

{

int k = 1;

//k就是一个标志位，在第一趟中如果k变成0了，就说明顺序是需要程序来排序的

//如果k不变，还是等于1，则数据顺序本身就是好的，就直接break

for (int j = 0; j < sz - 1 - i; j++)

{

if (arr[j] > arr[j + 1])

{

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

k = 0;

}

}

if (k == 1)

{

break;

}

}

}

分享出来，希望大家都知道冒泡排序的最少比较次数是n-1; 哈哈，希望对大家有所帮助