冒泡排序和选择排序

冒泡排序(Bubble sort)和选择排序(Selection sort)

　　初看冒泡排序和选择排序不禁会问它们有什么区别? 的确, 它们的基本思想是一样的. 都是通过一轮的循环找到所要排序数中的最值(最大值或最小值), 然后将最值置于顶端. 它们的区别主要体现在对其他数(非最值)的处理上.

　　冒泡排序: 通过相邻的两个数的比较, 根据需要决定是否将两个数互换位置, 然后将比较往前(或往后)推进. 例如, 要求从小到大排序. 通过将两个数比较, 将较大的数置换到右边. 如此不断循环将得到最值.

　　选择排序: 和冒泡排序不同, 选择排序使用标记最值所在位置的方式, 查找最值过程中不移动数位置, 只是在最后将最值置换到顶端.

　　冒泡排序代码:

 1 void bubblesort(int arrayVal[],int length)
 2 {
 3     int i,j;
 4     int temp;
 5 
 6     for(i=0;i<length-1;i++)
 7         for(j=i+1;j<length;j++)
 8             if(arrayVal[i]>arrayVal[j])
 9             {
10                 //置换位置
11                 temp=arrayVal[i];
12                 arrayVal[i]=arrayVal[j];
13                 arrayVal[j]=temp;
14             }
15 }

　　选择排序代码:

 1 void selectionsort(int arrayVal[],int length)
 2 {
 3     int i,j,max;
 4     int temp;
 5 
 6     for(j=length;j>1;j--)
 7     {
 8         max=0;//标记最值位置
 9         for(i=1;i<j;i++)
10             if(arrayVal[i]>arrayVal[max])
11                 max=i;
12             if(max!=j-1)
13             {
14                 temp=arrayVal[max];
15                 arrayVal[max]=arrayVal[j-1];
16                 arrayVal[j-1]=temp;    
17             }
18     }
19 
20 }

　　从上两段代码可以看出,它们处于同一个数量级，即时间复杂度是相同的,都用了两层循环,为O(n^2)(n:排序个数); 但是内层循环中，冒泡排序的互换位置的操作从概率上讲要明显多于选择排序. 整个排序算法，选择排序换位操作为O(n)，二冒泡排序为O(n^2/2). 所以综合来讲选择排序的时间效率要高于冒泡排序.

冒泡排序和选择排序

推荐阅读