一，排序
其中最基本的三种排序是冒泡，选择与插入。其平均复杂度为O(n^2). 但是其中选择排序在数据有序的情况or数据量小的情况下效率很高。虽然简单也是应该掌握的排序。
比如C++的STL库中的sort模板函数，在数据量较小的情况下使用的是插入排序，在数据量较大使用快速排序等。
1.冒泡
最简单的排序方法。思路如下 时间复杂度O(N^2) 空间复杂度O(1)
1）从左往右扫描两两比较数据，如果发现左边的数大于右边的数则交换。
第一轮扫描以后，最右边的数一定为序列中最大的数
2）第二轮开始扫描，重复步骤1，只是此次扫描排除第一轮中已经确定的最大数
3）以此类推知道最后一轮扫描仅剩下一个元素时排序结束
// Bubble sort
int bubble_sort(int *data, int length) {int i = 0, j = 0, temp;for(j = length - 1; j > 0; j--) {for(i = 0; i < j; i++) {if(data[i] > data[i + 1]) {temp = data[i + 1];data[i + 1] = data[i];data[i] = temp;}}}
}
2.选择排序
时间复杂度O(n^2), 空间复杂度O(1)
1）先将锚点选为第一个元素，然后逐一比较后续的每个数，如果发现有比锚点小的数则对其进行标记。
一轮扫描完以后将锚点标记的数与第一个元素进行交换；
2）接着将锚点标记为第二个数，并从第二个数起往后扫描，同样发现比锚点小的数则对齐进行重新标记。
一轮扫描完以后将锚点的数与第二个数进行交换；
3）以此类推直到只剩下最后一个数。
// Selection sort
int selection_sort(int *data, int length) {int i = 0, j = 0, k, temp;for(i = 0; i < length - 1; i++) {k = i;for(j = i + 1; j < length; j++) {if(data[k] > data[j])k = j;}// swap the dataif (k != i) {temp = data[k];data[k] = data[i];data[i] = temp;}}
}3.插入排序
插入排序在数据量小or基本有序的情况下其效率非常之高。最理想的时间复杂度是O(n) ,也是STL中使用的一种排序算法。
插入排序的基本思想是：
1）从第二个元素开始与其前面对比，若发现逆序则交换。直到前面的数比其小则停止扫描