问题一：
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
问题二（荷兰国旗问题）：
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
这就引到了快排的思想。本文叙述一下解决问题二的思路。需要创造两个O(1)辅助空间，一个在数组的开头前一位，一个在数组的最后后一位，这两个辅助空间可以认为一个是小于区域，一个是大于区域，即一个less指针指向arr[-1],一个more指针指向arr[n]。接下来遍历整个数组了，用一个指针cur从arr[0]开始遍历，遇到一个数字arr[i]，如果比num小，则把这个数与小于区域的下一个数交换，同时cur指针后移一位,less指针也后移一位（小于区域扩大一位）；如果比num大，则把这个数与大于区域的上一个数交换，more指针向左移一位（大于区域扩大一位）；如果等于num ，指针cur直接右移一位。当cur指针和more指针相遇时，结束算法。
以下是荷兰国旗问题的代码：
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++;
}
}
//返回重复数组的下标
// 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;
}
快排
经典快排-->随机快排
由于随机快排每次划分的数字都是随机的，属于概率问题，长期期望的时间复杂度是O(nlogn)。
以下介绍随机快排。
随机快排是三种O(nlogn)中最常用的排序，工程上都用它。
对于一个样本状况，想要绕开原本的数据状况，算法研究常规有两种方法：
1.随机。随机选择。
2.哈希。哈希进行打乱。
以下是随机快排的代码：
package Sort;
import java.util.Arrays;
//改进的快排
//改进在原先快排每次只能确定一个位置，使用荷兰国旗问题解决思路，返回等于区域，改进了快排每一次确定了所有等于num的数字。
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);
}
}
//严版教材的快排逻辑是
// 首先定义第一个数是枢值，
// 先从右向左找到第一个小于枢值的数，与枢值进行交换。再从左向右找到第一个大于枢值的数，与刚换过来的小的数进行交换。直到相遇。
//本算法逻辑在荷兰国旗的解决问题上
//less more cur 三个指针
private static int[] partition(int[] arr, int l, int r) {
int less=l-1;
//本算法是将最后一个数字当作枢轴了，小于区域一开始在L-1上，大于区域在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++;
}
}
//让等于区域后的第一个数字与最后一个数字交换
swap(arr,more,r);
//返回等于区域的边界，
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;
}
}
堆排序
堆是什么呢？
首先堆是一颗完全二叉树，分为大根堆和小根堆，大根堆中，每一颗子树最大的节点在根节点上，小根堆中，每一颗子树最小的节点在根节点上；其次，堆保存在数组中，按照某个节点i的左孩子是2*i+1,右孩子是2*i+2，某个节点i的父节点为（i-1）/2。
堆的概念一共分两种介绍。第一种，堆的建立（heapinsert）,往上浮的过程。第二种，堆的调整（heapify），一个数字突然变小了，往下沉的过程。
一个大根堆的建立如下：要插入节点的下标为（index），如果当前节点i上的数字比它的父节点上的数字大，那么两者交换；如果交换了，i再次判断是否比它的父节点大。直至不能交换为止，即终止条件为i节点上的数字小于等于i的父节点上的数字。
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;
}
一个大根堆的调整如下：首先判断待调整节点下标为（index），index的左孩子是否越界（size），
（以下巴拉巴拉一堆操作就是找出 arr[index],arr[2*index+1],arr[2*index+2]这三个数字哪个大的过程，左孩子不存在直接不做如下操作），
在不越界的情况下判断是否有右孩子且右孩子上的数是否大于左孩子上的数，如果不满足上述情况，则设最大的节点是arr[左孩子]；否则最大的节点是arr[右孩子]；
其次判断根节点和最大节点上的数字哪个大，谁大谁在上面；如果最大节点等于根节点，直接跳出；否则进行交换操作；
最后依次循环这个过程。
public static void heapify(int[] arr,int index,int heapSize){
int left=index*2+1;
//不满足条件说明已经是叶节点了
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;
}
}
堆排序就是依次把节点插入堆中（heapinsert），建成一个大根堆后，弹出根上的最大节点和最后的节点交换，size-1，再做调整（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;
//不满足条件说明已经是叶节点了
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;
}
}
