今天来聊聊Java数据结构中关于排序的问题，如题涉及到的有希尔排序，归并排序，快速排序。
希尔排序(Shell Sort)：希尔排序其实就是一种特殊处理过的插入排序，是按指定的间隔增量进行插入排序，所以希尔排序也叫减小间隔增量插入排序。相对于普通的插入排序而言，希尔排序会对排序的过程加以控制，从而避免了一些极端输入情况(如一个倒序输入数列)对于算法运行时间的影响。
归并排序(Merge Sort)：归并排序是通过分治法思想来实现的。通过不断将问题切割成两个规模更小的子问题，知道基本情况(Base Case)，然后将这些子问题的解整合起来合成问题的解。一般情况下归并排序优于希尔排序。
快速排序(Quick Sort)：快速排序也是一种分治思想的体现，快速排序的优点在于他是原址排序的，即不需要额外的空间开销。虽然和归并排序一样，它的算法时间也是theta(nlgn)，但是通常情况下快速排序比归并排序快3倍左右。
最后扯一下“随机化的快速排序”，当快速排序的输入数列是已经排好序的，那么快速排序的效率就会变低。即该算法的运行时间受输入数据的影响，在进行排序之前对输入数据进行一次“随机化”处理可以避免算法运行时间受输入的影响。这样算法的运行时间就是“随机化”后的输入数列的一个概率分布问题。 即“随机化”处理后，我们仍然可能得到一个很差的输入数列，但是这个最差数列出现的概率是很低的。
MergeSort:
package com.wly.algorithmbase.sort;
/**
* 归并排序实现
* @author wly
*
*/
public class MergeSort {
/**
* 以pivot为分割点分成[0,pivot)和[pivot,array.length)两部分进行归并
* @param array
* @param pivot
* @return
*/
public void sort(int[] array,int left,int right) {
if(left == right) {
return ;
}
int pivot = (left+right)/2;
sort(array, left, pivot);
sort(array,pivot+1,right);
merge(array, left, pivot, right);
}
/**
* 合并数组方法一
* 注意：[low,high]不能分割成[low,mid)和[mid,high]
* 因为当low=0,mid=0,high=1时，无法进入循环
* 而分割成[low,mid]和(mid,high]的话，就可以进入循环
*
*/
public void merge(int[] array,int low,int mid,int high) {
int[] tempArray = new int[array.length];
for(int i=0;i
QuickSort:
package com.wly.algorithmbase.sort;
/**
* 快速排序实现
* @author wly
*
*/
public class QuickSort{
public void sort(int[] array,int left,int right) {
if(left >= right) {
return ;
} else {
int pivot = partition(array, left,right);
sort(array,left, pivot-1); //注意-1操作，因为递归求解范围不包括pivot
sort(array,pivot+1,right); //注意+1操作，因为递归求解范围不包括pivot
}
}
/**
* 拆分数组成两个部分，并且以pivot为基准，进行划分
* @param array
*/
private int partition(int[] array,int left,int right) {
//随机生成分割点
int pivot = (int) (Math.random() * (right - left)) + left;
int pValue = array[pivot];
int leftPos = left;
int rightPos = right;
while(leftPos != rightPos) {
while(array[leftPos] < pValue) {
leftPos ++;
}
while(array[rightPos] > pValue) {
rightPos --;
}
exchange(array,leftPos,rightPos);
}
return leftPos;
}
/**
* 交换数组中指定的两个元素
* @param array
* @param x1
* @param x2
*/
public void exchange(int[] array,int x1,int x2) {
int temp = array[x1];
array[x1] = array[x2];
array[x2] = temp;
}
}
ShellSort:
package com.wly.algorithmbase.sort;
/**
* 希尔排序是基于插入排序的，是一种增量递减的插入排序
* 也可以说插入排序是一种增量为1的希尔排序
* @author wly
*/
public class ShellSort {
public void sort(int array[], int interval) {
int temp;
int n = array.length / interval; // 每一分组包含的元素个数
if (n == 1) {
return;
} else {
// 对分组进行插入排序
int j = 1;
while (j < n) {
// 1.保存要排序元素到临时变量
temp = array[j * interval];
for (int k = 0; k < j; k++) {
// 2.寻找插入位置
if (temp <= array[k * interval]) {
// 3.移动插入位置和欲排序元素之间的元素，以腾出位置
for (int m = j; m > k; m--) { // 偶滴神啊，好多i,j,k啊~~~
array[m * interval] = array[(m - 1) * interval];
}
// 4.插入元素
array[k * interval] = temp;
break;
}
}
j++;
}
}
if (interval > 1) {
sort(array, getInterval(interval));
}
}
/**
* 递减增量
* @param interval 当前增量
* @return
*/
private int getInterval(int interval) {
if (interval == 1) {
return 0;
} else {
return (interval / 30) + 1;
}
}
}
测试一下：
package com.wly.algorithmbase.sort;
public class Test {
public static void main(String[] args) {
//1.测试快速排序
System.out.println(--快速排序--);
System.out.pri