算法	最坏情况	平均情况/期望运行时间
	Θ(n^2)	Θ(n^2)
	Θ(nlg(n))	Θ(nlg(n))
	O(nlg(n))
	Θ(n^2)	Θ(nlg(n))(期望)
	Θ(k+n)	Θ(k+n)
	Θ(d(k+n))	Θ(d(k+n))
	Θ(n^2)	Θ(n)(平均情况)

插入排序

将当前值插入到已经排好的序列中。最好的情况下是n，最差情况下是n^2。属于原址排序。

static void InsertSort(List
     
       sq){    for (int j = 1; j < sq.Count; j++)    {        var current = sq[j];        int i = j - 1;        //如果当前值大的话，不用移动，小的话，移动比他小的值        while (i >= 0 && sq[i] > current)        {            sq[i + 1] = sq[i];            i--;        }        sq[i + 1] = current;    }}
     

归并排序

总代价总是为nlg(n)。非原址排序。

static void Merge_Sort(List
     
       sq, int s, int e){    if (s < e)    {        int q = (s + e) / 2;        //分治        Merge_Sort(sq, s, q);        Merge_Sort(sq, q+1, e);        //合并        Merge(sq, s, q, e);    }}static void Merge(List
      
        sq, int s, int m, int e){    List
       
         sequenceL = new List
        
         ();    //拷贝分支    for (int i = s; i <= m; i++)        sequenceL.Add(sq[i]);    List
         
           sequenceR = new List
          
           (); for (int i = m+1; i <= e; i++) sequenceR.Add(sq[i]); //归并 int li = 0, ri = 0; for (int k = s; k <= e; k++) { //另外一个分支合并完成的情况 if (li >= sequenceL.Count) { sq[k] = sequenceR[ri]; ri++; continue; } if (ri >= sequenceR.Count) { sq[k] = sequenceL[li]; li++; continue; } //比较两个分支的当前元素 if (sequenceL[li] < sequenceR[ri]) { sq[k] = sequenceL[li]; li++; } else { sq[k] = sequenceR[ri]; ri++; } }}