选择排序和冒泡排序，能否整合成一种更高效的排序算法？

本文共计631个文字，预计阅读时间需要3分钟。

选择排序思想（升序排列）：

1.从未排序的数组中取第一个元素b[i]作为基准值。

2.遍历数组，比较每个元素与基准值。

3.如果发现元素b[j]小于基准值b[i]，则交换它们的位置。

4.重复步骤1-3，直到遍历完整个数组。

选择排序思路(按升序排列):依次取数组未排好序的首个元素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; } } } }