冒泡排序与选择排序

时间:2021-05-12 22:10:42

示例数组:

$array = [62, 88, 58, 47, 62, 35, 73, 51, 99, 37, 93];

一、冒泡排序

将数组分为有序和无序两部分,无序序列中的相邻元素进行比较,如果前面的元素值大于后边的元素值,两者交换,第一轮排序后,最大值(99)会放入有序序列的最前边(10的位置),即有序序列中的元素为[99],如下所示:

Array ( [0] => 62 [1] => 58 [2] => 47 [3] => 62 [4] => 35 [5] => 73 [6] => 51 [7] => 88 [8] => 37 [9] => 93 [10] => 99 ) 

第二轮排序,同理,无序序列中从第一个元素开始,相邻元素相比较,如果前者大于后者,交换数据,在9的位置结束(10为有序序列的位置),第二轮排序结束后,第二轮的最大元素插入有序序列的最前边(93在9的位置),即有序序列的元素为[93,99],结果如下所示:

Array ( [0] => 58 [1] => 47 [2] => 62 [3] => 35 [4] => 62 [5] => 51 [6] => 73 [7] => 37 [8] => 88 [9] => 93 [10] => 99 )

以此类推,经过10轮完成排序,如下:

第1次排序结束
Array ( [0] => 62 [1] => 58 [2] => 47 [3] => 62 [4] => 35 [5] => 73 [6] => 51 [7] => 88 [8] => 37 [9] => 93 [10] => 99


第2次排序结束
Array ( [0] => 58 [1] => 47 [2] => 62 [3] => 35 [4] => 62 [5] => 51 [6] => 73 [7] => 37 [8] => 88 [9] => 93 [10] => 99


第3次排序结束
Array ( [0] => 47 [1] => 58 [2] => 35 [3] => 62 [4] => 51 [5] => 62 [6] => 37 [7] => 73 [8] => 88 [9] => 93 [10] => 99


第4次排序结束
Array ( [0] => 47 [1] => 35 [2] => 58 [3] => 51 [4] => 62 [5] => 37 [6] => 62 [7] => 73 [8] => 88 [9] => 93 [10] => 99


第5次排序结束
Array ( [0] => 35 [1] => 47 [2] => 51 [3] => 58 [4] => 37 [5] => 62 [6] => 62 [7] => 73 [8] => 88 [9] => 93 [10] => 99


第6次排序结束
Array ( [0] => 35 [1] => 47 [2] => 51 [3] => 37 [4] => 58 [5] => 62 [6] => 62 [7] => 73 [8] => 88 [9] => 93 [10] => 99


第7次排序结束
Array ( [0] => 35 [1] => 47 [2] => 37 [3] => 51 [4] => 58 [5] => 62 [6] => 62 [7] => 73 [8] => 88 [9] => 93 [10] => 99


第8次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 58 [5] => 62 [6] => 62 [7] => 73 [8] => 88 [9] => 93 [10] => 99


第9次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 58 [5] => 62 [6] => 62 [7] => 73 [8] => 88 [9] => 93 [10] => 99


第10次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 58 [5] => 62 [6] => 62 [7] => 73 [8] => 88 [9] => 93 [10] => 99

 

二、选择排序

将数组分为有序与无序两部分,有序序列在前边,无序序列在后边,每一轮排序将无序序列中的第一个元素与剩余元素进行比较,找到最小元素后放到有序序列的最后。

第一轮排序,有序序列默认为空,找出数组中的最小元素(35),放入有序序列中(有序序列元素只有35一个元素),结果如下:

Array ( [0] => 35 [1] => 88 [2] => 62 [3] => 58 [4] => 62 [5] => 47 [6] => 73 [7] => 51 [8] => 99 [9] => 37 [10] => 93 ) 

以此类推,10轮排序后结束,如下:

第1次排序结束
Array ( [0] => 35 [1] => 88 [2] => 62 [3] => 58 [4] => 62 [5] => 47 [6] => 73 [7] => 51 [8] => 99 [9] => 37 [10] => 93 ) 


第2次排序结束
Array ( [0] => 35 [1] => 37 [2] => 88 [3] => 62 [4] => 62 [5] => 58 [6] => 73 [7] => 51 [8] => 99 [9] => 47 [10] => 93 ) 


第3次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 88 [4] => 62 [5] => 62 [6] => 73 [7] => 58 [8] => 99 [9] => 51 [10] => 93 ) 


第4次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 88 [5] => 62 [6] => 73 [7] => 62 [8] => 99 [9] => 58 [10] => 93 ) 


第5次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 58 [5] => 88 [6] => 73 [7] => 62 [8] => 99 [9] => 62 [10] => 93 ) 


第6次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 58 [5] => 62 [6] => 88 [7] => 73 [8] => 99 [9] => 62 [10] => 93 ) 


第7次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 58 [5] => 62 [6] => 62 [7] => 88 [8] => 99 [9] => 73 [10] => 93 ) 


第8次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 58 [5] => 62 [6] => 62 [7] => 73 [8] => 99 [9] => 88 [10] => 93 ) 


第9次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 58 [5] => 62 [6] => 62 [7] => 73 [8] => 88 [9] => 99 [10] => 93 ) 


第10次排序结束
Array ( [0] => 35 [1] => 37 [2] => 47 [3] => 51 [4] => 58 [5] => 62 [6] => 62 [7] => 73 [8] => 88 [9] => 93 [10] => 99 ) 

 

两者共同点:

将数组分为有序序列与无序序列,将每轮筛选出来的元素插入有序序列,黄的部分为有序序列

不同点:

冒泡排序——相邻元素比较,找出最大值,放入有序序列的最前边;

选择排序——用无序序列中的第一个元素与剩余无序序列元素进行比较,找出最小元素,插入有序序列的最后边