[21 Days Learning Challenge] Bubble Sort and Insertion Sort

---

冒泡排序

冒泡排序的英文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];
	}

时间复杂度分析

Because of the compare and swap behavior,The worst case is that each element is swapped from beginning to end
例如[9,8,7,6,5,4,3,2,1,0]
因此时间复杂度为O(n²)

插入排序

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

在生活中,The simplest example is the sorting of playing cards,
when sorting playing cards,We'll insert the small row to the front
Just know how to sort playing cards,Then you can quickly understand the insertion sort

代码

	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];
	}

时间复杂度

The worst case is that each small element must be inserted from the end to the first
例如[9,8,7,6,5,4,3,2,1]
因此时间复杂度为O(n²)