首页 > 算法 > 算法系列之三 冒泡排序

算法系列之三 冒泡排序

冒泡排序是从待排序的序列中,比较相邻的前后二个数据,如前面元素值大于后面元素值则交换位置,第1趟下来最大的元素就沉在数组的第n-1的位置,起到全部待排序的元素处理完

设数组为a[0...n-1]
1、初始时,数组全为无序区为a[0...n-1]。令i=0
2、比较相邻的前面两个元素,若前面元素大于后面元素,则交换位置,一趟下来,最大的元素就”沉”在了a[n-1]
3、i++重复第2步,起码到处理完i=n-1,排序完成

void BubbleSourt1(int a[], int n)
{
     int i, j;
     for (i = 0; i < n; i ++)
     {
          for (j = 0; j < n - 1 - i; j++)
          {
               if (a[j] > a[j + 1])
               {
                    swap(a[j], a[j+1]);
               }
          }
     }
}

冒泡排序可以优化,设置一个标记isSwapHappened,如果这一趟有发生交换,则为ture,否则为false.如果这一趟没有发生交换,则序列已经是有序的

void BubbleSourt2(int a[], int n)
{
     int i, j;
     bool isSwapHappened;
     for (i = 0; i < n; i ++)
     {
          isSwapHappened =  false;
          for (j = 0; j < n - 1 - i; j++)
          {
               if (a[j] > a[j + 1])
               {
                    swap(a[j], a[j+1]);
                    isSwapHappened = true;
               }
          }
          if (!isSwapHappened)
          {
               break;
          }
     }
}

另外还可以两向同时冒泡

void TwoWayBubbleSourt(int a[], int n)
{
     int i, low, high, isSwapHappend;
     low = 0;
     high = n - 1;

     while (low < high)
     {
          isSwapHappend = false;
          for (i = low; i < high; i++)
          {
               if (a[i] > a[i + 1])
               {
                    swap(a[i], a[i + 1]);
                    isSwapHappend = true;
               }
          }
          if (!isSwapHappend) 
          {
               break;
          }
          high--;
          isSwapHappend = false;
          for(i = high; i > low; i--)
          {
               if (a[i] < a[i - 1])
               {
                    swap(a[i], a[i - 1]);
                    isSwapHappend = true;
               }
          }
          if (!isSwapHappend) 
          {
               break;
          }
          low++;
     }
}

时间复杂度:
最好是一开始就有序的,只需要做n-1次判断,时间复杂度为O(n)
最差逆序的,需要做n(n-1)/2次比较,时间复杂度为O(n*n)
平均时间复杂度为O(n*n)

稳定性:
当相邻两个元素相等时,可以不交换,所以是稳定的

(转载本站文章请注明出处 www.helloitworks.com ,请勿用于任何商业用途)

分类: 算法 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.