冒泡排序

阿秀自己刷过的算法部分经过整理后是按照不同基础、不同人群分类的,如果你不知道自己该看哪个部分的算法题,可以先看一下这里,戳我直达

以下是本部分正文:

这里简单为大家讲解一下一些算法基础知识与十大排序,在面试考察中十大排序出现的频率是非常高的,特别是冒泡排序、快速排序、归并排序等,具体可点击这里

# 插入排序

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。

当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开 始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。

如果碰见一个和插入元素相 等的,那么插入元素把想插入的元素放在相等元素的后面。

所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

  1. 从第一个元素开始,该元素可以认为已经被排序

  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描

  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置

  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

  5. 将新元素插入到该位置后

  6. 重复步骤2~5

    时间复杂度 on^2 空间 o1,稳定排序,原地排序

void print(vector<int>& a, int n, int i) {
	cout << "step"<< i << ": ";
	for (int j = 0; j < n; j++) {
		cout << a[j] << " ";
	}
	cout << endl;
}
void insertionSort(vector<int>& a, int n) {//{ 9,1,5,6,2,3 }
	for (int i = 1; i < n; ++i) {
		if (a[i] < a[i - 1]) {   //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
			int j = i - 1;
			int x = a[i];     //复制为哨兵,即存储待排序元素
			//a[i] = a[i - 1];           //先后移一个元素,可以不要这一句,跟循环里面的功能重复了
			while (j >= 0 && x < a[j]) {   //查找在有序表的插入位置,还必须要保证j是>=0的 因为a[j]要合法
				a[j + 1] = a[j];
				j--;     //元素后移
			}
			a[j + 1] = x;     //插入到正确位置
		}

		print(a, n, i);      //打印每趟排序的结果
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23