认识时间复杂度
常数时间的操作
一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。
具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。
在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果f(N)，那么时间复杂度为O(f(N))。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是常数项时间。
几个简单算法
选择排序
选择排序的方法是将数组数按照从左到右的顺序，先将第一个数定位为最小，并将其下标定为minIndex，然后依次与后面的数进行对比，当遇到比它小的数，就将这个数的下标赋值给minIndex，直到最后一个元素，最后将minIndex对应的数调换到数组第一个位置，这样就能将数组中最小的数调整到数组第一个位置，接下来对数组第二个数进行相同的操作，这样就能将数组中第二小的数调整到数组第二个位置，以此类推。
其实现代码如下：[算法时间复杂度O（N^2）]
function SelectionSort(array) {
for (var i = 0; i < array.length; i++) {
var minIndex = i;
for (var j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array, i, minIndex);
}
}
function swap(array, i, j) {
if (array[i] == array[j]) {
return;
}
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
其中将数组中两个数进行互换的函数，采用了异或运算，其实现为：
a=a^b
b=(a^b) ^b=a
a=(a^b) ^a=b
异或运算的性质：
- 0^N == N，N^N == 0
- 异或运算满足交换律和结合率
- 不用额外变量交换两个数
冒泡排序
冒泡排序首先将数组的第一个数与第二个数进行对比，如果位于前面的数大，将两个数进行交换，然后将数组第二个数与其后一位数进行对比，同样的如果位于前面的数大，将两个数进行交换，依次类推，最后会将数组中最大的数调整到数组最后的位置。然后再从数组第一个数开始进行上述操作，但是这次不需要与最后的数进行对比，所以在代码中j < array.length - 1 - i这样就能避免与已经排好的后面的数字进行对比，节省程序运行时间。
function BubbleSort(array) {
for (var i = 0; i < array.length - 1; i++) {
for (var j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
function swap(array, i, j) {
if (array[i] == array[j]) {
return;
}
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
插入排序
插入排序是从数组第二个元素开始，从后往前的与前面的数进行对比，直到前面的数小于等于它或者已经到数组最前端时不再对比，此时将它与这个数进行交换，因为数组第一个元素前面没有数，所以它不用进行对比，因此循环开始是i=1
function InsertionSort(array) {
for (var i = 1; i < array.length; i++) {
for (var j = i; j > 0 && array[j] < array[j - 1]; j--) {
swap(array, j, j - 1);
}
}
}
function swap(array, i, j) {
if (array[i] == array[j]) {
return;
}
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
