排序算法-冒泡排序（改进）

冒泡排序（改进）

冒泡排序的排序思路是：

• 通过无序区的相邻元素的比较和位置的交换，使最大的元素往上移动
• 每一轮排序选出无序区的最大的元素，加入有序区中
• 不止可以得到升序排序，稍微改变下交换逻辑也可以得到降序排序

冒泡排序算法参考我的另一篇博客：链接

冒泡排序存在的问题：

假如我们运气好，用了1轮就已经将整个序列排序好了，整个数列已然是有序的了。可是我们的排序算法仍然“兢兢业业”地继续执行第2轮、第3轮、直至n-1轮，这就很没必要。也就是说如果序列已经有序，每一轮排序还是会继续比较相邻的元素，这就相当于做了一些没用的操作。

冒泡排序改进思路：

这种情况下，如果我们能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。因此我们可以用一个标志变量来标准序列是否有序，当一次冒泡过程中发现没有交换操作时，表明序列已经排好序了，便终止冒泡操作。用一个标志变量 标记在比较过程中是否发生了数据交换。

改进后的冒泡排序的代码实现：

#include <stdio.h>
/*
冒泡排序的排序思路是：
通过无序区的相邻元素的比较和位置的交换，使最大的元素往上移动
每一轮排序选出无序区的最大的元素，加入有序区中 
*/
void bubble_sort(int value[],int n)
{
	//n-1轮排序 （排序n-1轮剩下的那个数自然是最小的） 
    for(int i=0; i<n-1; i++)
    {
    	//使用标志变量判断序列是否有序 
    	bool isSorted = true;
    	
    	//每一轮排序选出无序区的最大的元素，加入有序区中
    	//循环终止条件是 j<n-i-1  
    	//n代表数组总共有n个数，i表示已经有i个排序好了
		//因为每次是和后面的元素比较，所以要 -1 （防止数组越界） 
        for(int j=0; j<n-i-1; j++)
        {
        	//每一次和后一个元素，进行比较，较大的后移 
            if( value[j] > value[j+1])
            {
            	//交换两个元素的值 
            	int temp = value[j];
            	value[j] = value[j+1];
                value[j+1] = temp;
                
                //若是发送交换元素，说明序列还是无序 
                isSorted = false;
            }
        }
        //如果序列已经有序结束循环 
        if(isSorted){
            break;
        }
    }
}
int main()
{
    int value[] = {8,3,6,2,4,5,7,1,9,0};
    
    printf("排序前的数据为：\n");
    for(int i=0; i<10;i++)
        printf("%d  ",value[i]);
    printf("\n\n");
    
    bubble_sort(value,10);
    
    printf("排序后的结果为：\n");
    for(int i=0; i<10;i++)
        printf("%d  ",value[i]);
    printf("\n");
    
    return 0;
}

运行结果：