一、荷兰国旗问题

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边（可无序），等于num的放中间，大于num的放在数组右边。

要求：空间复杂度O(1)，时间复杂度O(N)

    public static void sortnum(int[] arr,int num){
    	//small、big分别指向数组的最-1和arr.length的下标，使用current变量作为遍历数组的下标
        int small=-1;
        int big=arr.length;
        int current=0;
        //arr[cuurrent]<num时current和++small交换,current++
        while(current!=big) {
            if (arr[current]<num){
                swap(arr,++small,current++);
            }
            //arr[cuurrent]==num;不做任何处理，current++继续向右遍历
            else if (arr[current]==num){
                current++;

            }
            //arr[cuurrent]>num时current和--big交换，current不移动，
            else if(arr[current]>num){
                swap(arr,--big,current);
            }
        }
    }
    public static  void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

二、快速排序

①快排1.0，时间复杂度O(N²)

取数组最后一个数num，根据这个num，把数组分成两边，左边是≤num的，右边是＞num的

然后将num插入到≤中最后一个数后，即num的位置确定了

再将左右两边的区域重复上面两步操作，最后全有序（一次确定一个元素的位置）

②快排2.0，时间复杂度O(N²)，基于荷兰国旗问题优化

取数组最后一个数（如最后一个数为5），将数组分成<、=、>三个区域

当排好序后将num和>num的第一个数交换，中间就确定了一批=num的数

最后左右<区和>区的数组继续递归上述过程，最后全部有序（一次确定一批元素）

③快排3.0，时间复杂度O(N*logN)

因为快排的划分值（partition）决定了其时间负责度，只有partition值刚好是整个数组的中间值时时间复杂度才为O(N*logN）

如果将partition值换成数组中随机一个数来划分，那么所有划分情况就会变成等概率事件，求数学期望后，时间复杂度就会变成O(N*logN)，这就是快排3.0

public static quickSort(int[] arr){
	if(arr == null || arr.length < 2){
		return;
	}
	quickSort(arr, 0, arr.length-1);
}
punlic static 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);
	}
}
public static int[] partition(int[] arr, int L, int R){
	int less = L-1;
	int more = R;
	while(L < more){
		if(arr[L] < arr[R]){
			swap(arr, ++less, L++);
		}else if(arr[L] > arr[R]){
			swap(arr, --less, L++);
		}else{
			L++;
		}
	}
	swap(arr, more, R);
	return new int[] {less+1, more};
}
	
		

三、堆排序

①什么是堆结构：完全二叉树

（节点一点是按顺序来的，不能没有右孩子而有左孩子）

②对于连续的数组可以变成完全二叉树

i的左孩子下标：2*i+1

i的右孩子下标：2*i+2

i的父节点的下标：(i-1)/2 （向下取整）

③大根堆和小根堆

大根堆：在完全二叉树里，每一棵子树的头节点为最大值

小根堆：在完全二叉树里，每一棵子树的头节点为最小值

④向上保持堆结构(HeapInsert):向一个位置插入一个数，仍能保持堆结构

	//时间复杂度O(logN)
	public static void heapInsert(int[] arr, int index){
		//当插入的数大于其父节点，就交换位置
		while(arr[index] > arr[(index-1)/2]{
			swap(arr, index, (index-1)/2);
			//index标志位上升到父节点的位置，继续向上判断
			index = (index-1)/2;
		}
	}

⑤向下保持堆结构(Heapify)：获取某个数的index位置，取走这个数后，仍保持堆结构

	//时间复杂度O(logN)
	public static void heapify(int[] arr, int index, int heapSize){
		//获取插入位置的左节点位置
		int left = index*2+1;
		//如果左节点位置不超过堆长度，即存在左节点
		while(left < heapSize){
			//先比较子树左右节点的大小，获取左右节点中最大值的下标
			int largest = left + 1 && arr[left+1] > arr[left] ? left+1 : left;
			//再用左右节点的最大值和插入的值来比较，得到整棵子树的最大值
			largest = arr[largest] > arr[index] ? largest : index;
			//如果最大值为父节点，直接break，不用交换
			if(largest == index){
				break;
			}
			//交换子树中的最大值到父节点上
			swap(arr, largest, index);
			//index标志位移到左右节点中最大的那个上
			index = largest;
			//更新index位置的左节点的位置，继续向下比较，循环继续
			left = index*2+1;
		}
	}

⑥堆排序

	//时间复杂度O(N*logN)
	public static void heapSort(int[] arr){
		if(arr == null || arr.length < 2){
			return;
		}
		
		//从叶子节点开始建立大根堆，O(N)
		for(int i = arr.length-1; i >= 0; i--){
			heapify(arr, i, arr.length);
		}
		//还可以用heapInsert插入元素,O(N*logN)
		//for(int i=0; i < arr.length; i++){//O(N)
			heapInsert(arr, i);//O(logN)
		  }
		
		//堆长度等于数组长度
		int heapSize = arr.legnth;
		//将大根堆顶的元素交换到堆末尾，堆长度减一
		swap(arr, 0, --heapSize);
		//堆长度大于0时，持续将堆顶元素放到堆末尾，并且堆长度减一，一次交换确定一个数的位置，最后得到一个升序数组
		while(heapSize > 0){
			//从堆顶开始向下保持堆结构
			heapify(arr, 0, headSize);
			//交换堆顶元素到交换到当前堆的末尾，堆长度减一
			swap(arr, 0, --heapSize);
		}
	}

⑦堆排序的扩展题

已知一个几乎有序的数组（几乎有序指如果把数组排好顺序的话，每个元素移动的距离可以不超过k，且k相对于数组来说比较小），请将这个数组排好序

//如 k=6
//先遍历一遍数组的前7个数建立小根堆
//因为每个元素移动距离都不会超过6，所以小根堆里最小的数一定是整个数组最小的数，可以放心从0位置弹出，后面最小的数也只能从1位置弹出
//继续从数组中按顺序放前7个元素进小根堆，排序后，最小值弹出
//重复过程至全部元素有序
//时间复杂度O(N*logk)
public void sortedArrDistanceLessK(int[] arr, int k){
	//优先级队列默认是小根堆，扩容时时间复杂度为O(logN),但不能轻易操作单独元素，因为是定好的结构，可以理解为一个黑盒
	PriorityQueue<Integer> heap = new PriorityQueue<>();
	int index = 0;
	//首先前k个元素放进小跟堆里
	for(;index < Math.min(arr.length,k); index++){
		heap.add(arr[index]);
	}
	int i = 0;
	for(;index < arr.length; i++, index++){
		//再继续从数组中按顺序添加元素进小根堆
		head.add(arr[index]);
		//每次弹出小根堆的堆顶元素到数组的i位置
		arr[i] = heap.poll();
	}
	//当元素全部加入小根堆后，继续弹出最小值到数组的i位置，直到堆为空结束
	while(!heap.isEmpty()){
		arr[i++] = heap.poll();
	}