【21天学习挑战赛】冒泡排序与插入排序

---

冒泡排序

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

冒泡排序的步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码

	public static void bubbleSort(int[] arr) {
    
		if (arr == null || arr.length < 2) {
    
			return;
		}
		// 0 ~ N-1
		// 0 ~ N-2
		// 0 ~ N-3
		for (int e = arr.length - 1; e > 0; e--) {
     // 0 ~ e
			for (int i = 0; i < e; i++) {
    
				if (arr[i] > arr[i + 1]) {
    
					swap(arr, i, i + 1);
				}
			}
		}
	}

	// 交换arr的i和j位置上的值
	public static void swap(int[] arr, int i, int j) {
    
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}

时间复杂度分析

因为有比较和交换行为,最差的情况就是每个元素从头交换到尾
例如[9,8,7,6,5,4,3,2,1,0]
因此时间复杂度为O(n²)

插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

在生活中,最简单的例子就是扑克牌的排序了,
在排序扑克牌的时候,我们会把小的排插入到前面
只要会了如何排序扑克牌,那么就可以很快的理解插入排序了

代码

	public static void insertionSort(int[] arr) {
    
		if (arr == null || arr.length < 2) {
    
			return;
		}
		// 不只1个数
		for (int i = 1; i < arr.length; i++) {
     // 0 ~ i 做到有序
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
    
				swap(arr, j, j + 1);
			}
		}
	}
	public static void swap(int[] arr, int i, int j) {
    
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}

时间复杂度

最差情况为每次小的元素都要从最后插到最前面
例如[9,8,7,6,5,4,3,2,1]
因此时间复杂度为O(n²)