冒泡排序.md

冒泡排序

简介

数组长度为N, 
第一次循环将0到N-1位置上最大的数放在N-1的位置, 
第二次循环将0-N-2位置上最大的数放在N-2的位置,
...

过程分析

# [3, 6, 4, 2, 7], 设数组长度为N

# 第一次循环 0 到 N-1
[3, 6, 4, 2, 7]
 ^  ^ 
3 < 6, 不用交换
[3, 6, 4, 2, 7]
    ^  ^
6 > 4, 交换位置
[3, 4, 6, 2, 7]
       ^  ^
6 > 2, 交换位置
[3, 4, 2, 6, 7]
          ^  ^
6 < 7, 不用交换
[3, 4, 2, 6, 7]

# 第二次循环 0 - N-2
...
[3, 2, 4, 6, 7]

# 第三次循环 0 - N-3
...
[2, 3, 4, 6, 7]

# 第四次循环 0 - N-4
...
[2, 3, 4, 6, 7]

代码

PHP

<?php

class BubbleSort
{
    /**
     * 排序
     *
     * @param $arr
     * @return bool
     */
    public static function sort(&$arr)
    {
        if ($arr == null || count($arr) < 2) {
            return false;
        }

        for ($end = count($arr) - 1; $end > 0; $end--) {
            for ($i = 0; $i < $end; $i++) {
                if ($arr[$i] > $arr[$i + 1]) {
                    list($arr[$i], $arr[$i + 1]) = [$arr[$i + 1], $arr[$i]];
                }
            }
        }
    }
}

// Test
$arr = [3, 6, 4, 2, 7];
BubbleSort::sort($arr);
// [2, 3, 4, 6, 7]
print_r($arr);

java

import java.util.Arrays;

public class BubbleSort {
	public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int end = arr.length - 1; end > 0; end--) {
			for (int i = 0; i < end; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	public static void main(String[] args) {
		int[] arr = {3, 6, 4, 2, 7};
		bubbleSort(arr);
		// [2, 3, 4, 6, 7]
		System.out.println(Arrays.toString(arr));
	}
}

时间复杂度

O(N^2)