基本排序（一）：冒泡排序算法的三种基本实现及改进

排序算法

1. 最基本的冒泡排序算法的实现

以下助记码和图片来自维基百科，第三种不是严格意义上的冒泡（其不是相邻2个相互比较——选择排序）

  i∈[0,N-1)                //循环N-1遍
    j∈[0,N-1-i)            //每遍循环要处理的无序部分
      swap(j,j+1)          //两两排序（升序/降序）
  i∈[N-1,0)                //循环N-1遍
    j∈[N-1,N-i-1)            //每遍循环要处理的无序部分
      swap(j,j-1)          //两两排序（升序/降序）
  i∈[0,N-1)                //循环N-1遍
    j∈[i+1,N)            //每遍循环要处理的无序部分
      swap(i,j)          //两两排序（升序/降序）

#include <iostream>
#include <time.h>
using namespace std;
typedef int DATA_TYPE;
void swap(DATA_TYPE *x, DATA_TYPE *y)
{
    DATA_TYPE temp;
    temp = *y;
    *y = *x;
    *x = temp;
}
void bubble_sort1(DATA_TYPE  a[] , int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if ( a[j] > a[j+1])
            {
                swap(&a[j], &a[j+1]);
            }
        }
    }
}
void bubble_sort2(DATA_TYPE  a[] , int length)
{
    for (int i = length - 1; i > 0; i--)
    {
        for (int j = length - 1; j < length - 1 - i; j--)
        {
            if (a[j] < a[i-1])
            {
                swap(&a[j], &a[j-1]);
            }
        }
    }
}
void bubble_sort3(DATA_TYPE  a[] , int length)
{
    for(int i = 0; i < length - 1; i++)
    {
        for(int j = i; j <length; j++)
        {
            if (a[i] > a[j])
            {
                swap(&a[i], &a[j]);
            }
        }
    }
}
void print_array(DATA_TYPE *a, int length)
{
    for( int  i = 0; i < length; i++)
        cout<<a[i]<<"  ";
    cout << endl;
}
int main()
{
    srand( (unsigned)time(NULL) ); //随机种子
    DATA_TYPE a[10], b[10], c[10];
    for(int i = 0; i < 10; i++)//产生3个随机数组
    {
        a[i] = rand()%100;
        b[i] = rand()%100;
        c[i] = rand()%100;
    }
    int  length = sizeof(a) / sizeof(a[0]);
    cout<<"排序前的三个数组："<<endl;
    print_array(a,length);
    print_array(b,length);
    print_array(c,length);
    bubble_sort1(a, length);
    bubble_sort2(b, length);
    bubble_sort3(b, length);
    cout<<"排序后的三个数组："<<endl;
    print_array(a,length);
    print_array(b,length);
    print_array(c,length);
    system("pause");
    return 0;
}

2. 改进

在冒泡排序过程中，可以判断测试文件是否提前排好序，当其中一步中已经没有任何交换操作时，即文件已经排好序，就可以终止外部循环，提高效率。
提高排序效率的两种办法：
1. 更换高效算法
2. 缩短内部循环、减少不必要的比较和交换操作、根据数据的形式判断“比较和循环”的折衷次数

void bubble_sort(int a[], int N)
{
    int ret;//是否存在交换标志位
    for(int i = 0; i < N-1; i++)
    {
        ret = 0;
        for(int j = 0; j < N-1-i; j++)
        {
            if(a[j] > a[j+1])
            {
                swap(&a[j], &a[j+1]);
                ret = 1;
            }
        }
        if(!ret) //当没有任何交换时，ret保持为0，此时排序已完成，跳出外部循环，
            break;
    }
}