Nolan's Notes
0%

BubbleSort

Posted on Edited on In ,

冒泡排序

一、冒泡排序

原理：对一组数据，比较相邻数据的大小，将值小数据在前面，值大的数据放在后面。 （以下都是升序排列，即从小到大排列）

举例说明： $arr = array(6, 3, 8, 2, 9, 1);

$arr 有6个数据，按照两两比较大小如下，注意 比较轮数 和 每轮比较次数

第一轮排序：

第一次比较 6和3比较 结果：3 6 8 2 9 1

第二次比较 6和3比较 结果：3 6 8 2 9 1

第三次比较 8和2比较 结果：3 6 2 8 9 1

第四次比较 8和9比较 结果：3 6 2 8 9 1

第五次比较 9和1比较 结果：3 6 2 8 1 9

第一轮比较总结：

1.排序第1轮、比较5次，没有获得从小到大的排序

2.因为每次比较都是大数往后靠，所以比较完成后，可以确定大数排在最后（9 已经冒泡冒出来了，下轮比较可以不用比较了 ）

第二轮排序：

第一次比较 3和6比较 结果：3 6 2 8 1 9

第二次比较 6和2比较 结果：3 2 6 8 1 9

第三次比较 6和8比较 结果：3 2 6 8 1 9

第四次比较 8和1比较 结果：3 2 6 1 8 9

第一轮比较总结：

1.排序第2轮、比较4次，没有获得从小到大的排序

2.冒泡出了 8，下轮不用比较8 了

第三轮排序：

第一次比较 3和2比较 结果：2 3 6 1 8 9

第二次比较 3和6比较 结果：2 3 6 1 8 9

第三次比较 6和1比较 结果：2 3 1 6 8 9

第三轮比较总结：

1.排序第3轮、比较3次，没有获得从小到大的排序

2.冒泡出了 6，下轮不用比较6 了　

第四轮排序：

第一次比较 2和3比较 结果：2 3 1 6 8 9

第二次比较 3和1比较 结果：2 1 3 6 8 9

第四轮比较总结：

1.排序第4轮、比较2次，没有获得从小到大的排序

2.冒泡出了 3，下轮不用比较3 了

第五轮排序：

第一次比较 2和1比较 结果：1 2 3 6 8 9

第五轮比较总结：

1.排序第5轮、比较1次，没有获得从小到大的排序

2.冒泡出了 2，由于还剩一个1，不用再比较了，至此通过5轮排序，完成整个排序。

结论

通过以上五轮排序，若干次比较，我们有理由推断出一个结论：

对于一个长度为N的数组，我们需要排序 N-1 轮，每 i 轮 要比较 N-i 次。对此我们可以用双重循环语句，外层循环控制循环轮次，内层循环控制每轮的比较次数。

Golang实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func sort_bubble(arr []int) {

	len := len(arr)
	for i:=1;i<len;i++{
		for j:=0;j<len-i;j++{
			if arr[j] > arr[j+1]{
				arr[j],arr[j+1] = arr[j+1],arr[j]

			}
			fmt.Println(arr)
		}
	}
	fmt.Println()
	fmt.Println(arr)
}

func main() {
	arr := [...]int{6,3,8,2,9,1}
	slice := arr[:]
	fmt.Println(slice)
	fmt.Println()
	sort_bubble2(slice)
}

PHP实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function bubble($arr)
{
    $count = count($arr);

    for ($i = 1; $i <$count;$i++){
        for ($j =0; $j<$count-$i;$j++){
            if($arr[$j] > $arr[$j+1]){
                $tmp = 0;
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;

            }
        }
    }
    print_r($arr);
}

$arr = array(6, 3, 8, 2, 9, 1);
bubble($arr);