排序

插入排序

    InsertionSort( A )   //T(n) = O(n^2)
        for j = 2 to Length[A]
            key = A[j] ;
            i = j - 1 ;

            while i > 0 and A[i] > key   
                A[i+1] = A[i] ;
                i-- ;

            A[i+1] = key ;
  • 证明:
    循环不变式:数组A[1..n]的子数组A[1..j-1]有序
    初始化:j=2,子数组A[1..j-1]只有一个元素A[1],所以有序
    保持:子数组A[1..j-1]已经有序,现在来看A[j],第二层循环会将所有大于A[j]的,在子数组A[1..j-1]的元素向右移动,然后再将A[j]插入到空出来的位置,依旧保持子数组A[1..j-1]有序
    结束:j=n,数组A[1..n]有序

并归排序

    Merge( A, p, q, r)      //p低位置,q中间位置,r高位滞
        n1 = q - p + 1 ;
        n2 = r - q ;

        create array L[1..n1+1] ;   //L[n1+1]存放哨兵
        create array R[1..n2+1] ;   //R[n2+1]存放哨兵

        L[1..n1] = A[p..q] ;
        L[1..n2] = A[q+1..r] ;

        //哨兵
        L[n1+1] = MAX_VALUE ;
        R[n2+1] = MAX_VALUE ;

        i = 1 ;
        j = 1 ;

        for k = p to r             //加入哨兵后,循环不用检测i<=n1,j<=n2
            A[k] = ( L[i] < R[j] ? L[i++] : R[j++] ) ;

    /*=================*/
    MergeSort( A, p, r )   //T(n) = O(lgn)
        if p < r 
            q = (p + r) / 2 ;
            MergeSort( A, p, q ) ;
            MergeSort( A, q+1, r ) ;
            Merge( A, p, q, r ) ;
  • 在MergeSort中,条件 p < r,即A[p..r]中至少有两个元素,这是执行Merge才有意义

二分查找

    BinSearch( A, p, r, key )  //T(n) = O(lgn)
        if p <= r
            q = (p + r) / 2 ;
            switch A[q] in 
            == key : return q ;
            > key : return BinSearch( A, p, q-1, key ) ;
            < key : return BinSearch( A, q+1, r, key ) ;

        return nil ;
  • 给定一个由n个整数构成的集合S和另一个整数x,判断S中是否存有两个其和等于x的元素
    SearchSum( S, p, r, x )     //T(n) = nlgn 
        MergeSort( S, p, r ) ;
        i = p ;
        while S[i] <= x / 2 ;
            i++ ;

        w = i - 1 ;

        for i = p to w 
            key = x - A[i] ;
            k = BinSearch( S, i+1, r, key ) ;
            if k != nil 
                print i, k ;

冒泡排序

    BubbleSort( A )  //T(n) = O(n^2)
        for i = 1 to n
            for j = n down to i+1
                A[j] < A[j-1] && swap( A[j], A[j-1] ) ;
  • 循环不变式: A[i]是数组A[i,i+1]最小的

  • 霍纳规则

多项式: P(x) = SUM( Ak * X^k; k=0 to n ) = A0+X(A1+X(A2+…+X(An-1+XAn)…))

    PolyAdd( A, x )    //T(n)=O(n)
        Y = 0 ;
        i = length[A] ;
        while i >= 0
            Y = A[i] + x*Y ; //对应于 An-1 + XAn
            i-- ;     
        return Y ;       
  • 设A[1..n]是一个包含n个不同数的数组,如果在i < j 的情况下,有A[i] > A[j],则( i, j )就称为A中的一个逆序对.确定n个元素的任何排列中的逆序的数目
      global define N = 0 //定义全局变量N,用来计数逆序对
    
      MergeCount( A, p, q, r )
          n1 = q - p + 1 ;
          n2 = r - q ;
    
          create array L[1..n1+1] ;
          create array R[1..n2+1] ;
    
          L[1..n1] = A[p..q] ;
          R[1..n2] = A[q+1..r] ;
    
          L[n1+1] = MAX_VALUE ;
          R[n2+1] = MAX_VALUE ;
    
          i = 1 ;
          j = 1 ;
    
          for k = p to r 
              if L[i] <= R[j]
                  A[k] = L[i] ;
                  i++ ;
              else
                  A[k] = R[j] ;  //L[j] > R[j] ==> R[j]比L[i..n1]中所有的数都小
                  j++ ;          //因为L[1..n1]和R[1..n2]都是升序排列
                  N += n1-i+1 ;  //逆序对就有(L[i],R[j]),(L[i+1],R[j]),...,(L[n1],R[j])
                                 //一共 n1 - i + 1 对
    
      /*================*/
      CountInversion( A, p, r )
          if( p < r )
              q = (p + r) / 2 ;
              CountInversion( A, p, q ) ;
              CountInversion( A, q+1, r ) ;
              MergeCount( A, p, q, r ) ;
    

