冒泡排序的思想很简单,就是以此比较相邻的元素大小,将小的前移,大的后移,就像水中的气泡一样,最小的元素经过几次移动,会最终浮到水面上。
举例分析说明一下,如下数据:
2 7 4 6 9 1 首先比较最后两个数字,发现1比9小,于是前移
2 7 4 6 1 9 然后比较6和1
2 7 4 1 6 9 继续前移,然后是4和1
2 7 1 4 6 9 7和1比较
2 1 7 4 6 9 2和1
1 2 7 4 6 9 至此,第一趟冒泡过程完成,最小的元素1被移到第一个,不再参与后面的排序过程。下一趟冒泡过程同理,比较6和9,以此类推,最终得到结果。
void bubblesort(int v[]){ for (int i=0; i<v.size(); i++){ int temp = 0; for(int j=v.size()-1; j>i; j--){ if (v[j] < v[j-1]){ temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } } }
若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为此, 在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序 结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。这样可以减少不必要的比较。
void bubble_sort(vector<int> &v){ bool exchange; for (int i=0; i<v.size(); i++){ int temp = 0; exchange = false; for(int j=v.size()-1; j>i; j--){ if (v[j] < v[j-1]){ temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; exchange = true; } } if (!exchange){ break; } } }