P=NP?

Title

第六章 堆排序

MAX-HEAPIFY(A,i):    依次调整使A[i]为根的子树成为最大堆，是堆排序的重要子程序；
BUILD-MAX-HEAP(A):
   1.  heap-size[A]    ←   length[A]
   2.  for   i   ←  ⌊length[A]/2⌋   downto   1              //从最后一个节点的父节点开始调整  
   3.         do    MAX-HEAPIFY(A,i)

HEAPSORT(A):
    1.    BUILD-MAX-HEAP(A)
    2.    for    i   ←    length[A]   downto   2
    3.           do   exchange    A[1]   ↔   A[i]
    4.                   heap-size[A]  ←   heap-size[A] -1
    5.                   MAX-HEAPIFY(A,1)

HEAPSORT的时间复杂度为Ο(nlgn);而且最坏和最佳运行时间都是Ω(nlgn)

最大优先级队列支持的操作:
INSERT(S,x)
MAXIMUM(S):   返回S中具有最大关键字的元素
EXTRACT-MAX(S):   去掉并返回S中的具有最大关键字的元素
INCREASE-KEY(S,x,k):    将元素x的关键字的值增加到k

HEAP-EXTRACT-MAX(A):   跟堆排序一样
MAX-HEAP-INSERT(A,key): 
 1.  heap-size[A] ←  heap-size[A] + 1
 2.  A[heap-size[A]] ← -∞
 3.  HEAP-INCREASE-KEY(A, heap-size[A] , key)

Title

第七章 快速排序

PARTITION(A,p,r):
 1. x ← A[r]
 2. i ← p-1
 3. for j ←    p to r - 1
 4.       do  if  A[j] £ x
 5.                then  i ← i+1
 6.                         exchange  A[i] ↔ A[j]
 7.  exchange  A[i+1]  ↔ A[r]
 8.  return  i+1

QUICKSORT(A,p,r)
 1. if  p < r
 2.     then q ← PARTITION(A,p,r)
 3.              QUICKSORT(A,p,q-1)
 4.              QUICKSORT(A,q+1,r)










 

求解T(n)=T(ceil(n/2))+1

猜测解为O(lgn)
只需证T(n)<=clg(n-b)。于是T(n)<=clg(ceil(n/2-b))+1
                                                     <=clg(n/2-b+1)+1
                                                      ...
                                                       <=clg(n-b)

 

主方法:

形如T(n)=aT(n/b)+f(n),注意a>=1,b>1
比较f(n)和n^log_ba，则T(n)为较大者，如果f(n)=Q(n^log_ba),则T(n)=Q(n^log_balgn)

简单插入排序:


Insertion-Sort(A):

1.for j = 2 to length[A]
2.   do key=A[j]
3.   //insert A[j] into the sorted sequence A[1..j-1]
4.    i = j-1
5.    while i>0 and A[i]>key
6.    do A[i+1] = A[i]
7.       i = i-1
8.   A[i+1] = key

T(n)=O(n²)   ,稳定，空间为O(1) 

合并排序:

Meger-Sort(A,p,r):

1. if p < r
2.   then q = floor((p+r)/2)
3.       Meger - Sort(A,p,r)
4.       Meger - Sort(A,q+1,r)
5.       Meger(A,p,q,r)

T(n)=O(nlgn),  稳定，空间O(n)