堆排序

  • 大根堆: A[parent[i]] >= A[i]
  • 小根堆: A[parent[i]] <= A[i]

当用数组表示存储n个元素的堆时,叶子节点的下标是 n/2+1, n/2+2, …, n

    MaxHeapify( A, i, heapsize[A] )  //T(n) = O(lgn)
    /*
    设A[i+1,...,heapsize[A]]为已好的大根堆
    此函数的作用是将A[i]加入到堆中,并保持堆的性质
    */
        if heapsize[A] / 2 + 1 > i      //判断A[i]是不是叶节点
            n = heapsize[A] ;
            j = 2 * i + 1 > n ? 2 * i ( A[2*i] > A[2*i+1] ? 2*i : (2*i+1) ) //防止数组越界
            if A[i] < A[j]
                swap( A[i], A[j] ) ;
                MaxHeapify( A, j, n ) ; 

建堆

    BuildMaxHeap( A ) 
        heapsize[A] = length[A] ;
        for i = heapsize[A] / 2 down to 1      //不用考虑吧叶节点
            MaxHeapify( A, i, heapsize[A] ) ;

排序

    HeapSort( A )   //T(n) = O(nlgn)
        n = length[A] ;
        BuildMaxHeap( A ) ;
        for i = n down to 2
            swap( A[1], A[i] ) ;
            MaxHeapify( A, 1, i-1 ) ;

优先级队列(大根堆)

    HeapMaximum( A )        //返回堆的最大值,T(n)=O(1)
        return A[1] ;

    //==========
    HeapExtractMax( A, heapsize[A] ) //弹出最大值,T(n)=O(lgn)
        max = A[1] ;
        swap( A[1], A[heapsize[A]] ) ;
        heapsize[A]-- ;
        MaxHeapify( A, 1, heapsize[A] ) ;
        return max ;

    //==========
        HeapInceasingKey( A, i, key ) //增加A[i]的值,并保持堆的性质,T(n)=O(lgn)
            if A[i] >= key
                return ERROR ;
            A[i] = key ;
            while parent[i] > 0     //parent[i] = i/2
                  and A[i] > A[parent[i]]
                  swap( A[i], A[parent[i]] ) ;
                  i = parent[i] ;

    //===========
        MaxHeapInsert( A, key, heapsize[A] ) //再堆的尾部插入key值并保持对的性质,T(n)=O(lgn)
            n = ++heapsize[A] ;
            A[n] = MIN_VALUE ;
            HeapInceasingKey( A, n, key ) ;

    //==========
        BuildMaxHeapWithInsert( A )  //使用 MaxHeapInsert 建堆,T(n)=O(lgn)
            heapsize[A] = 1 ;
            for i = 2 to length[A]
                MaxHeapInsert( A, A[i], heapsize[A] ) ;

快速排序

    QuickSort( A, p, r )    //对数组A[p..r]进行排序
                            //平均性能T(n) = O(lgn)
        if p < r            //最坏情况下T(n) = O(n^2)
            q = Partition( A, p, r ) ;
            QuickSort( A, p, q-1 ) ;
            QuickSort( A, q+1, p ) ;

    /*=================*/
    Partition( A, p, r )
        x = A[r] ;          //划分元素
        i = p - 1 ;
                                        //循环不变式:
        for j = p to r-1                //1. p <= k <= i ==> A[k] <= x
            if( A[j] <= x )             //2. i+1 <= k <= j-1 ==> A[k] > x
                i++ ;                   //3. k == r ==> A[k] = x
                swap( A[i], A[j] ) ;
        swap( A[i+1], A[r] ) ;
        return i+1 ;

