冒泡排序改进算法

冒泡排序属于简单的排序,这里不作详细介绍。只写下改进思路。以前学习的时候从未想过有改进的想法,突然听到有改进版,首先反思的是自己当时只是盲目的学习,没有深入思考。
冒泡排序

0X001 冒泡排序实现

void BubbleSort_1(int a[], int size)  
{  
    for (int i = 0; i < size -1; i++)  
    {  
        for (int j = size - 1; j > i ; j--)  
        {  
            if (a[j-1] > a[j])  
            {  
                int temp = a[j-1];  
                a[j-1] = a[j];  
                a[j] = temp;  
            }  
        }  
    }  
}  

0X002 第一步优化
如果在一次循环中,数据没发生交换,那么是不是代表数组已经全部有序,可以退出循环,所以这里做一个标记,来判断数组是否有序

void BubbleSort_2(int a[], int size)  
{  
    bool bSwaped = true;  
    for (int i = 0; i < size -1; i++)  
    {  
        // 每次先重置为false  
        bSwaped = false;  
        for (int j = size - 1; j > i ; j--)  
        {  
            if (a[j-1] > a[j])  
            {  
                int temp = a[j-1];  
                a[j-1] = a[j];  
                a[j] = temp;  
                bSwaped = true;  //转换标记
            }  
        }  
        // 如果上一次扫描没有发生交换,则说明数组已经全部有序,退出循环  
        if (!bSwaped)  
        break;  
    }  
}  

0X003 第二步优化
记录每一次元素交换的位置,当元素交换的位置在第0个元素时,则排序结束。

void BubbleSort_3(int a[],int size)
{
  int i = size - 1;

   int lastChange = 0;
   int j;

  while(i > 0)

   {
     lastChange = 0;
     for (j = 0; j < i; j++)
     {
       if (a[j] > a[j+1])
       {
         swap(a[j], a[j+1]);
         lastChange = j;
       }
     }
   i = lastChange;
   }

}
添加新评论