算法复习

一、蛮力法

1、选择排序(O(n^2))

算法 SelectionSort(A[0..n-1]) for i<-0 to n-2 do min<-i for j<-i+1 to n-1 do if A[min]>A[j] min<-j swap A[min] and A[i]

2、冒泡排序(O(n^2))

算法 BubbleSort(A[0..n-1]) for i<-n-1 to 1 do for j<-1 to i do if A[j-1]>A[j] swap A[j-1] and A[j] 算法 BubbleSort(A[0..n-1]) for i<-0 to n-2 do for j<-0 to n-2-i do if A[j+1]<A[j] swap A[j] and A[j+1]

二、减治法

1、插入排序(O(n^2))

算法 InsertSort(A[0..n-1]) for i<-1 to n-1 do v<-A[i] j<-i-1 while j>=0 and A[j]>v A[j+1]<-A[j] j<-j-1 A[j+1]<-v

三、分治法

1、合并排序(O(nlogn))

算法 MergeSort(A[0..n-1]) if n>1 copy A[0..⌊n/2⌋-1] to B[0..⌊n/2⌋-1] copy A[⌊n/2⌋..n-1] to C[0..⌈n/2⌉-1] MergeSort(B[0..⌊n/2⌋-1]) MergeSort(C[0..⌈n/2⌉-1]) Merge(B,C,A) 算法 Merge(B[0..p-1],C[0..q-1],A[0..p+q-1]) i<-0;j<-0;k<-0; while i<p and j<q do if B[i]<C[j] A[k]<-B[i];i<-i+1 else A[k]<-C[j];j<-j+1 k<-k+1 if i=p copy C[j..q-1] to A[k..p+q-1] else copy B[i..p-1] to A[k..p+q-1]

2、快速排序(O(nlogn),最坏O(n^2))

算法 QuickSort(A[l..r]) if l<r s=Partition(A[l..r]) QuickSort(A[l..s]) QuickSort(A[s+1..r]) 算法 Partition(A[l..r]) p<-A[l] i<-l;j<-r+1; repeat repeat i<-i+1 until A[i]>=p repeat j<-j-1 until A[j]<=p swap A[i] and A[j] until i>=j swap A[i] and A[j] swap A[l] and A[j] return j

四、变治法

1、堆排序

算法 HeapButtomUp(H[1..n]) for i<-⌊n/2⌋ downto 1 do k<-i;v<-H[k]; heap<-false while not heap and 2*k<=n do j<-2*k if j<n if H[j]<H[j+1] j<-j+1 if v>H[j] heap<-true else H[k]<-H[j];k<-j; H[j]<-v 算法 HeapSort(H[1..n]) for i<-n downto 2 do HeapButtomUp(H[1..i]) exchange H[i] and H[1]