P=NP?

Title

第六章 堆排序

MAX-HEAPIFY(A,i):    依次調(diào)整使A[i]為根的子樹成為最大堆，是堆排序的重要子程序；
BUILD-MAX-HEAP(A):
   1.  heap-size[A]    ←   length[A]
   2.  for   i   ←  ⌊length[A]/2⌋   downto   1              //從最后一個節(jié)點的父節(jié)點開始調(diào)整  
   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的時間復(fù)雜度為Ο(nlgn);而且最壞和最佳運行時間都是Ω(nlgn)

最大優(yōu)先級隊列支持的操作:
INSERT(S,x)
MAXIMUM(S):   返回S中具有最大關(guān)鍵字的元素
EXTRACT-MAX(S):   去掉并返回S中的具有最大關(guān)鍵字的元素
INCREASE-KEY(S,x,k):    將元素x的關(guān)鍵字的值增加到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)