排序算法—冒泡排序

 1:  /**
 2:    * 基本的冒泡排序
 3:    * @param int* num 排序数组
 4:    * @param int length 数组大小
 5:    * @return int 排序成功与否
 6:    */
 7:  int BubbleSort(int *num, int length)
 8:  {
 9:     int i,j;
10:     if(length < 2)
11:        return 0;
12:     for(i = 0; i < n; i++)           //外层循环控制排序的趟数
13:     {
14:        for(j = 0; j < n-1-i; j++)    //内层循环控制排序要交换的数的范围
15:        {
16:           if(num[j] > num[j+1])
17:              swap(num[j],num[j+1])   //两两相邻的数比较大小 
18:        }
19:     }
20:     return 0;
21:  }
22:  算法分析:
23:    时间复杂度:最优的情况,所有的数都是有序的,那么内层循环就不用交换数了,
24:                      只进行外层的循环,复杂度是O(n);
25:             最差的情况,所有的数都是倒序的,那么两层循环都要进行,复杂度是O(n^2);
26:             平均时间复杂度是O(n^2);
27:      空间复杂度:一维数组 O(1);

该思路也可以逆序进行,伪代码如下:

 1:  for(i from n-1 downto 0)
 2:  {
 3:     for(j from n-1 downto n-1-i)
 4:     {
 5:        cmp(num[j],num[j-1])
 6:     }
 7:  }
 8:  
 9:  // 其他类似的写法还有:
10:  for(i = n-1; i > 0; i--)
11:  {
12:     for(j = 0; j > i; j++)
13:     {
14:        cmp(j,j+1)
15:     }
16:  }
17:  
18:  // 交换排序
19:  for(i = 0; i < n-1; i++)
20:  {
21:     for(j = i+1; j < n; j++)
22:     {
23:        cmp(num[i],num[j])   //此时比较的不是相邻的两个元素了
24:     }
25:  }

上述的排序是两两相邻的数进行比较,更符合冒泡的形态.但实际上要比较的也不一定就是相邻的数.

 1:    /**
 2:    * 改进的冒泡排序一
 3:    * @param int* num 排序数组
 4:    * @param int length 数组大小
 5:    * @return int 排序成功与否
 6:    */
 7:   
 8:  //逆序版 但还是不同的较少了交换的次数 而且类似选择排序
 9:  int BubbleSort(int *num, int length)
10:  {
11:     int i,j,max;
12:     if(length < 2)
13:        return 0;
14:     for(i = n-1; i > 0; i--)           //外层循环控制排序的趟数
15:     {
16:        for(j = 1,max = 0; j < i; j++)  //从0～j左边部分选出最大的数
17:        {
18:           if(num[max] < num[j])
19:             max = j;
20:        }
21:        if(num[i] < num[max])
22:          swap(num[i],num[max]);
23:     }
24:     return 0;
25:  }

可以设置一个标志,如果一趟过程中发成了交换,则为true,反之则未false,如果有一趟没有发生交换就说明排序已经完成

 1:  /**
 2:    * 改进的冒泡排序二
 3:    * @param int* num 排序数组
 4:    * @param int length 数组大小
 5:    * @return int 排序成功与否
 6:    */
 7:  int BubbleSort(int *num, int length)
 8:  {
 9:     int i,j,flag;
10:     if(length < 2)
11:        return 0;
12:     for(i = 0; i < n-1; i++)       //外层循环控制排序的趟数
13:     {
14:        flag = 0;
15:        for(j = n-1; j > i; i++)    //内层循环控制依次排序的完成
16:        {
17:           if(num[j] > num[j-1])
18:           { 
19:             swap(num[i],num[j])  
20:             flag = 1;
21:           }
22:        }
23:        if(flag == 0)               //终止排序
24:          break;     
25:     }
26:        return 0;
27:  }  
28:  如果100个数,就前10个数是乱序的,后面的数是有序的.可以通过设置标志记录交换时的位置,下一次循环到此处即可.
29:  int BubbleSort(int *num, int length)
30:  {
31:     int i,j,lastchange;            //lastchange记录上次交换的位置
32:     if(length < 2)
33:        return 0;
34:     i = n;
35:     while(i > 0)
36:     {
37:       lastchange = 0;
38:       for(j = 0; j < i; j++)
39:       {
40:          if(num[j] > num[j+1])
41:          {
42:             swap(num[j],num[j+1])
43:             lastchagne = j;
44:          } //if
45:       }// for
46:       i = lastchange;
47:     }
48:        return 0;
49:  }  

双向冒泡进一步提高效率,又称鸡尾酒排序.

 1:   /**
 2:  * 基本的冒泡排序
 3:  * @param int* num 排序数组
 4:  * @param int length 数组大小
 5:  * @return int 排序成功与否
 6:  */
 7:  int BubbleSort(int *num, int length)
 8:  {
 9:     int i,j,left,right,l,r;
10:     left = 0;i = 0;
11:     right = length-1;
12:     
13:     //双向冒泡
14:     while(left < right)
15:     {
16:     //必须要给l和r赋值,否则若数组一开始就是有序,则right = r时,r未赋值会报错.
17:       l = left + 1;
18:       r = right - 1;
19:       
20:       // 第一次循环将最大的值放到末尾
21:       for(j = left; j < right; j++)
22:       {
23:          if(a[j] > a[j+1])
24:          { 
25:             swap(a[j],a[j+1]);
26:             r = j;
27:          }
28:       }
29:       right = r;  // 这里好好想想,r 不一定是最后一个数喔!
30:      
31:      //第二次循环将最小的值放到开头
32:       for(j = right; j > left; j--)
33:       { 
34:         if(a[j] < a[j-1])
35:         {
36:            swap(a[j],a[j-1]);
37:            l = j;
38:         }
39:       }
40:       left = l;
41:       
42:       //测试结果
43:       /*
44:        printf("第%d次排序结果:",i+1);
45:        i++;
46:        for(j = 0; j < n; j++)
47:         printf("%d\t",a[j]);
48:       */
49:     }
50:  }
51: