快速排序的基本思想是:通过一趟排序将待排记录分割成两个独立的部门,其中一部门记录的关键字均比另一部分记录的关键字要小,则可分别对这两部分记录继续进行排序,已达到整个序列有序的目的.
整个排序最核心的部分就是:如何通过一趟排序将待排记录分割成两个独立的部门,这个功能由partition函数实现:partition函数要做的就是,先选取一个关键字(这个关键字的选取很有讲究,直接关心到快速排序的效率),然后想办法把它放到一个合适的位置,使得它左边的数都比它小,而右边的数都比它大.我们称这样的关键字为枢轴.
partition的两种实现如下:
实现一:
public static int partition(int[] data, int start, int end){ int temp = data[start]; // 把第一个数作为基准数 int low = start; int high = end; while(low < high){ while(low<high && data[high]>=temp){ high--; } swap(data, high, low); while(low<high && data[low]<=temp){ low++; } swap(data, low, high); } return low; }实现二:
public static int partition(int[] data, int start, int end){ int index = start; int small = index -1; swap(data, index, end); for(int i=start; i<end; i++){ if(data[i] <= data[end]){ small++; if(small != i){ swap(data, small, i); } } } small++; swap(data, small, end); return small; }两种方法的完整版本如下:
实现一:
package cn.ccnu.sort; public class QuickTwo { public static void quickSort(int[] data, int start, int end){ if(data == null){ throw new RuntimeException("input error"); } if(start < end){ int index = partition(data, start, end); quickSort(data, start, index-1); quickSort(data, index+1, end); } } public static int partition(int[] data, int start, int end){ int temp = data[start]; // 把第一个数作为基准数 int low = start; int high = end; while(low < high){ while(low<high && data[high]>=temp){ high--; } swap(data, high, low); while(low<high && data[low]<=temp){ low++; } swap(data, low, high); } return low; } private static void swap(int[] data, int a, int b) { int temp = data[a]; data[a] = data[b]; data[b] = temp; } public static void main(String[] args) { int[] data = {10, 3, 12, 5, 4, 9, 5, 7, 6}; int start = 0; int end = data.length-1; quickSort(data, start, end); for (int i : data) { System.out.print(i + " "); } } } 实现二:
package cn.ccnu.sort; public class Quick { public static void quickSort(int[] data, int start, int end){ if(data == null){ throw new RuntimeException("input error"); } if(start < end){ int index = partition(data, start, end); quickSort(data, start, index-1); quickSort(data, index+1, end); } } public static int partition(int[] data, int start, int end){ int index = start; int small = index -1; swap(data, index, end); for(int i=start; i<end; i++){ if(data[i] <= data[end]){ small++; if(small != i){ swap(data, small, i); } } } small++; swap(data, small, end); return small; } private static void swap(int[] data, int a, int b){ int temp = data[a]; data[a] = data[b]; data[b] = temp; } public static void main(String[] args) { int[] data = {10, 3, 12, 5, 4, 9, 4, 7, 4}; int start = 0; int end = data.length-1; quickSort(data, start, end); for (int i : data) { System.out.print(i + " "); } } }
