冒泡排序2-排序算法

遍历数组的同时，使本次相邻的俩个数是左小右大（左大右小）；

冒泡排序

平均时间复杂度：O(n²)；最好情况：O(n)；最坏情况：O(n²)；

空间复杂度：O(1)

排序方式：In-place （占用常数内存，不占用额外内存）

稳定性：稳定

Implementation:

/**
 * 冒泡算法
 * @author hxr
 * @see https://github.com/MisterBooo/LeetCodeAnimation
 * 核心：遍历数组的同时，使本次相邻的俩个数是左小右大（左大右小）；每次循环少遍历一个数；定义一个标记，当某次没有交换时，数组已经有序。
 */
public class BubbleSort {
	public static void main(String[] args) throws Exception {
		int[] sourceArray = {8,3,2,4,5};
		
		int[] arr = sort(sourceArray);
		
		System.out.print("排序后：");
		System.out.println(Arrays.toString(sourceArray));
		
		System.out.print("排序前：");
		System.out.println(Arrays.toString(arr));
		
	}
	public static int[] sort(int[] sourceArray) throws Exception{
		// 复制数组内容，int[] arr = sourceArray 排序后会改变原数组内容
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		
		for (int i = 1; i < arr.length; i++) {
			// 若循环没有做交换，则数组有序。设定一个标记，若为true，排序已经完成。例如：数组为8,5,4,3,2，第一次循环数组没有做交换，则数组有序，直接返回。
			boolean flag = true;
			
			for (int j = 0; j < arr.length-i; j++) {
				if (arr[j] < arr[j+1]) {
					int temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
					
					flag = false;
				}
			}
			
			if (flag) {
				break;
			}
		}
		return arr;
	}
}