問題一：
給定一個(gè)數(shù)組arr，和一個(gè)數(shù)num，請(qǐng)把小于等于num的數(shù)放在數(shù)組的左邊，大于num的數(shù)放在數(shù)組的右邊。
要求額外空間復(fù)雜度O(1)，時(shí)間復(fù)雜度O(N)
問題二（荷蘭國旗問題）：
給定一個(gè)數(shù)組arr，和一個(gè)數(shù)num，請(qǐng)把小于num的數(shù)放在數(shù)組的左邊，等于num的數(shù)放在數(shù)組的中間，大于num的數(shù)放在數(shù)組的 右邊。
要求額外空間復(fù)雜度O(1)，時(shí)間復(fù)雜度O(N)
這就引到了快排的思想。本文敘述一下解決問題二的思路。需要?jiǎng)?chuàng)造兩個(gè)O(1)輔助空間，一個(gè)在數(shù)組的開頭前一位，一個(gè)在數(shù)組的最后后一位，這兩個(gè)輔助空間可以認(rèn)為一個(gè)是小于區(qū)域，一個(gè)是大于區(qū)域，即一個(gè)less指針指向arr[-1],一個(gè)more指針指向arr[n]。接下來遍歷整個(gè)數(shù)組了，用一個(gè)指針cur從arr[0]開始遍歷，遇到一個(gè)數(shù)字arr[i]，如果比num小，則把這個(gè)數(shù)與小于區(qū)域的下一個(gè)數(shù)交換，同時(shí)cur指針后移一位,less指針也后移一位（小于區(qū)域擴(kuò)大一位）；如果比num大，則把這個(gè)數(shù)與大于區(qū)域的上一個(gè)數(shù)交換，more指針向左移一位（大于區(qū)域擴(kuò)大一位）；如果等于num ，指針cur直接右移一位。當(dāng)cur指針和more指針相遇時(shí)，結(jié)束算法。
以下是荷蘭國旗問題的代碼：
public static int[] partition(int[] arr,int L,int R,int p){
int less=L-1;
int more=R+1;
while(L<more){
if(arr[L]<p){
// swap(arr,less+1,L);
// less++;
// L++;
swap(arr,++less,L++);
}else if(arr[L]>p){
swap(arr,--more,L);
}else {
L++;
}
}
//返回重復(fù)數(shù)組的下標(biāo)
// return new int[]{less+1,more-1};
return arr;
}
private static void swap(int[] arr,int i, int j) {
// arr[i]=arr[i]^arr[j];
// arr[j]=arr[i]^arr[j];
// arr[i]=arr[i]^arr[j];
//自己和自己交換是0？？？？
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
快排
經(jīng)典快排-->隨機(jī)快排
由于隨機(jī)快排每次劃分的數(shù)字都是隨機(jī)的，屬于概率問題，長(zhǎng)期期望的時(shí)間復(fù)雜度是O(nlogn)。
以下介紹隨機(jī)快排。
隨機(jī)快排是三種O(nlogn)中最常用的排序，工程上都用它。
對(duì)于一個(gè)樣本狀況，想要繞開原本的數(shù)據(jù)狀況，算法研究常規(guī)有兩種方法：
1.隨機(jī)。隨機(jī)選擇。
2.哈希。哈希進(jìn)行打亂。
以下是隨機(jī)快排的代碼：
package Sort;
import java.util.Arrays;
//改進(jìn)的快排
//改進(jìn)在原先快排每次只能確定一個(gè)位置，使用荷蘭國旗問題解決思路，返回等于區(qū)域，改進(jìn)了快排每一次確定了所有等于num的數(shù)字。
public class QuickSort {
public static void quickSort(int[] arr){
if(arr==null||arr.length<2){
return;
}
quickSort(arr,0,arr.length-1);
}
private static void quickSort(int[] arr, int l, int r) {
if (l<r){
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p=partition(arr,l,r);
quickSort(arr,l,p[0]-1);
quickSort(arr,p[1]+1,r);
}
}
//嚴(yán)版教材的快排邏輯是
// 首先定義第一個(gè)數(shù)是樞值，
// 先從右向左找到第一個(gè)小于樞值的數(shù)，與樞值進(jìn)行交換。再從左向右找到第一個(gè)大于樞值的數(shù)，與剛換過來的小的數(shù)進(jìn)行交換。直到相遇。
//本算法邏輯在荷蘭國旗的解決問題上
//less more cur 三個(gè)指針
private static int[] partition(int[] arr, int l, int r) {
int less=l-1;
//本算法是將最后一個(gè)數(shù)字當(dāng)作樞軸了，小于區(qū)域一開始在L-1上，大于區(qū)域在R上。
int more=r;
int cur=l;
while(cur<more){
if(arr[cur]<arr[r]){
swap(arr,++less,cur++);
}else if(arr[cur]>arr[r]){
swap(arr,--more,cur);
}else{
cur++;
}
}
//讓等于區(qū)域后的第一個(gè)數(shù)字與最后一個(gè)數(shù)字交換
swap(arr,more,r);
//返回等于區(qū)域的邊界，
return new int[]{less+1,more};
}
private static void swap(int[] arr, int i, int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
堆排序
堆是什么呢？
首先堆是一顆完全二叉樹，分為大根堆和小根堆，大根堆中，每一顆子樹最大的節(jié)點(diǎn)在根節(jié)點(diǎn)上，小根堆中，每一顆子樹最小的節(jié)點(diǎn)在根節(jié)點(diǎn)上；其次，堆保存在數(shù)組中，按照某個(gè)節(jié)點(diǎn)i的左孩子是2*i+1,右孩子是2*i+2，某個(gè)節(jié)點(diǎn)i的父節(jié)點(diǎn)為（i-1）/2。
堆的概念一共分兩種介紹。第一種，堆的建立（heapinsert）,往上浮的過程。第二種，堆的調(diào)整（heapify），一個(gè)數(shù)字突然變小了，往下沉的過程。
一個(gè)大根堆的建立如下：要插入節(jié)點(diǎn)的下標(biāo)為（index），如果當(dāng)前節(jié)點(diǎn)i上的數(shù)字比它的父節(jié)點(diǎn)上的數(shù)字大，那么兩者交換；如果交換了，i再次判斷是否比它的父節(jié)點(diǎn)大。直至不能交換為止，即終止條件為i節(jié)點(diǎn)上的數(shù)字小于等于i的父節(jié)點(diǎn)上的數(shù)字。
public static void heapInsert(int[] arr,int index){
while (arr[index]>arr[(index-1)>>1]){
swap(arr,index,(index-1)>>1);
index=(index-1)>>1;
}
一個(gè)大根堆的調(diào)整如下：首先判斷待調(diào)整節(jié)點(diǎn)下標(biāo)為（index），index的左孩子是否越界（size），
（以下巴拉巴拉一堆操作就是找出 arr[index],arr[2*index+1],arr[2*index+2]這三個(gè)數(shù)字哪個(gè)大的過程，左孩子不存在直接不做如下操作），
在不越界的情況下判斷是否有右孩子且右孩子上的數(shù)是否大于左孩子上的數(shù)，如果不滿足上述情況，則設(shè)最大的節(jié)點(diǎn)是arr[左孩子]；否則最大的節(jié)點(diǎn)是arr[右孩子]；
其次判斷根節(jié)點(diǎn)和最大節(jié)點(diǎn)上的數(shù)字哪個(gè)大，誰大誰在上面；如果最大節(jié)點(diǎn)等于根節(jié)點(diǎn)，直接跳出；否則進(jìn)行交換操作；
最后依次循環(huán)這個(gè)過程。
public static void heapify(int[] arr,int index,int heapSize){
int left=index*2+1;
//不滿足條件說明已經(jīng)是葉節(jié)點(diǎn)了
while (left< heapSize){
int largest=left+1< heapSize &&arr[left+1]>arr[left]? left+1:left;
largest=arr[largest]>arr[index]?largest:index;
if(largest==index){
break;
}
swap(arr,largest,index);
index=largest;
left=index*2+1;
}
}
堆排序就是依次把節(jié)點(diǎn)插入堆中（heapinsert），建成一個(gè)大根堆后，彈出根上的最大節(jié)點(diǎn)和最后的節(jié)點(diǎn)交換，size-1，再做調(diào)整（heapify）。
package Sort;
import java.util.Arrays;
public class HeapSort {
public static void heapSort(int[] arr){
if (arr==null||arr.length<2){
return;
}
for (int i=0;i< arr.length;i++){
heapInsert(arr,i);
}
int heapSize=arr.length;
swap(arr,0,--heapSize);
while(heapSize>0){
heapify(arr,0, heapSize);
swap(arr,0,--heapSize);
}
}
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 index,int heapSize){
int left=index*2+1;
//不滿足條件說明已經(jīng)是葉節(jié)點(diǎn)了
while (left< heapSize){
int largest=left+1< heapSize &&arr[left+1]>arr[left]? left+1:left;
largest=arr[largest]>arr[index]?largest:index;
if(largest==index){
break;
}
swap(arr,largest,index);
index=largest;
left=index*2+1;
}
}
public static void swap(int[] arr,int i,int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
