冒泡排序

稳定性

//冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

代码

普通代码

void BubbleSort(int *arr,int size)
{
    assert(arr&&size)//判断程序报错终止程序
    for(int i=0;i<size-1;i++)
    {
        for(int j=0;j<size-1-i;j++)
        {
            if(arr[j] > arr[j+1])
            {
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }
}

优化代码

void BubbleSort_Optimize_1(int *arr,int size)
{
    assert(arr&&size)//判断程序报错终止程序
    if(size=1)
    	return 0；//单一元素无需排序  
    bool flag=0;//定义标识符有序或无序
    for(int i=0;i<size-1;i++)
    {
        flag=1;//开始置于1
        for(int j=0;j<size-1-i;j++)
        {
            if(arr[j] > arr[j+1])
            {
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                flag =0;//交换完成置于0
            }
        }
        if(flag)
            break;//flag为1则已经有序
    }
}

void BubbleSort_Optimize_2(int *arr,int size)
{
    assert(arr&&size)//判断程序报错终止程序
    if(size=1)
    	return 0；//单一元素无需排序  
    bool flag=0;//定义标识符有序或无序
    int index=size-1;
    int max_index=0;//每一次找到无序区的上界
    for(int i=0;i<size-1;i++)
    {
        flag=1;//开始置于1
        max_index=0;
        for(int j=0;j<size-1-i;j++)
        {
            if(arr[j] > arr[j+1])
            {
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                flag =0;//交换完成置于0
                max_index=j;//注意不要在这里直接将index置为j
            }
        }
        if(flag)
            break;//flag为1则已经有序
    }
}