排序算法 -1 ：冒泡排序

首选了解一下我们需要了解的10大排序算法

image

接下来我们依次学习每一个排序算法

• 冒泡排序（Bubble Sort）

1、概念

冒泡排序又称为泡式排序 是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。(维基百科)

2、运行过程

1、比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。
3、针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。
4、持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。
如图：

image

代码如下：

java:

  public void sort(int[] array){
        for (int end = array.length - 1; end > 0 ; end--) {
            for (int begin = 1; begin <= end; begin++) {
                if (array[begin] < array[begin -1]){
                    int tmp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin-1] = tmp;
                }
            }
        }
    }

object-c:

-(NSArray *)sort:(NSArray *)array{
    if (array.count <= 1) {
        return array;
    }
    NSMutableArray *sortedArray = [array mutableCopy];
    for (int i = 0; i < sortedArray.count-1; i++) {
           for (int j = 0; j< sortedArray.count-1-i; j++) {
               if ([sortedArray[j] integerValue] > [sortedArray[j+1] integerValue]) {
                   [sortedArray exchangeObjectAtIndex:j withObjectAtIndex:j+1];
               }
           }
       }
    return [sortedArray copy];
}

3、改进

• 1、改进方法 增加标志变量

java:

    public void sort(int[] array){
        for (int end = array.length - 1; end > 0 ; end--) {
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {
                if (array[begin] < array[begin -1]){
                    int tmp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin-1] = tmp;
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }

object-c:

-(NSArray *)sort:(NSArray *)array{
    if (array.count <= 1) {
        return array;
    }
    NSMutableArray *sortedArray = [array mutableCopy];
    for (int i = 0; i < sortedArray.count-1; i++) {
           BOOL exchanged = NO;
           for (int j = 0; j< sortedArray.count-1-i; j++) {
               if ([sortedArray[j] integerValue] > [sortedArray[j+1] integerValue]) {
                   [sortedArray exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                   exchanged = YES;
               }
           }
           if (!exchanged) {
               break;
           }
       }
    return [sortedArray copy];
}

4、改进原因

1）时间复杂度

在设置标志变量之后：

当原始序列“正序”排列时，冒泡排序总的比较次数为n-1，移动次数为0，也就是说冒泡排序在最好情况下的时间复杂度为O(n)；

当原始序列“逆序”排序时，冒泡排序总的比较次数为n(n-1)/2，移动次数为3n(n-1)/2次，所以冒泡排序在最坏情况下的时间复杂度为O(n^2)；

当原始序列杂乱无序时，冒泡排序的平均时间复杂度为O(n^2)。

（2）空间复杂度

冒泡排序排序过程中需要一个临时变量进行两两交换，所需要的额外空间为1，因此空间复杂度为O(1)。

（3）稳定性

冒泡排序在排序过程中，元素两两交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

参考：小码哥《恋上数据结构与算法第二季》