选择排序and冒泡排序整理

选择排序思路(按升序排列):依次取数组未排好序的首个元素b[i]作为哨兵值,遍历数组,依次与哨兵值比较,若元素比哨兵值小b[j]

选择排序 思路(按升序排列):

依次取数组未排好序的首个元素b[i]作为哨兵值,遍历数组,依次与哨兵值比较,若元素比哨兵值小b[j]

选择排序时间复杂度:

以第二个for循环中的比较作为基本操作,

第一次比较n-1 次,第二次比较n-2 次,...直到比较1次,时间复杂度为:(1n-1)*(n-1)/2 n*(n-1)/2 O(n² )

具体代码如下:

void sort(int b[], int n) { int k,temp; for(int i 0; i

冒泡排序 思路(按升序排列):

从第一个元素开始,相邻两元素之间做比较,若前面元素比后面元素大,则交换,重复n-1 趟;每趟结束后,元素从末尾逐个从大到小排列.

冒泡排序时间复杂度:

以第二个for循环中的赋值作为基本操作,

最好情况:元素全都排列好,则只执行一次外部循环,时间复杂度为O(n-1)

最坏情况:元素按降序排列,则第一趟进行n-1次交换,第二趟进行n-2次交换,...最后一趟进行一次交换,共进行n-1次交换

所以,时间复杂度为(1n-1)*(n-1)/2 n*(n-1)/2 O(n² )

具体代码如下:

void bubble_sort(int b[], int n) { bool changetrue; int i,j,temp; for(in-1;i>1 i--) { changefalse; for(j0;jb[j1]) { tempb[j]; b[j]b[j1]; b[j1]temp; changetrue; } } } }

【本文来源：香港服务器租用 http://www.558idc.com/st.html欢迎留下您的宝贵建议】