首页 > 代码库 > 冒泡的实现即优化
冒泡的实现即优化
冒泡排序:
设数组长为N。以升序为例。
-
1 比较相邻的2个前后的数据,如果前面数据大于后面的数据,则2个数据交换
-
2 这样对数组的第0个数据到第N-1个数据进行遍历,则最大的数据会沉到数组的第N-1个位置。
-
3 N = N-1,如果N != 0 就执行第二步。
1 void Bubble_Sort( int a[], int N ) 2 { 3 int i, j; 4 5 for( i = 0; i < N; ++i ) 6 for( j = 1; j < N-i; ++j ) 7 if( a[j-1] > a[j] ) 8 swap( a[j-1], a[j] ); 9 }
下面对其进行优化:
设置一个标志,如果某一趟遍历发生了交换则为true,如果没发生交换则为false。 如果某一趟遍历没发生交换,则表明已经排好序了。
1 void Bubble_Sort( int a[], int N ) 2 { 3 bool flag = true; 4 int i; 5 int k = n; 6 while( flag ) 7 { 8 flag = false; 9 for( i = 1; i < k; ++i ) 10 if( a[i-1] < a[i] ) 11 { 12 swap( a[i-1], a[i] ); 13 flag = true; 14 } 15 --k; 16 } 17 }
再进行进一步优化:
如果100个数据,前10个无序,后90个有序且都大于前10个数据。那么在第一趟遍历时最后发生交换的位置必定小于10。切这个位置之后的数据必定已经有序了,记录下这个位置,则第二次遍历时从数组头部位置遍历到该位置即可。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。