快速排序的分治的两种实现方式
快速排序在数组基本有序和基本逆序的情况下，时间复杂度都是O（n的平方），平均时间复杂度O（nlogn）；空间复杂度为O（1）
1，两个指针分别从前面和后面向中间移动
// 快速排序有两种partition的方式 // 方式一：两个指针从两端向中间靠拢 private int partation1(int[] array, int start, int end) { int i = start; int j = end; int pivot = array[start]; while (i < j) { while (i < j && array[j] > start) { j--; } array[i] = array[j]; i++; while (i < j && array[i] < start) { i++; } array[j] = array[i]; j--; } array[i] = pivot; return i; }
2，两个指针一前一后的从左到右的分治（当然也可以从右向左）
这种方法在其他的题目中也很常见
// 方式二，利用两个指针一前一后向后走 // 前面的指针j每次移动一个位置，一直移动到倒数第二个元素 // 后面的指针i始终指向比pivot大的元素的上一个，如果j元素比pivot小，那么i++，并且与j进行交换 // 使用这种方法的好处是，pivot左侧的元素，其相对位置保持不变 private int partation2(int[] array, int start, int end) { int i = start - 1; int pivot = array[end]; for (int j = start; j <= end - 1; j++) { if (array[j] < pivot) { i++; swap(array, i, j); } } swap(array, i + 1, end); return i + 1; }
两种分治方法，其中第二种能够保证pivot左侧（指针从左向右），后者pivot右侧（指针从右向左）的相对顺序保持不变
快排对于分治的调用实现
// 递归实现快速排序 public void quickSort(int[] array, int start, int end) { if (start >= end) { return; } // int part=partation1(array,start,end); int part = partation2(array, start, end); quickSort(array, start, part - 1); quickSort(array, part + 1, end); }
快排的相关衍生问题（有pivot的快排和0-1判断的快排）
1，这类问题侧重对分治而非递归问题的改进
2，这类问题的考虑，如果分析是抽象的数字问题，还是具体的实体问题。如果是抽象的数字，而且没有其他限制的情况下，往往会有更简单的方法（比如计数排序等），但是如果是实体，或者限制了不能占用额外控件的话，就只能用快排两种实现方法中交换的思路了
3，如果只是少数的几种数字，本质上只是快排次数的问题，标准的快排是递归，一直到区间只剩下一个元素；而对于快排的衍生问题，一般可以抽象为少数几个数字，有n个数字就需要n-1轮快排
快排衍生问题一：
// 将数组中的大写字母与小写字母分开
// 题目描述，一个数组中存储的仅有大写字母与小写字母，编写一个函数对数组中的字母重新排列，让所有的小写字母都在大写字母之前
private boolean isUpper(char c) { return c >='A' && c <= 'Z' ? true : false; } private boolean isLower(char c) { return c >='a' && c <='z' ? true : false; } // 利用快排的思路一，首尾两个指针向中间靠拢 public void zimuPart(char[] charArr, int start, int end) { int i = start; int j = end; while (i < j) { while (i < j && isUpper(charArr[j])) { j--; } while (i < j && isLower(charArr[i])) { i++; } swap(charArr, i, j); } } //利用快排的第二种思路，利用前后两个指针，一个指针始终加加，碰到小写字母的时候和另一个指针进行交换 //另一个指针始终指向大写字母的前面一个 public void zimuPart2(char[] charArr,int start,int end){ int j=start; int i=start-1; for(j=start;j<=end;j++){ if(isLower(charArr[j])){ i++; swap(charArr,i,j); } } } private void swap(char[] charArr, int i, int j) { char tmp = charArr[i]; charArr[i] = charArr[j]; charArr[j] = tmp; }
快排衍生问题二：
//题目描述，给定一个含有n个元素的整形数组a，其中包括0元素和非0元素，对数组进行排序，要求：
//1,排序后所有0元素在前，非0元素在后，且非0元素排序前后相对位置不变
//2,不能使用额外的存储空间
//因为要求不能使用额外的存储空间，因此采用计数排序不太可行 //因为要求相对位置保持不变，因此只能采用快排的思路二，并且指针不应该像之前的从前往后，而应该从后往前 public void set0part(int[] array,int start,int end){ int j=end; int i=end+1; //j在前，i在后 for(j=end;j>=0;j--){ if(array[j]!=0){ i--; swap(array,j,i); } } }
快速排序衍生问题三：
//找出数组中第K小的数，或者找出数组中前K小的数
//最平常的思路是将数组排序，最快的排序是快排，然后返回已排序数组的第k个数，算法时间复杂度为O（nlogn），空间复杂度为O（1）。使用快排的思想，但是每次只对patition之后的数组的一半递归，这样可以将时间复杂度将为O（n）。
public void findKmin(int[] array,int start,int end){ if(start>=end){ return; } int pivot=array[start]; int i=start; int j=end; while(i<j){ while(i<j&&array[j]>=pivot){ j--; } if(i<j){ array[i]=array[j]; i++; } while(i<j&&array[i]<=pivot){ i++; } if(i<j){ array[j]=array[i]; j--; } } array[i]=pivot; //判断找到元素应排的位置和K-1的关系 if(i>kMin-1){ //那么应当在0到i-1之间寻找 findKmin(array,start,i-1); }else if(i<kMin-1){ //应当在i+1到n-1之间寻找 findKmin(array,i+1,end); }else{ //说明i=kMin-1，也即是找到了第i个元素即是倒数第k小的，前面的i个元素就是依次最小的k个 return; } }
这个问题也可以采用堆的方法来解决
堆操作的关键是adjustDown以及adjustUp
对于堆的删除，只能从头部删除。现将第0个元素与最后一个交换，之后删除最后一个，再从第0个元素开始进行一次自上而下的调整
对于堆的插入，只能从尾部进行。将要插入的元素放置到最后一个位置，再对这个元素进行依次自下而上的调整（类似于插入排序）
因此对于这个题：
1）构建一个k个元素的最大堆
2）将数组中k+1...的元素依次和堆顶的元素比较，如果比堆顶的元素小，那么替换掉堆顶元素，并进行依次自上而下的调整