一些高级排序算法的Java实现
1. 快速排序
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，另外其中涉及的分而治之的思想在程序设计中也是一个常用的技巧，因此它是需要认真学习的一个算法重点。快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
1.1 算法分析：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
1.2 快速排序的核心算法
/**
* 快速排序：通过将列表分区，然后对这两个分区进行递归式排序，从而完成对整个列表的排序
* 快速排序的策略：
* 【1】首先，选择一个列表元素作为作为分区元素。
* 【2】分割该列表，使得小于该分区元素的所有元素位于该元素的左边，所有大于该分区元素的元素位于右边。
* 【3】最后，将该快速排序策略（递归式）应用于两个分区。
* @param data
*/
public static <T extends Comparable<? super T>> void quickSort(T[] data) {
quickSortRec(data,0,data.length-1);
}
/**
* 需要使用递归的快速排序
* @param data
* @param begin
* @param end
*/
private static <T extends Comparable<? super T>> void quickSortRec(T[] data,int begin,int end) {
if(begin<end){
//int mid = AdjustArray(data, begin, end);//先成挖坑填数法调整data[]
int mid = partition(data, begin, end);//先成挖坑填数法调整data[]
quickSortRec(data, begin, mid - 1); // 递归调用
quickSortRec(data, mid + 1, end);
}
}
/**
* 挖坑填数的快速排序的实现
* @param data
* @param begin
* @param end
* @return
*/
private static <T extends Comparable<? super T>> int AdjustArray(T[] data,int begin,int end) {
int i = begin, j = end;
T x = data[begin]; //s[l]即s[i]就是第一个坑
///由于是从小到达的排序算法
///因此我们首先找一个比基准小的数放在当前的坑里
while (i < j)
{
//从右向左找小于x的数来填s[i] 这是找小于基准数的过程
while(i < j && data[j].compareTo(x)>0)
j--;
if(i < j)
{
data[i] = data[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
i++;
}
//------------------------------------------------------------------------------//
// 从左向右找大于或等于x的数来填s[j] 这是找大于基准数的过程
while(i < j && data[i].compareTo(x)<0)
i++;
if(i < j)
{
data[j] = data[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
j--;
}
}
//退出时，i等于j。将x填到这个坑中。
data[i] = x;
return i;
}
/**
* 第二种分割方法的实现
* @param data
* @param min
* @param max
* @return
*/
private static <T extends Comparable<? super T>> int partition(T[] data,int min,int max) {
T pa;
int left,right;
int mid = (min+max)/2;
//将中点的data作为分割元素
pa=data[mid];
//将分割元素前置到min处
swap(data,mid,min);
left=min;
right=max;
while(left<right){
while(left<right&&data[left].compareTo(pa)<=0){
left++;
}
while(data[right].compareTo(pa)>0){
right--;
}
if(left<right)
swap(data,left,right);
}
//分割点置回中间位置
swap(data,min,right);
return right;
}2. 归并排序
2.1 归并排序算法
归并排序是另一种递归排序算法，通过将列表递归式分成两半直至每一个列表都只含有一个元素，然后将这些子列表按照顺序重组，这样就完成了对列表的排序。
归并排序算法的总结：递归划分子列表合并的方式，子列表有序，然后归并到一个列表中完成对列表的归并排序。
2.2 归并排序算法实现
/**
* 归并排序：归并排序是另一种递归排序算法，通过将列表递归式分成两半直至每一个列表都只含有一个元素，
* 然后将这些子列表按照顺序重组，这样就完成了对列表的排序。
* 策略：
* 【1】首先将该列表分成两个大约相等的部分
* 【2】对每一个部分列表递归调用其自身，
* 【3】继续该列表的递归分解，直至达到该递归的基本情形，这是该列表被分割成长度为1的列表
* @param data
* @param min
* @param max
*/
public static <T extends Comparable<? super T>> void mergeSort(T[] data,
int min, int max) {
if (min < max) {
int mid = (min + max) / 2;
mergeSort(data, min, mid);
mergeSort(data, mid + 1, max);
merge(data, min, mid, max);
}
}
/**
* Merges two sorted subarrays of the specified array.
*
* @param data the array to be sorted
* @param first the beginning index of the first subarray
* @param mid the ending index fo the first subarray
* @param last the ending index of the second subarray
*/
private static <T extends Comparable<? super T>> void merge(T[] data,
int first, int mid, int last) {
T[] temp = (T[]) (new Comparable[data.length]);
int first1 = first, last1 = mid; // endpoints of first subarray
int first2 = mid + 1, last2 = last; // endpoints of second subarray
int index = first1; // next index open in temp array
// Copy smaller item from each subarray into temp until one
// of the subarrays is exhausted
while (first1 <= last1 && first2 <= last2) {
if (data[first1].compareTo(data[first2]) < 0) {
temp[index] = data[first1];
first1++;
} else {
temp[index] = data[first2];
first2++;
}
index++;
}
// Copy remaining elements from first subarray, if any
while (first1 <= last1) {
temp[index] = data[first1];
first1++;
index++;
}
// Copy remaining elements from second subarray, if any
while (first2 <= last2) {
temp[index] = data[first2];
first2++;
index++;
}
// Copy merged data into original array
for (index = first; index <= last; index++)
data[index] = temp[index];
}3. 快排和归并的区别
快速排序和归并排序有点正好相反的意思。
我们以从小到达排序为例：
【1】快速排序的算法是首先执行找中心点，中间大两边小的分割开，然后不断的将列表规模变小，小的在左，大的在右的原则一直不变。这样慢慢的随着列表越变越小就能够实现全部有序。
【2】归并排序的算法是首先将列表递归的一份为二，知道每一个子列表只有一个元素，然后在就近将两个子列表有序合并，列表规模慢慢扩大，这就实现了局部有序到整体有序的过渡。
【3】总之，二者都是递归排序的有效实现，实质上的区别就是，在两个算法的实现过程中一个是先利用分割点通过比较修改表结构，然后再调用递归方法；另一个是先从分割点实现递归调用，然后通过比较实现有序合并。