排序算法

交换排序

冒泡排序：从后往前（或从前往后），两两比较相邻元素的值，若为逆序，交换，直到序列比较完。则为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置。

特点：稳定
注意 flag 变量的作用。
空间复杂度：临时变量用作交换。 O(1)
时间复杂度：最坏：外层 0 到 n-1 次计算，内层 n-1-i ,所以一共执行 $\sum_0^{n-1} n-1-i = \frac {n*(n-1)}{2}$

快速排序：选第一个元素枢轴（随机选取，一般选择第一个），先从后往前找小于枢轴（pivot）的数，再从前往后找比枢轴要大的元素，往复循环到下标相等的时候，下标对应的值为枢轴的值。一趟排序结束，结果是左边的比枢轴元素小，右边的数比枢轴元素要大。分治两边的排序，当划分最小为 1 时，不在划分，排序完成。

两部分：partition 和 quicksort
特点：适合无序程度高的序列排序。分治法。不稳定，存在交换。
空间复杂度：快排是递归排序的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。
最好的情况：$\lceil log_2 (n+1) \rceil$ ,每次 partition 都很均匀, 递归树的深度 O(logn)
最坏的情况：因为要进行 n-1 次调用，所以栈的深度为 O(n)
时间复杂度：$T(n) = aT(\frac {n}{b} + f(n))$ 其中 $\frac {n}{b}$ 是子问题的大小，比如快排每次划分子问题之后的大小，a 是子问题大小的数量，f(n) 是分解问题和合并问题所需要的时间。
最好的情况：a = b = 2 $f(n) = O (n) = $ 均分
最坏的情况：每次 partition 取到的元素在一端，即 $T(n) = T(n-1) + T(0) f(n) = T(n-2) + f(n) + f(n-1) =……= f(1) + f(2) + … + f(n)$ (等差数列) = O(n^2)
根据主定理的第二种情况分析：O(nlogn)

快速排序最坏的情况运行时间为 $O(n^2)$ ,最然这个最坏情况运行时间比较差，但快速排序通常是用于排序最佳的实用选择，这是因为其平均性能相当好：期望运行时间为 $O(nlogn)$，而且$O(nlog(n))$ 记号中隐含的常数因子很小。 ———— 《算法导论》

快排什么情形下出现最坏时间复杂度？
划分函数极度不平衡的时候，是 $O(n^2)$ 。

# 快速排序代码
class Solution(object):        
    def quicksort(self,nums,l,h):
        if l < h:
            pivotpos = self.partition(nums,l,h)
            self.quicksort(nums,l,pivotpos - 1)
            self.quicksort(nums,pivotpos + 1,h)

    def partition(self,nums,l,h):
        p = nums[l]
        while l < h:
            while l < h and nums[h] <= p:
                h -= 1
            nums[l] = nums[h]
            while l < h and nums[l] >= p:
                l += 1
            nums[h] = nums[l]
        nums[l] = p
        return l

插入排序

插入类排序就是在一个有序的序列中，插入一个新的关键字，直到所有的关键字都插入形成一个有序的序列
插入类排序包括直接插入排序、折半插入排序和希尔排序。

直接插入排序

首先以一个元素为有序的序列，然后将后面的元素依次插入到有序的序列中合适的位置直到所有元素都插入有序序列。
直接插入排序分析:

• 空间复杂度：在下标为0处存储哨兵，是常数个辅助空间大小，所以空间复杂度为O(1)
• 时间复杂度：最坏情况下：整个序列都是逆序, 最好情况下：整个序列都是顺序。
  当给关键字4排序时，前面的序列已经是2 4 5 6，根据算法比较4和有序序列的关键字大小。
  当比较4和4的时候，已经不满足A[0].key<A[j].key。所以直接将4放在4后面。所以直接插入排序是稳定性是稳定的。

  void InsertSort(ElemType A[],int n){
  int i,j;
  for(i=2;i<=n;i++)   
      if(A[i].key<A[i-1].key){    
          A[0]=A[i];  //复制为哨兵，A[0]不存放元素
          for(j=i-1;A[0].key<A[j].key;--j)
              A[j+1]=A[j];    //所有比待插入元素值大的都往后移一位，腾出空位
          A[j+1]=A[0];        //复制到插入位置 
      }
  }