白话经典算法系列笔记一冒泡排序

       一直以来都想好好补补算法的东西，正好看到IT面试论坛中的白话经典算法系列，觉得将以前的一些算法再次熟悉下似乎不错。所以就从它开始把。

原始文章地址：

http://www.itmian4.com/forum.php?mod=viewthread&tid=4395&extra=page%3D1%26filter%3Dtypeid%26typeid%3D128%26typeid%3D128

我实现及注释代码：

#include <iostream>
using namespace std;
void swap(int &a,int &b)
{
    int tmp ;
    tmp =a;
    a = b;
    b = tmp;
}
//基础版冒泡排序
void BubbleSort1(int arr[],int n)
{
    //要沉n-1个数据才能完成排序
    for(int i=0; i<n;i++)
    {
        //每一次数据排序时，排序数的索引（指比较量）为1-n-i
        //(排完一个后之后索引就上升一个，每次排序最大的数已经沉底了）
        for(int j=1; j<n-i;j++)
        {
            //拿前一个数与待比较的后一个数进行比较
            if(arr[j-1]>arr[j])
            {
                //前一个数比较大，请到后面排队
                swap(arr[j-1],arr[j]);
            }
        }
    }
}
//设置标志位版冒泡排序
void BubbleSort2(int arr[],int n)
{
    bool flag=true;            //是否还有要排序的,咱先假设是有的
    int k=n;
    //不是有嘛，有事情做了
    while(flag)
    {
        //来个数学上的举反例法证明假设成立
        flag=false;
        for(int j=1; j<k;j++)
        {
            //拿前一个数与待比较的后一个数进行比较
            if(arr[j-1]>arr[j])
            {
                //前一个数比较大，请到后面排队
                swap(arr[j-1],arr[j]);
                flag = true;            //找到反例，说明假设不成立
            }
        }
        k--;
    }
}
/*
再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，
那么在第一趟遍历后，最后发生交换的位置必定小于10，
且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。
*/
//冒泡排序3
void BubbleSort3(int a[], int n)
{
        int j, k;
        int flag;                   //flag标记还要比较到哪里
        flag = n;
        while (flag > 0)            //flag=0时说明换完了
        {
            k = flag;
            //最后换的地方在那计数开始
            flag = 0;
            for (j = 1; j < k; j++)
            {
                if (a[j - 1] > a[j])
                {
                    swap(a[j - 1], a[j]);
                    flag = j;           //不断更新最大换的位置
                }
            }
        }
}
//打印数组
void PrintArray(int arr[],int n)
{
    for(int i=0;i<n;i++)
    {
       std::cout<<arr[i]<<"  ";
    }
    std::cout<<endl;
}
int main()
{

    int arr1[5]={3,2,9,10,20};
    std::cout<<"Before bubble sort1:\n";
    PrintArray(arr1,5);
    BubbleSort1(arr1,5);
    std::cout<<"After bubble sort1:\n";
    PrintArray(arr1,5);
    std::cout<<endl<<endl;

    int arr2[5]={3,2,9,10,20};
    std::cout<<"Before bubble sort2:\n";
    PrintArray(arr2,5);
    BubbleSort2(arr2,5);
    std::cout<<"After bubble sort2:\n";
    PrintArray(arr2,5);
    std::cout<<endl<<endl;

    int arr3[5]={3,2,9,10,20};
    std::cout<<"Before bubble sort3:\n";
    PrintArray(arr3,5);
    BubbleSort3(arr3,5);
    std::cout<<"After bubble sort3:\n";
    PrintArray(arr3,5);
    return 0;
}