快速排序
荷蘭國旗問題(Dutch National Flag Problem)
給定一個數(shù)組arr油狂，和一個數(shù)num;
請把小于等于num的數(shù)放在數(shù)組的左邊，大于num的數(shù)放在數(shù)組的右邊。
要求額外空間復(fù)雜度O(1)粪糙，時間復(fù)雜度O(N)
思路：
給定一個無序數(shù)組[4,5,6,7,2,1,9,8]，num為5
使用一個變量p來劃分小于等于num的范圍忿项，剛開始p=-1表示這個范圍不存在猜旬。
遍歷數(shù)組，當出現(xiàn)小于等于num的數(shù)后倦卖，當前遍歷到的數(shù)字與p的下一個數(shù)字發(fā)生交換，p加1
本示例中遍歷到數(shù)組的第一個數(shù)小于num椿争，所以當前數(shù)字和p的下一個位置的數(shù),即自己交換怕膛。后續(xù)過程省略，代碼如下：
public class Patition {
public static void patition(int []arr,int num){
if(arr == null)
return;
int p = -1;
for(int i = 0;i<arr.length;i++){
if(arr[i]<=num)
swap(arr,i,++p);
}
return ;
}
public static void swap(int []arr,int i,int j){
if(arr == null || i == j)
return;
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
}
問題的升級：(荷蘭國旗問題)Dutch National Flag Problem
給定一個整數(shù)數(shù)組秦踪，給定一個值K褐捻，這個值在原數(shù)組中一定存在;
要求把數(shù)組中小于K的元素放到數(shù)組的左邊掸茅，大于K的元素放到數(shù)組的右邊，等于K的元素放到數(shù)組的中間;
最終返回一個整數(shù)數(shù)組柠逞，其中只有兩個值昧狮，分別是等于K的數(shù)組部分的左右兩個下標值。
例如:
給定數(shù)組：[2, 3, 1, 9, 7, 6, 1, 4, 5]板壮，給定一個值4,
那么經(jīng)過處理原數(shù)組可能得一種情況是：[2, 3, 1, 1, 4, 9, 7, 6, 5].
需要注意的是逗鸣，小于4的部分不需要有序，大于4的部分也不需要有序绰精，返回等于4部分的左右兩個下標撒璧，即[4, 4]
荷蘭國旗問題較上問題增加了對等于區(qū)域劃分的判斷，在算法的思路上笨使，我們可以再使用一個變量來跟蹤大于num的區(qū)域：
num為5卿樱，當遍歷到5時，p1與p2不發(fā)生變化硫椰，小于與大于區(qū)域不發(fā)生擴張繁调；遍歷到大于num的數(shù)時，當前遍歷的數(shù)與p2前的數(shù)發(fā)生交換靶草，p2減1蹄胰，表示大于num的數(shù)擴張了一個單位，并且遍歷的索引停止：
遍歷到了數(shù)組的arr[2]爱致，發(fā)生交換后烤送，繼續(xù)判斷arr[2]位置的數(shù)(8)與num的大小，直到當前遍歷到的index與p2“相撞”后,停止糠悯。后續(xù)過程省略,代碼如下:
public class DutchNationalFlag {
public static int[] partition(int []arr,int L,int R,int num){
if(arr == null)
return null;
int p1 = L - 1;
int p2 = R + 1;
int curIndex = L;
while(curIndex < p2){
if(arr[curIndex] < num){
swap(arr,curIndex++,++p1);
}else if(arr[curIndex] == num){
curIndex++;
}else{
swap(arr,curIndex,--p2);
}
}
return new int[]{++p1,--p2};
}
public static void swap(int[] arr,int i,int j){
if(arr == null || i == j)
return;
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
}
經(jīng)典快排與改進
經(jīng)典快排
經(jīng)典快排的思路即：partition+recursion
partition選擇數(shù)組的最后一個數(shù)為參考值帮坚，將小于等于該數(shù)字的數(shù)羅列到左邊，該數(shù)字放在中間互艾，大于這個數(shù)的數(shù)羅列到該數(shù)字的右邊试和，然后對該數(shù)字左邊的數(shù)和右邊的數(shù)進行遞歸，完成排序纫普。經(jīng)典快排以及測試代碼如下：
import java.util.Arrays;
public class ClassicQuickSort {
public static void quickSort(int [] arr){
sort(arr,0,arr.length-1);
}
public static void sort(int []arr,int L,int R){
if(L < R){
int mid = partition(arr,L,R);
sort(arr,L,mid-1);
sort(arr,mid+1,R);
}
}
public static int partition(int []arr,int L,int R){
int p = L-1;
for(int i = L;i<R+1;i++){
if(arr[i]<=arr[R])
swap(arr,i,++p);
}
return p;
}
public static void swap(int []arr,int i,int j){
if(arr == null || i == j)
return;
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
// test:comparator
public static void comparator(int []arr){
Arrays.sort(arr);
}
// test :printer
public static void printArray(int[]arr){
if(arr == null)
return;
for(int i = 0;i<arr.length;i++){
System.out.print(arr[i]+ " ");
}
System.out.println();
}
// test: copier
public static int[] copier(int []arr){
if(arr == null)
return null;
int [] copyArr = new int[arr.length];
for(int i = 0;i<arr.length;i++){
copyArr[i] = arr[i];
}
return copyArr;
}
// test: generateRandomArray
public static int[] generateRandomArray(int maxSize,int maxValue){
int size = (int)((maxSize+1)*Math.random());
int[] arr = new int[size];
for(int i = 0;i<size;i++){
// (-maxValue,maxValue)
arr[i] = (int)((maxValue+1)*(Math.random()) - maxValue*Math.random());
}
return arr;
}
// test: isEqual
public static boolean isEqual(int[] arr1, int[] arr2){
if(arr1 != null&& arr2 == null || arr2 != null && arr1 == null)
return false;
if(arr1.length != arr2.length)
return false;
if(arr1 == null && arr2 == null)
return true;
for(int i = 0;i<arr1.length;i++){
if(arr1[i] != arr2[i])
return false;
}
return true;
}
public static void main(String[]args){
int testTime = 5000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for(int i = 0;i<testTime;i++){
int [] arr1 = generateRandomArray(maxSize,maxValue);
int [] arr2 = copier(arr1);
quickSort(arr1);
comparator(arr2);
if(!isEqual(arr1,arr2)){
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed?"Nice":"Wrong");
}
}
改進快排
經(jīng)典快排的問題是阅悍，每次只能排出一個數(shù)字，partition過程中是將num這個數(shù)字與小于等于區(qū)域和大于區(qū)域進行劃分昨稼，如果有多個和num相等的數(shù)字节视，那么排序效率會變得十分低，由荷蘭國旗問題的思考總結(jié)假栓，我們可以進一步將快排進行優(yōu)化改進寻行。將partition過程變?yōu)閷?shù)組劃分為小于區(qū)域，等于區(qū)域以及大于區(qū)域匾荆，然后對小于區(qū)域和大于區(qū)域再進行partition的遞歸拌蜘。代碼如下杆烁，省略測試代碼：
public class QuickSort {
public static void quickSort(int[] arr){
sort(arr,0,arr.length-1);
}
public static void sort(int[] arr,int L,int R){
if(L < R){
int [] indexArr = partition(arr,L,R);
sort(arr,L,indexArr[0]-1);
sort(arr,indexArr[1]+1,R);
}
}
public static int[] partition(int[] arr,int L,int R){
int p1 = L - 1;
int p2 = R ;
int curIndex = L;
while(curIndex < p2){
if(arr[curIndex] < arr[R]){
swap(arr,curIndex++,++p1);
}else if(arr[curIndex] > arr[R]){
swap(arr,curIndex,--p2);
}else{
curIndex++;
}
}
swap(arr,p2,R);
return new int[]{++p1,--p2};
}
public static void swap(int[] arr,int i,int j){
if(arr == null || i == j)
return;
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
}
快排時間復(fù)雜度與額外空間復(fù)雜度分析
快排的時間復(fù)雜度與數(shù)據(jù)狀況有關(guān)，一個有序的數(shù)組[0,1,2,3,4,5,6,7],如果使用快排排序简卧，那么狀況就是最差的兔魂。但是如果每次參考的基準數(shù)都能把數(shù)組均分成兩部分那么我們就可以按照master公式來計算時間復(fù)雜度：T(N) = a*T(N/b) + O(N^d).快排分為兩個子過程遞歸，除去遞歸外partition的時間復(fù)雜度為O(N),所以其時間復(fù)雜度為O(N^d * logN)即：O(NlogN)举娩。但是如何使基準數(shù)能夠?qū)?shù)組均分成兩坨呢析校？為了解決這個問題，我們可以打亂當前的數(shù)據(jù)狀況晓铆，sort部分的代碼改動如下：
public static void sort(int[] arr,int L,int R){
if(L < R){
swap(arr,L+(int)((R-L+1)*Math.random()),R);// 隨機讓任意位置的數(shù)與基準數(shù)位置R的數(shù)調(diào)換
int [] indexArr = partition(arr,L,R);
sort(arr,L,indexArr[0]-1);
sort(arr,indexArr[1]+1,R);
}
}
通過添加一句代碼勺良，就可以讓未知狀況的數(shù)組取基準數(shù)，轉(zhuǎn)換成一個概率問題骄噪，通過長期數(shù)學期望最終計算得到隨即快速排序的時間復(fù)雜度為O(NlogN)尚困。
隨機快速排序的額外空間復(fù)雜度為O(logN),原因在于，partition最后要返回一個數(shù)組來記錄與基準數(shù)相等的區(qū)域索引范圍链蕊，這樣的額外數(shù)組量為一個二叉樹的高度即logN事甜。
堆排序
最大堆與最小堆
滿二叉樹
什么是滿二叉樹？國內(nèi)定義如果一個二叉樹的層數(shù)為K,且節(jié)點的總數(shù)是2^K-1,那么這棵樹就是一個滿二叉樹滔韵，示例：
完全二叉樹
節(jié)點從左至右依次排布的樹就是完全二叉樹逻谦，示例：
堆
堆是一種完全二叉樹，分為最大堆(大根堆)和最小堆(小根堆)陪蜻。當父節(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大堆邦马，反之，當父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆宴卖。示例：
最大堆或最小堆的子樹仍然是最大堆或最小堆滋将。
heapInsert與heapify
heapInsert 與 heapify是堆結(jié)構(gòu)中重要的兩個方法。
heapInsert
heapInsert顧名思義症昏，是向堆中插入節(jié)點随闽，插入節(jié)點后，要判斷該節(jié)點與其父節(jié)點的大小肝谭，如果大于父節(jié)點掘宪，那么則插入的節(jié)點與父節(jié)點交換位置，并繼續(xù)向上判斷攘烛，直到小于等于父節(jié)點為止魏滚。一個節(jié)點的父節(jié)點的索引為(index-1)/2。
public static void heapInsert(int[] arr,int index){
while(arr[index] > arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index = (index-1)/2;
}
}
public static void swap(int[] arr,int i,int j){
if(arr == null || i == j)
return;
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
heapify
heapify的作用舉例：
假設(shè)有一個流坟漱，它源源不斷向外吐出數(shù)字栏赴，這些數(shù)字是沒有規(guī)律的；
現(xiàn)在希望你設(shè)計一種數(shù)據(jù)結(jié)構(gòu)，可以快速地收集并獲取吐出所有數(shù)字的中位數(shù)
如果你用一個數(shù)組去接收流吐出的數(shù)字须眷，那么收集流吐出的數(shù)字很簡單，但是如果要獲取中位數(shù)的話就要對數(shù)組進行一次排序沟突，如果要求流每次吐出一個數(shù)字就獲取一次中位數(shù)花颗，那么就要頻繁地對數(shù)組進行排序操作。解決的方法就是使用堆結(jié)構(gòu)來解決這個問題：設(shè)計一個最大堆惠拭，和一個最小堆扩劝，每次流吐出數(shù)字的時候都和最大堆的堆頂作比較，如果小于等于最大堆堆頂就放入最大堆职辅，如果大于最大堆的堆頂則放入最小堆棒呛，入堆這個操作就是heapInsert。同時我們還需要保證最大堆的數(shù)據(jù)量不能比最小堆中的數(shù)據(jù)量大超過1域携，反之亦是如此/也就是要保持最大堆數(shù)據(jù)量N和最小堆的數(shù)據(jù)量M的關(guān)系為 |N-M| <= 1,如何保持這種關(guān)系呢簇秒？一旦破壞了這種關(guān)系的平衡，我們就讓最大堆的頂部或者最小堆的頂部彈出秀鞭，讓這個最大的數(shù)字進入到最小堆里面趋观，或者是讓最小堆的最小的數(shù)字insert到最大堆里面，如圖示意：
假設(shè)這個數(shù)據(jù)流吐出的數(shù)字依次是 5->6->4->7->3->8->1
左側(cè)為最大堆數(shù)字數(shù)量為N锋边，右側(cè)為最小堆數(shù)字數(shù)量為M,沒有破壞過 |N-M| <= 1的規(guī)定皱坛，如果這個時候數(shù)據(jù)流吐出的數(shù)字為0，那么就要heapInsert到最大堆里面豆巨，這個時候N-M = 2破壞了兩堆數(shù)量上的平衡剩辟，所以要把最大堆的堆頂彈入到最小堆中去，操作如下：
首先將數(shù)字0 heapInsert到最大堆中
交換最大堆首尾數(shù)字
將最大堆末尾數(shù)字(5) heapInsert到最小堆
接下來就是heapify操作了往扔，對最大堆中的堆頂0進行heapify,首先要判斷它的兩個孩子誰更大贩猎，誰大跟誰交換，直到滿足最大堆的結(jié)構(gòu)為止
heapify的代碼如下：
public static void heapify(int[] arr,int heapSize,int index){
int leftIndex = 2*index+1;
while(leftIndex < heapSize){
int largestIndex = leftIndex+1<heapSize && arr[leftIndex]<arr[leftIndex+1]?leftIndex+1:leftIndex;
largestIndex = arr[index]>arr[largestIndex]?index:largestIndex;
if(largestIndex != index){
swap(arr,index,largestIndex);
index = largestIndex;
leftIndex = largestIndex*2+1;
}else {
break;
}
}
}
arr代表最大堆的數(shù)據(jù)瓤球，heapSize為最大堆數(shù)字的個數(shù)融欧，index代表對哪個索引的數(shù)字進行heapify
堆排序
堆排序的思路就是對數(shù)組中的每個數(shù)字進行heapInsert操作，然后置換堆頂和堆末的數(shù)字卦羡，交換之后噪馏，最大的數(shù)字就排序好了，這時heapSize-1绿饵，然后對heapSize-1的這個堆的堆頂進行heapify,heapify操作后欠肾，這個heapSize-1的堆再次變?yōu)樽畲蠖眩缓笤僦脫Q堆頂和堆末的數(shù)字拟赊，排出最大數(shù)字......代碼如下：
public class HeapSort {
public static void heapSort(int[] arr){
// 形成最大堆
for(int i = 0;i<arr.length;i++){
heapInsert(arr,i);
}
int heapSize = arr.length;
while(heapSize > 0){
swap(arr,0,heapSize-1);
heapSize--;
heapify(arr,heapSize,0);
}
}
public static void swap(int[] arr,int i,int j){
if(arr == null || i == j)
return;
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
public static void heapInsert(int[] arr,int index){
while(arr[index] > arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index = (index-1)/2;
}
}
public static void heapify(int[] arr,int heapSize,int index){
int leftIndex = 2*index+1;
while(leftIndex < heapSize){
int largestIndex = leftIndex+1<heapSize && arr[leftIndex]<arr[leftIndex+1]?leftIndex+1:leftIndex;
largestIndex = arr[index]>arr[largestIndex]?index:largestIndex;
if(largestIndex != index){
swap(arr,index,largestIndex);
index = largestIndex;
leftIndex = largestIndex*2+1;
}else {
break;
}
}
}
}
堆排序heapInsert花費的時間為log1+log2+log3+log4...+logN刺桃；heapify的操作也是相當于每個元素依次遍歷二叉樹的高度，因為有O(log1+log2+...+logn)=O(log(n!))=O(nlogn)所以堆排序的時間復(fù)雜度為O(NlogN)吸祟，且堆排序的額外空間復(fù)雜度為O(1)瑟慈。
