快速排序
package changsheng.algorithms.sort;
public class QuickSort {
public static void Sort(int[] a){
Sort(a,0,a.length-1);
}
public static void Sort(int[] a, int low, int high) {
/*实际上不应该选择第一个元素作为pivot,因为第一个元素可能是极值元素,会造成递归解决大量空集*/
/*推荐的pivot应该利用三个元素的中值分割*/
/*1、对第一个元素、中间元素,最后一个元素,进行排序*/
/*2、然后将排好序的三个元素的中间元素与倒数第二个元素进行交换*/
/*另外对于个数较少的元素应该进行插入排序,或者结合堆排序*/
if (low <= high) {
/*先对指定范围内的值进行一次快速过程,再对这次快速过程的结果进行分解递归*/
int mid = Partition(a, low, high);
Sort(a, low, mid - 1);
/*mid位置上的值为键,所以mid-1和mid+1来划分*/
Sort(a, mid + 1, high);
}
}
static private int Partition(int[] a, int low, int high) {
/*以指定范围内数组选中第一个做为pivot*/
int key = a[low];
while (low < high) {
/*从high至low与key进行比较*/
while (low < high && a[high] >= key)
high--;
/*当这个循环结束时,high就是小于key的索引位置*/
/*a[high] < key*/
a[low] = a[high];
/*从high至low与key进行比较*/
while (low < high && a[low] <= key)
low++;
/*当这个循环结束时,high就是小于key的索引位置*/
/*a[low] > key*/
a[high] = a[low];
}
a[low] = key;
return low;
}
}