本文主要是介绍排序算法(二)_希尔排序、快速排序、归并排序的Java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天来聊聊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<tempArray.length;i++) {tempArray[i] = array[i];};int i = low;int j = mid+1;int index = low; //注意这里的是从index开始的while(i <= mid && j <= high) {if(tempArray[i] < tempArray[j]) {array[index++] = tempArray[i];i ++;} else {array[index++] = tempArray[j];j++;}}while(i <= mid) {array[index++] = tempArray[i];i++;}while(j <= high) {array[index++] = tempArray[j];j ++;}}// /**
// * 合并数组方法二
// * @param a1
// * @param a2
// */
// public int[] merge(int[] a1,int[] a2) {
// int[] a3 = new int[a1.length + a2.length];
// int i = 0;
// int j = 0;
// while(i < a1.length && j < a2.length) {
// if(a1[i] < a2[j]) {
// a3[i+j] = a1[i];
// i ++;
// } else {
// a3[i+j] = a2[j];
// j++;
// }
// }
// while(i < a1.length) {
// a3[i+j] = a1[i];
// i++;
// }
// while(j < a2.length) {
// a3[i+j] = a2[j];
// j ++;
// }
// return a3;
// }
}
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操作，因为递归求解范围不包括pivotsort(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.print("排序前:");int[] array = {3,5,1,6,2,8,7,4,9};for(int i:array) {System.out.print(i + " ");}System.out.print("\n排序后:");QuickSort quickSort = new QuickSort();quickSort.sort(array, 0, array.length-1);for(int i:array) {System.out.print(i + " ");}//2.测试归并排序System.out.println("\n--归并排序--");System.out.print("排序前:");int[] array2 = {3,6,1,2,8,7,9,5,4};for(int i:array2) {System.out.print(i + " ");}System.out.print("\n排序后:");MergeSort mergeSort = new MergeSort();mergeSort.sort(array2, 0, 8);for(int i:array2) {System.out.print(i + " ");}//3.测试希尔排序System.out.println("\n--希尔排序--");System.out.print("排序前:");int[] array3 = {4,7,2,1,8,9,3,6,5};for(int i:array3) {System.out.print(i + " ");}System.out.print("\n排序后:");ShellSort shellSort = new ShellSort();shellSort.sort(array3, 3);for(int i:array3) {System.out.print(i + " ");}}
}
运行结果：
--快速排序--
排序前:3 5 1 6 2 8 7 4 9
排序后:1 2 3 4 5 6 7 8 9
--归并排序--
排序前:3 6 1 2 8 7 9 5 4
排序后:1 2 3 4 5 6 7 8 9
--希尔排序--
排序前:4 7 2 1 8 9 3 6 5
排序后:1 2 3 4 5 6 7 8 9 以上三种排序有个共同点，都是"比较型"的排序算法，按照算法导论公开课中讲到的凡是"比较型"的排序算法其运行时间不可能低于theta(nlgn)，视频中给出了证明，这里不再赘述。具体可查看公开课的第五章—线性时间排序。
O啦~~~
转载请保留出处:http://blog.csdn.net/u011638883/article/details/13769747
谢谢!!
这篇关于排序算法(二)_希尔排序、快速排序、归并排序的Java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
