冒泡排序

冒泡排序属于几种排序算法里面的最简单的一种，不需要什么高深的思维，就可以很快理解。

冒泡排序实际上就是把相邻的数相互比较，把大的放右边（或者左边，这取决于你想顺序排还是倒序排）。如果把大的放右边，那么第一轮遍历之后，就会把这组数据中最大的放到最后边。

此时，最后一个已经是固定的了，依次把前面的按照这样的套路排序下去就行了。

下面这个动画可能会更直观地帮助你理解：

代码实现如下：

C:

#include <stdio.h>
void sort(int arr[])
{
    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]) - 1; i++)
    {
        for(int j = 0; j < sizeof(arr)/sizeof(arr[0]) - 1 - i; j++)
        {
            int temp = 0;
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Java:

public static void sort(int arr[]){
    for( int i = 0 ; i < arr.length - 1 ; i++ ){
        for(int j = 0;j < arr.length - 1 - i ; j++){
            int temp = 0;
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Python:

def sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

我们看到双层循环，就不难推出这个算法的时间复杂度为$O_{(n^2)}$，且为稳定排序。

其实通过我们上面的动图发现，当排到第4轮的时候，实际上整个列表就已经是有序的了，那么接下来的几轮，就是在浪费时间和资源。那么既然如此，有没有优化的方案呢？

当然是有的。

冒泡排序优化版：鸡尾酒排序

我们所设想的，应该是这样：

这个思路也很好实现。只需要设一个变量用来做标记，当某一次遍历的时候，一个元素都没有替换，那么就可以视为已经有序，后面的遍历就全省了。

代码实现如下：

C:

#include <stdio.h>
void swap(int a[], b, c)//设置交换数据的函数
{
    int temp = 0;
    if (b < c)
    {
        if (a[b] > a[c])
        {
            temp = a[b];
            a[b] = a[c];
            a[c] = temp;
        }
    }
}

void cocatailSort(int a[])
{
    int length = sizeof(a)/sizeof(a[0]);
    int flag1 = 1, flag2 = 1;
    for (int i = 0, i < length / 2, i++)
    {
        flag1 = 1;
        flag2 = 1;
        for(int j=i;j<length-i-1;j++)
        {
            if(array[j] > array[j+1]) { 
            swap(array, j, j+1) ; 
            flag1 = false ; //若已交换则更改变量
        }
        for(int j=length-i-1;j>i;j--)
        { 
            if(array[j] < array[j-1])
            { 
                 swap(array, j-1, j) ; 
                 flag2 = false ; //若已交换则更改变量
            } 
        } 
        if(flag1 && flag2)
        { //来回一趟都没有交换则跳出
            break ; 
        }
}

Java:

public static void swap(int[] a, int b, int c) { //交换数据的函数
    int temp = 0 ; 
    if(b < c) { 
      if(a[b] > a[c]) { 
        temp = a[b] ; 
        a[b] = a[c] ; 
        a[c] = temp ;  
      } 
    } 
  } 

public static void cocatailSortFlag(int[] array) { 
    int length = array.length ; 
    boolean flag1,flag2 = true ; 
    //来回循环length/2次 
    for(int i=0;i<length/2;i++) { 
      flag1 = true ; //初始化标记变量
      flag2 = true ; 
      for(int j=i;j<length-i-1;j++) { 
        if(array[j] > array[j+1]) { 
          swap(array, j, j+1) ; 
          flag1 = false ; //若已交换则更改变量
        } 
      } 
      for(int j=length-i-1;j>i;j--) { 
        if(array[j] < array[j-1]) { 
          swap(array, j-1, j) ; 
          flag2 = false ; //若已交换则更改变量
        } 
      } 
      if(flag1 && flag2) { //来回一趟都没有交换则跳出
        break ; 
      } 
    } 
  } 

Python:

def sort(arr):
    flag1, flag2 = True
    #来回循环len/2次
    for i in range(len(arr) - 2):
        flag1, flag2 = True
        for j in range(i, len(arr) - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag1 = False
        for j in range(len(arr) - i - 1, i, -1):
            if arr[j] < arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag2 = False
        if flag1 and flag2:
            break