快速排序的随机化版本

    RandomizedPartition( A, p, r )
        i = Random( p, r ) ;
        swap( A[i], A[r] ) ;
        return Partition( A, p, r ) ;

    /*=============*/
    RandomizedQuickSort( A, p, r )
        if p < r 
            q = RandomizedPartition( A, p, r ) ;
            RandomizedQuickSort( A, p, q-1 ) ;
            RandomizedQuickSort( A, q+1, r ) ;
  • 使用比较的排序算法的时间下界
    T(n) = O(lgn)

计数排序

    CountingSort( A, B, k )         //数组c记录A中元素最终位置
        n = length[A] ;             //A为输入数组,k表示A中元素是从0到k的整数
                                    //B为排好序的输出数组
        for i = 0 to k
            C[i] = 0 ;

        for i = 1 to n              
            C[A[i]]++ ;             //此时,C记录A中各元素的数量

        for i = 1 to k 
            C[i] += C[i-1] ;        //此时,C记录A中各元素的最终位置

        for i = n down to 1         //使用 i = n down to 1,可以保证A中
            B[C[A[i]]] = A[i] ;     //相等的数载B中的相对位置不变
            C[A[i]]-- ;             //即可以保证排序是稳定的

基数排序

    RadixSort( A, d )           //A中元素都有d位,从低到高为1到d
        for i = 1 to d
            use a STABLE SORT to sort array A on digit i ;

桶排序

    BucketSort( A )         //B为桶数组,B[0..n-1]
        n = length[A] ;     //数组A为 0 <= A[i] < 1
        for i = 1 to n
            insert A[i] into list B[n*A[i]] with InsertionSort ;
        collect the lists B[0..n-1] together in order ;
    //T(n) = O(n)

中位数和顺序统计学

最大值和最小值

    MinMax( A )     //A[1..n]
        n = length[A] ;
        if n % 2 == 0 
            max = A[2] > A[1] ? A[2] : A[1] ;
            min = A[2] > A[1] ? A[1] : A[2] ;
        else
            min = max = A[1] ;

        for i = 3 - ( n % 2 ) ; i <= n-1 ; i += 2       //n为偶数,i从3开始,n为奇数,i从2开始
            if A[i] < A[i+1]
                min = min > A[i] ? A[i] : min ;
                max = max < A[i+1] ? A[i+1] : max ;
            else
                min = min > A[i+1] ? A[i+1] : min ;
                max = max < A[i] ? A[i] : max ;

        return max, min ;

以线性时间找到第i小的值

    RandomizedSelect( A, p, r i )
        while( p < r )
            q = RandomizedPartition( A, p, r ) ;
            k = q - p + 1 ;
            if( k == i ) 
                return A[q] ;
            else if k > i
                r = q - 1 ;
            else 
                p = q + 1 ;
                i = i - k ;

        return A[p] ;      

    /*==================*/
    RandomizedSelect( A, p, r, i )
        if p == r 
            return A[p] ;   //即A[p..r]中只有一个元素,就是要找的元素

        q = RandomizedPartition( A, p, r ) ;
        k = q - p + 1 ;

        if i == k 
            return A[q] ;
        else if i < k 
            return RandomizedSelect( A, p, q-1, i ) ;
        else
            return RandomizedSelect( A, q+1, r, i-k ) ;

    /*
    i 是 A[p..r] 中第i小的元素
    q 是 A[p..r] 中第k = q-p+1小的元素
    当 k = i 时,A[q]即为要找的元素
    当 k > i 时,i问为A[p..q-1]中第i小的元素
    当 k < i 时,即去掉A[p..q],即k个元素,所以i为A[p+1..r]中的第i-k小的元素        
    */