算法笔记

2.7.5 引用

int &x 不是取地址的意思，而是对原变量的引用，在函数内的修改可以反映到变量上。常量不可以使用引用。

6.9.6 sort()

#include <iostream>
#cmp为比较函数，下面实现从大到小排序的例子。
bool cmp(int a,int b){
	return a>b;//当a>b时把a放在前面
}
sort(start,end,cmp)

排序

冒泡排序

定义：依次比较序列两个数的值，将较大的数字放在同一个方向。经过这一操作，最大数字可以筛到序列的最末端。在含有n个数的序列中，进行n-1趟操作，第i趟操作都能确定第i大的数字在序列的倒数第i位。

冒泡：大数字像泡泡一样，依次按顺序从序列末端浮现。

算法复杂度：第i趟需要比较n-1次。n-1 + n-2 + … + 1=$\frac{n(n-1)}{2}$ 复杂度为O($n^2$)

选择排序

定义：每一趟选出未排序中最小的数字，与未排序的第一位进行交换

选择：按照排序的结果来理解，就是按照顺序从小到大排列。那我们就按照顺序，确定好每个位置的数字

算法复杂度：O($n^2$)

插入排序

定义：对于第i个元素，判断其在$[0,i-1]$的有序列表中应该插入的位置。将应该插入位置后面的元素向后移位，等该位置空出后插入。

插入：判断后续元素在前面的有序序列中应该插入的位置。

算法复杂度：最坏情况O（$n^2$）最好情况：O(N)

This line appears after every note.