Time complexity:
Binary search O(log2 n):
i=0. n elements: -------------------
i=1. n/2 elements: ----------
i=2. n/4 elements: -----
...
i=i. n/2^i elements: -
进行n/2^i=1， i=log2 n 次，来达到只剩一个element.
1，Selection Sort
Steps:
from 0~n-1, select the minimum element[comparing n-1 times], swap it with the A[0].
from 1~n-1, select the minimum element[comparing n-2 times], swap it with the A[1].
...
So total comparison times: n-1+n-2+...+2+1 = n(n-1)/2=O(n^2).
2, Insertion Sort
Steps:
i, compare with j=0~i-1=0, if bigger than A[j], nothing changes; if smaller than A[j], A[j+1] = A[j], move A[i] to position j.
So total comparison times: 1+2+...+n-1=n(n-1)/2=O(n^2).
[DS Basics] Sorting,布布扣,bubuko.com
原文：http://www.cnblogs.com/chayu3/p/3928167.html