排序算法

冒泡排序

4	5	3	6	2	1
4	5	3	6	2	1
4	5	3	6	2	1
4	3	5	6	2	1
4	3	5	6	2	1
4	3	5	2	6	1
4	3	5	2	1	6

一次冒泡操作，可以将最大的数浮到最后面。

循环 array.size() 次，即可完成排序。

当某次冒泡操作已经没有数据交换时，说明已经达到了完全有序，不用再执行后续的冒泡排序了。

void bubbleSort(vecotr<int> &a, int n) { // n 为数组长度
	if (n <= 1) return;
	
	for (int i = 0; i < n; i++) { // 这是需要进行冒泡操作的次数
		bool flag = false; // 用来记录是否有数据交换
		
		for (int j = 0; i < n - 1 - i; j++) { // 这是一次冒泡操作，n - 1 - i 是这次冒泡排序中最大的数能够浮动到的位置的前一位
			a[j] = a[j] ^ a[j + 1];
			a[j+1] = a[j] ^ a[j + 1];
			a[j] = a[j] ^ a[j + 1];
			
			flag = true;
		}
		if (!flag) break;
	}
}

1. 冒泡排序是原地排序算法吗？

• 是，空间复杂度为 O(1)

2. 冒泡排序是稳定的排序算法吗？

• 是，当两个相邻的元素大小相等的时候，不会进行交换，元素的排列顺序不变。

3. 冒泡排序的时间复杂度是多少？

• 最好情况：[1, 2, 3, 4, 5, 6]，1次冒泡，时间复杂度：O(n)

• 最坏情况：[6, 5, 4, 3, 2, 1]，6次冒泡，时间复杂度：O(n^2)

• 平均时间复杂度：O(n^2)

插入排序

4	5	3	6	2	1
4	5	3	6	2	1
4	5	3	6	2	1
3	4	5	6	2	1
3	4	5	6	2	1
2	3	4	5	6	1
1	2	3	4	5	6

void insertionSort(vector<int> &a, int n) {
	if (n <= 1) return;
	
	for (int i = 1; i < n; i++) {
		int value = a[i];
		int j = i - 1;
		
		for (; j >=0; j--) {
			if (a[j] > value) {
				a[i + 1] = a[j];
			} else {
				break;
			}
		}
		a[j + 1] = value;
	}
}

1. 插入排序是原地排序算法吗？

• 是，空间复杂度为 O(1)

2. 插入排序是稳定的排序算法吗？

• 是。

3. 冒泡排序的时间复杂度是多少？

• 最好情况：[1, 2, 3, 4, 5, 6]，1次冒泡，时间复杂度：O(n)

• 最坏情况：[6, 5, 4, 3, 2, 1]，6次冒泡，时间复杂度：O(n^2)

• 平均时间复杂度：O(n^2)