java排序算法（二）
二、改进排序算法
2.1希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
常用的h序列（增量）由Knuth提出，该序列从1开始，通过如下公式产生：h = 3 * h +1
反过来程序需要反向计算h序列，应该使用h=(h-1)/3
2.2快速排序
定义：快速排序（Quicksort）是对冒泡排序的一种改进，是一种非稳定排序。
快速排序通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
2.3归并排序
定义：归并排序（MergeSort）是建立在归并操作上的一种有效的排序算法，该算法是分治法的典型应用。是稳定排序。
归并排序假设初始序列（数据）有n个记录，看作n个子序列，每个子序列长度为一，然后进行两两归并，得到n/2个长度为2的子序列；让后再两两归并，...，重复操作，最后得到一个长度为n的有序序列，这种方法称为2路归并排序。
代码如下
public class Sort
{
//实现从小到大排序
public static void main(String[] args)
{
int[] arr1 = {9,1,5,8,3,7,4,6,2};
//quickSort(arr1,0,8);
mergeSort(arr1);
//shellSort(arr1);
for(int i=0;i<arr1.length;i++)
{
System.out.println(arr1[i]);
}
}
/*---------------------------------希尔排序---------------------------------------------
*希尔排序（缩小增量排序）,对直接插入排序的改进
*通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大框度的移动
*当这些数据项排过一趟序之后，希尔排序算法见效数据项的间隔再进行排序，依次进行下去
*哦爱心时的数据项之间的间隔被称为增量，习惯上用h表示
*常用h序列由Knuth剔除，序列从1开始，通过公式产生h=3*h+1；
*反过来程序反向计算h=（h-1）/3
---------------------------------------------------------------------------------------*/
public static void shellSort(int[] data)
{
int h=1;
while(h<=data.length/3)
{
h=h*3+1;
}
while(h>0)
{
for (int i = h; i < data.length; i += h)
{
if (data[i] < data[i - h])
{
int tmp = data[i];
int j = i - h;
while (j >= 0 && data[j] > tmp)
{
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
//print(data);
}
}
// 计算出下一个h值(增量)
h = (h - 1) / 3;
}
}
/*---------------------------------快速排序---------------------------------------------
-----------------------------------------------------------------------------------*/
public static void quickSort(int[] arr,int low,int high)
{
if(low<high)
{
int mid = getMid(arr,low,high);
quickSort(arr,0,mid-1); //递归排序
quickSort(arr,mid+1,high);
}
}
//取中值
public static int getMid(int[] arr,int low,int high)
{
int key = arr[low]; //基准元素
while(low<high)
{
while(low<high&&arr[high]>=key) //从high开始找比基准小的元素，如果找到，则互换位置
{
high--;
}
arr[low] = arr[high];
while(high>low&&arr[low]<=key) //从low开始找比基准大的，放到之前high空出的位置上
{
low++;
}
arr[high]=arr[low];
}
arr[low]=key; //此时low=high是基准元素的位置，也是空出来的那个位置
return low;
} /*--------------------------------归并排序------------------------------------
-------------------------------------------------------------------------------*/
public static void mergeSort(int[] data)
{
sort(data,0,data.length-1);
}
public static void sort(int[] data,int left,int right)
{
if(left>=right)
{
return;
}
int center = (left + right) / 2; // 找出中间索引
sort(data, left, center); // 对左边数组进行递归
sort(data, center + 1, right); // 对右边数组进行递归
merge(data, left, center, right); // 合并
}
/**
* 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
*
* @param data 数组对象
* @param left 左数组的第一个元素的索引
* @param center 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
* @param right 右数组最后一个元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 临时数组
int[] tmpArr = new int[data.length];
// 右数组第一个元素索引
int mid = center + 1;
// third 记录临时数组的索引
int third = left;
// 缓存左数组第一个元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 从两个数组中取出最小的放入临时数组
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// 将临时数组中的内容拷贝回原数组中
// （原left-right范围的内容被复制回原数组）
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
}