起泡排序算法

观察:
在有序序列中, 任意一对相邻元素顺序,
在无序序列中, 至少一对相邻元素逆序.
而冒泡法的基本思想就是消除紧邻的逆序元素,方法就是交换.
如果整趟扫描都没有交换,则排序完成.


Codebegin

/*
起泡排序 观察:
在有序序列中, 任意一对相邻元素顺序,
在无序序列中, 至少一对相邻元素逆序.
而冒泡法的基本思想就是消除紧邻的逆序元素,方法就是交换.
方法:依次比较每一对相邻元素,如有必要交换之
如果整趟扫描都没有交换,则排序完成;否则,再做一趟扫描交换.
*/

#include "stdafx.h"
#include <stdio.h>

void swap(int *a, int *b)
{
   int t;
   t=*a;
   *a=*b;
   *b=t;
}

void bubble00(int a[],int N)/*基本算法*/
{
   int i,j,t;
   for(i=0;i<N-1;i++)/* 外層循環只是保證N-1趟處理, 而且是最多N-1趟*/
   {
      for(j=1;j<=N-1-i;j++)/*j<=N-1-i*/
      { /*每趟结束都会有一个值放到正确位置,所以j的右界是不断缩小的 */
         if(a[j-1]>a[j])
         { t=a[j-1]; a[j-1]=a[j]; a[j]=t; }
      }
   }
}

/*
不变性:经过k轮扫描交换后,最大的k个元素必然就位
单调性:经过k轮扫描交换后,问题的规模缩减至n-k
正确性:经至多n轮扫描后,算法必然终止,且给出正确解答
*/
void bubble01(int a[],int N)
{
   int sorted;
   int i;
   do{
      sorted=1;
      for(i=1;i<N;i++){
         if(a[i-1]>a[i]){
            swap(&a[i-1],&a[i]);
            sorted=0;
         }
      }
      N-=1;
   }while(0==sorted);
}

void bubble02(int a[],int n)
{
   int i, j;
   int flag;/* 改进 */
   for(i = 0; i < n-1; ++i)/* 此处的++i 和 i++ 没有区别 */
   {
      flag = 1;/* 改进 */
      for(j = 0; j < n-i-1; ++j)
      {
         if(a[j] > a[j+1]) /* 升序排列 */
         {
            a[j] = a[j+1] ^ a[j];
            a[j+1] = a[j+1] ^ a[j];
            a[j] = a[j+1] ^ a[j];
            flag = 0;/* 改进 */
         }
      }
      if(1 == flag)/* 改进 : 此次遍历没有一次交换,说明顺序已经排好 */
         break;
    }
}

void bubble03(int a[],int N)/*交換狀態*/
{
   int j,t;
   int flag=1;
   int k=N-1;
   while(flag==1)/*當不再發生交換，說明已經排好序*/
   {
      flag=0;
      for(j=1;j<=k;j++)
      {
         if(a[j-1]>a[j])
         {
            t=a[j-1];
            a[j-1]=a[j];
            a[j]=t;
            flag=1;
         }
      }
      k-=1;
   }
}

void bubble04(int a[], int n)
{
   int j, k;
   int right;

   right = n;
   while (right > 0)
   {
      k = right;
      right = 0;
      for (j = 1; j < k; j++)
         if (a[j - 1] > a[j])
         {
            swap(&a[j - 1], &a[j]);
            right = j;
         }
   }
}

void bubble05(int a[],int N)/*記錄現場*/
{
   int j,m,t;
   int bound=N-1;
   while(bound)
   {
      m=0;
      for(j=1;j<=bound;j++)
      {
         if(a[j-1]>a[j])
         {
            t=a[j-1];
            a[j-1]=a[j];
            a[j]=t;
            m=j-1;
         }
      }
      bound=m;
   }
}

void bubble06(int a[],int N)/*雙向冒泡*/
{
   int lbound=0;
   int rbound=N-1;
   int min,max,j,t;
   while(lbound<rbound)
   {
      min=0;
      max=0;
      for(j=lbound;j<rbound;j++)/*j+1<=rbound*/
      {
         if(a[j]>a[j+1])
         {
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
            max=j;
         }
      }
      if(max==0)/*值沒變，說明沒有發生交換，數組已經有序，直接退出循環*/
         break;
      rbound=max;
      for(j=rbound;j>lbound;j--)/*j-1>=lbound*/
      {
         if(a[j]<a[j-1])
         {
            t=a[j];
            a[j]=a[j-1];
            a[j-1]=t;
            min=j;
         }
      }
      if(min==0)/*值沒變，說明沒有發生交換，數組已經有序，直接退出循環*/
         break;
      lbound=min;
   }
}
int main(int argc, char* argv[])
{
   int i;
   int N;
   int a[10];
   if(NULL==freopen("bubblei.txt","r",stdin)){
      printf("Failed to open file\n");
      return -1;
   }
   scanf("%d",&N);
   for(i=0;i<=N-1;i++)
      scanf("%d",&a[i]);

   bubble01(a,N);

   for(i=0;i<=N-1;i++)
      printf("%d ",a[i]);
    return 0;
}

/*
10
8 100 50 22 15 6 1 1000 999 0
*/

Codeend