关于冒泡排序的简单优化

一说到冒泡排序,学过C语言的人都不会陌生.冒泡排序一个简单易懂的排序方法,使我们很好的掌握了两层for循环的用法.

一般的来说,对一个数组 int array[5] = [12, 2, 33, 25, 6];进行简单的排序,大家也都会想到冒泡排序.就会迅速的在编译器上敲下已经烂熟于心的冒泡排序代码:(如下:)

for (int i = 0 ; i < 5 - 1; i++) {

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

              if (array[j] > array[j + 1]) {

                      array[j] = array[j] ^ array[j + 1];

                      array[j + 1] = array[j] ^ array[j + 1];

                      array[j] = array[j] ^ array[j + 1];

             }

       }

}

上面的代码已经对冒泡排序进行了实现.另外在交换两个变量的时候,用^(异或)来交换两个变量的值,这种方法逼格很高.(推荐使用)

现在问题来了:假如说给你一个数组,数组里面的元素大部分已经是有序的,int array[5]={23, 32, 7, 4, 2}; 这样的话,我用上面的冒泡排序对数组array进行降序的话,还是会进行一一比较确定是否交换.那么我们该如何改进冒泡排序,使它知道后面有序的情况下,就不在继续for循环?

我们该如何知道数组array后面的是否有序?通过for循环,我们需要前后两个数一次比较,如果满足某个要求(降序或升序)这样的话,我们才能对这两个数进行交换.如果没有进行交换,则说明这两个数是有序的(这两个数按照降序或者升序排列), 如果循环到最后依旧没有交换过,则说明后面的数都是有序的.

因此,我们需要定义一个布尔类型的变量来记录,循环中相比较的两个数是否进行了交换.实现代码如下:

BOOL isNeedNext = YES;//定义BOOL值决定是否需要下一趟比较

for(inti =0; i < 5 -1&& isNeedNext; i++) {

        //每趟开始假定不需要下一趟比较

        isNeedNext =NO;

        for(intj =0; j < 5 -1- i ; j++) {

              if(array[j] > array[j + 1]) {

                 //如果发生交换,说明还是乱序,需要下一趟

                isNeedNext =YES;

              array[j] = array[j] ^ array[j + 1];

              array[j + 1] = array[j] ^ array[j + 1];

              array[j] = array[j] ^ array[j + 1];

            }

      }

}