快速排序的分治的两种实现方式
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); }
快排的相关衍生问题
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); } } }
原文：http://www.cnblogs.com/bobodeboke/p/3937880.html
