Java經常使用排序算法及機能測試聚集。本站提示廣大學習愛好者：（Java經常使用排序算法及機能測試聚集）文章只能為提供參考，不一定能成為您想要的結果。以下是Java經常使用排序算法及機能測試聚集正文
如今再回過火懂得，聯合本身的領會， 選用最好的方法描寫這些算法，以便利懂得它們的任務道理和法式設計技能。本文合適做java面試預備的資料浏覽。
先附上一個測試申報：
Array length: 20000
bubbleSort : 766 ms
bubbleSortAdvanced : 662 ms
bubbleSortAdvanced2 : 647 ms
selectSort : 252 ms
insertSort : 218 ms
insertSortAdvanced : 127 ms
insertSortAdvanced2 : 191 ms
binaryTreeSort : 3 ms
shellSort : 2 ms
shellSortAdvanced : 2 ms
shellSortAdvanced2 : 1 ms
mergeSort : 3 ms
quickSort : 1 ms
heapSort : 2 ms
經由過程測試，可以以為，冒泡排序完整有來由扔進渣滓桶。它存在的獨一來由能夠是最好懂得。希爾排序的高效性是我沒有想到的；堆排序比擬難懂得和編寫，要有微觀的思想。
package algorithm.sort;
import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Date;
/**
* Java經常使用排序算法及機能測試聚集
*
* 本法式聚集涵蓋經常使用排序算法的編寫，並在正文中合營極端簡略的特例講授了各類算法的任務道理，以便利懂得和接收；
* 法式編寫進程中接收了許多維基百科和他人blog下面的例子，並聯合本身的思慮，選擇並改良一個最輕易讓人懂得的寫法
*（特別是疾速排序，我認為我寫的算法最好懂得）。
* 同時包括一個集中式的機能測試和准確性測試辦法，便利不雅測。
* @author /link.php?url=http://blog.csdn.net/sunxing007
* 轉載請注明來自/link.php?url=http://blog.csdn.net/sunxing007
*/
public class SortUtil {
// 被測試的辦法聚集
static String[] methodNames = new String[]{
"bubbleSort",
"bubbleSortAdvanced",
"bubbleSortAdvanced2",
"selectSort",
"insertSort",
"insertSortAdvanced",
"insertSortAdvanced2",
"binaryTreeSort",
"shellSort",
"shellSortAdvanced",
"shellSortAdvanced2",
"mergeSort",
"quickSort",
"heapSort"
};
public static void main(String[] args) throws Exception{
//correctnessTest();
performanceTest(20000);
}
/**
* 准確性測試<br>
* 簡略地測試一下各個算法的准確性<br>
* 只是為了便利不雅測新添加的算法能否根本准確；<br>
* @throws Exception 重要是反射相干的Exception；<br>
*/
public static void correctnessTest() throws Exception{
int len = 10;
int[] a = new int[len];
for(int i=0; i<methodNames.length; i++){
for(int j=0; j<a.length; j++){
a[j] = (int)Math.floor(Math.random()*len*2);
}
Method sortMethod = null;
sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
Object o = sortMethod.invoke(null, a);
System.out.print(methodNames[i] + " : ");
if(o==null){
System.out.println(Arrays.toString(a));
}
else{
//統籌mergeSort，它的排序成果以前往值的情勢湧現；
System.out.println(Arrays.toString((int[])o));
}
}
}
/**
* 機能測試<br>
* 數組長度用參數len傳入，每一個辦法跑20遍取耗時均勻值；<br>
* @param len 數組長度 建議取10000以上，不然有些算法會顯示耗時為0；<br>
* @throws Exception 重要是反射相干的Exception；<br>
*/
public static void performanceTest(int len) throws Exception{
int[] a = new int[len];
int times = 20;
System.out.println("Array length: " + a.length);
for(int i=0; i<methodNames.length; i++){
Method sortMethod = null;
sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
int totalTime = 0;
for(int j=0; j<times; j++){
for(int k=0; k<len; k++){
a[k] = (int)Math.floor(Math.random()*20000);
}
long start = new Date().getTime();
sortMethod.invoke(null, a);
long end = new Date().getTime();
totalTime +=(end-start);
}
System.out.println(methodNames[i] + " : " + (totalTime/times) + " ms");
//System.out.println(Arrays.toString(a));
}
}
/**
* 最原始的冒泡交流排序;<br>
* 兩層遍歷，外層掌握掃描的次數，內層掌握比擬的次數；<br>
* 外層每掃描一次，就有一個最年夜的元素沉底；所之內層的比擬次數將逐步減小；<br>
*/
public static void bubbleSort(int[] a){
for(int i=0; i<a.length; i++){
for(int j=0; j<a.length-i-1; j++){
if(a[j]>a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
/**
* 改良的冒泡法<br>
* 改良的地方在於：設一個標記位，假如某趟跑上去，沒有產生交流，解釋曾經排好了；<br>
*/
public static void bubbleSortAdvanced(int[] a){
int k = a.length-1;
boolean flag = true;
while(flag){
flag = false;
for(int i=0;i<k;i++){
if(a[i]>a[i+1]){
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
//有交流則持續堅持標記位；
flag = true;
}
}
k--;
}
}
/**
* 改良的冒泡法2<br>
* 改良的地方在於接收下面的思惟(沒有交流意味著曾經有序)，假如部分的曾經是有序的，則後續的比擬就不須要再比擬他們了。<br>
* 好比：3142 5678，假設方才做完了2和4交流以後，發明這趟比擬後續再也沒有產生交流，則後續的比擬只須要比到4便可；<br>
* 該算法就是用一個標記位記載某趟最初產生比擬的所在；<br>
*/
public static void bubbleSortAdvanced2(int[] a){
int flag = a.length - 1;
int k;
while(flag>0){
k = flag;
flag = 0;
for(int i=0; i<k; i++){
if(a[i] > a[i+1]){
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
//有交流則記載該趟最初產生比擬的所在；
flag = i+1;
}
}
}
}
/**
* 拔出排序
*
* 關於拔出排序，這裡有幾個商定，從而可以疾速懂得算法：<br>
* i: 無序表遍歷下標；i<n-1；<br>
* j: 有序表遍歷下表；0<=j<i;<br>
* a[i]:表現以後被拿出來做拔出排序的無序表頭元素；<br>
* a[j]:有序表中的隨意率性元素；<br>
* <br>
* 算法症結點：把數組朋分為a[0~i-1]有序表，a[i~n-1]無序表；每次從無序表頭部取一個，<br>
* 把它拔出到有序表恰當的地位，直到無序表為空；<br>
* 初始時，a[0]為有序表，a[1~n-1]為無序表；<br>
*/
public static void insertSort(int[] a){
//從無序表頭開端遍歷；
for(int i=1; i<a.length; i++){
int j;
//拿a[i]和有序表元素順次比擬，找到一個適當的地位；
for(j=i-1;j>=0; j--){
if(a[j] < a[i]){
break;
}
}
//假如找到適當的地位，則從該地位開端，把元素朝後挪動一格，為拔出的元素騰出空間；
if(j!=(i-1)){
int tmp = a[i];
int k;
for(k = i-1; k>j;k--){
a[k+1] = a[k];
}
a[k+1] = tmp;
}
}
}
/**
* 改良的拔出排序1
* 改良的症結在於：起首拿無序表頭元素a[i]和有序表尾a[i-1]比擬，
* 假如a[i]<a[i-1],解釋須要調劑；調劑的進程為：
* 從有序表尾開端，把有序內外面比a[i]年夜的元素都朝後挪動，直到找到適當的地位；
*/
public static void insertSortAdvanced(int[] a){
//遍歷無序表；
for(int i=1; i<a.length; i++){
//假如無序表頭元素小於有序表尾，解釋須要調劑；
if(a[i]<a[i-1]){
int tmp = a[i];
int j;
//從有序表尾朝前搜刮並比擬，並把年夜於a[i]的元素朝後挪動以騰出空間；
for(j=i-1; j>=0&&a[j]>tmp;j--){
a[j+1] = a[j];
}
a[j+1] = tmp;
}
}
}
/**
* 改良的拔出排序2
* 整體思惟和下面類似，拿無序表頭元素從有序表尾元素開端朝前比擬，
* 假如a[i]比a[i-1]小，則把a[i]從有序表尾用冒泡交流的方法朝前挪動，直到達到適當的地位；
*/
public static void insertSortAdvanced2(int[] a){
//遍歷無序表
for(int i=1; i<a.length; i++){
//拿a[i]從有序表尾開端冒泡；
for(int j=i-1; j>=0 && a[j] > a[j+1]; j--){//a[j+1]就是a[i]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
/**
* 疾速排序<br>
* 算法的思惟在於分而治之:先找一個元素(普通來講都是數組頭元素),把比它年夜的都放到左邊,把比它小的都放到右邊;<br>
* 然後再依照如許的思惟行止理兩個子數組; 上面說的子數組頭元素通指用來劃分數組的元素;<br>
* <br>
* 上面法式症結點就在於!forward, low0++, high0--這些運算; 這三個運算使得a[low0],a[high0]外面總有一個指向子數組頭元素; <br>
* 可以用極真個情形來便利懂得這三個值的運作: <br>
* 假設我的數列為0123456789, 初始時forward=false,0作為子數組劃分根據,很明顯第一輪的時刻不會產生任何交流,low0一向指向0,<br>
* high0逐步降低直到它指向0為止; 同理可思慮9876543210這個例子;<br>
* <br>
* @param a 待排序數組<br>
* @param low 子數組開端的下標;<br>
* @param high 子數組停止的下標;<br>
*/
public static void quickSort(int[] a, int low, int high){
if(low>=high){
return;
}
int low0 = low;
int high0 = high;
boolean forward = false;
while(low0!=high0){
if(a[low0]>a[high0]){
int tmp = a[low0];
a[low0] = a[high0];
a[high0] = tmp;
forward = !forward;
}
if(forward){
low0++;
}
else{
high0--;
}
}
low0--;
high0++;
quickSort(a, low, low0);
quickSort(a, high0, high);
}
/**
* 疾速排序的簡略挪用情勢<br>
* 便利測試和挪用<br>
* @param a
*/
public static void quickSort(int[] a){
quickSort(a, 0, a.length-1);
}
/**
* 合並排序<br>
* 所謂合並，就是歸並兩個有序數組；合並排序也用了分而治之的思惟，把一個數組分為若干個子數組；<br>
* 當子數組的長度為1的時刻，則子數組是有序的，因而便可以兩兩合並了；<br>
* <br>
* 因為合並排序須要分派空間來轉儲合並的成果，為了算法上的便利，合並算法的成果以前往值的情勢湧現；<br>
*/
/**
* 歸並兩個有序數組
* @param a 有序數組1
* @param b 有序數組2
* @return 歸並以後的有序數組；
*/
public static int[] merge(int[] a, int[] b){
int result[] = new int[a.length+b.length];
int i=0,j=0,k=0;
while(i<a.length&&j<b.length){
if(a[i]<b[j]){
result[k++] = a[i];
i++;
}
else{
result[k++] = b[j];
j++;
}
}
while(i<a.length){
result[k++] = a[i++];
}
while(j<b.length){
result[k++] = b[j++];
}
return result;
}
/**
* 合並排序<br>
* 把數組從中央一分為二，並對閣下兩部門遞歸挪用，直到數組長度為1的時刻，開端兩兩合並；<br>
* @param 待排序數組；
* @return 有序數組；
*/
public static int[] mergeSort(int[] a){
if(a.length==1){
return a;
}
int mid = a.length/2;
int[] leftPart = new int[mid];
int[] rightPart = new int[a.length-mid];
System.arraycopy(a, 0, leftPart, 0, leftPart.length);
System.arraycopy(a, mid, rightPart, 0, rightPart.length);
leftPart = mergeSort(leftPart);
rightPart = mergeSort(rightPart);
return merge(leftPart, rightPart);
}
/**
* 選擇排序<br>
* 和拔出排序相似，它也把數組朋分為有序區和無序區，所分歧的是：<br>
* 拔出排序是拿無序區的首元素拔出到有序區恰當的地位，而<br>
* 選擇排序是從無序區中遴選最小的放到有序區最初；<br>
* <br>
* 兩層輪回，外層掌握有序區的隊尾，內層用來查找無序區最小元素；<br>
* @param a
*/
public static void selectSort(int[] a){
for(int i=0; i<a.length; i++){
int minIndex = i;
for(int j=i+1; j<a.length; j++){
if(a[j]<a[minIndex]){
minIndex = j;
}
}
int tmp = a[i];
a[i] = a[minIndex];
a[minIndex]= tmp;
}
}
/**
* 希爾排序<br>
* 其思惟是把數組按等步長(/間距)劃分為多個子序列，對各個子序列做通俗的拔出排序，<br>逐次下降步長，直到為1的時刻最初再做一次通俗的拔出排序；
* 用一個極真個例子作比喻，我稀有列以下：<br>
* [1,2,3,4,5,6,7,8,9,10];<br>
* 初始的時刻，步長gap=5；則劃分的子數組為[1,6], [2,7], [3,8], [4,9], [5,10];<br>對他們分離排序(固然因為本數組特別，所以成果是不變的)；<br>
* 然後gap=2=5/2; 子數組為[1,3,5,7,9], [2,4,6,8,10]; <br>
* 最初gap=1=2/2; 做一次全局排序；<br>
* <br>
* 希爾排序戰勝了拔出/冒泡排序的弱點(一次只能把元素挪動一個相鄰的地位), <br>依附年夜步長，可以把元素盡快挪動到目的地位(或鄰近);<br>
* 希爾排序現實上是拔出排序的變種。它實用於：當數組整體有序，個體須要調劑的情形；這時候候應用拔出排序的優勢，可以到達O(n)的效力；<br>
* 影響希爾算法的一個主要的身分是步長選擇，一個好步長的長處是：前面的短步長排序不會損壞後面的長步長排序；<br>
* 怎樣懂得這類損壞呢？後面的長步長把一個較小的數移到了左面，然則在減少步長以後有能夠又被交流到了左面 (由於它被分到了一個有許多比它更小的組)；<br>
* 關於步長，可以檢查http://zh.wikipedia.org下面關於希爾排序的頁面；<br>
* 上面的法式是希爾排序最基本的寫法，合適用來懂得希爾排序思惟；<br>
*/
public static void shellSort(int[] a){
// 掌握間距；間距逐步減小，直到為1；
for(int gap = a.length/2; gap>0; gap/=2){
// 掃描每一個子數組
for(int i=0; i<gap; i++){
// 對每一個字數組，掃描無序區；留意增量；
// a[i]是初始有序區；
for(int j=i+gap; j<a.length; j+=gap){
// 無序區首元素小於有序區尾元素，解釋須要調劑
if(a[j]<a[j-gap]){
int tmp = a[j];
int k = j-gap;
//從有序區尾向前搜刮查找恰當的地位；
while(k>=0&&a[k]>tmp){
a[k+gap] = a[k];
k-=gap;
}
a[k+gap] = tmp;
}
}
}
}
}
/**
* 改良的希爾排序<br>
* 改良的地方在於：下面的寫法用一個for輪回來差別看待每一個字數組；而現實上是不用要的；<br>
* a[0,1,...gap-1]作為一切子數組的有序區，a[gap,...n-1]作為一切字數組的無序區；<br>
* <br>
* 該改良在時光效力上沒有改良；只是讓法式看起來更簡練；<br>
* @param a
*/
public static void shellSortAdvanced(int[] a){
// 掌握步長
for(int gap = a.length/2; gap>0; gap/=2){
// 從無序區開端處置，把多個子數組放在一路處置；
for(int j=gap; j<a.length; j++){
// 上面的邏輯和下面是一樣的；
if(a[j]<a[j-gap]){
int tmp = a[j];
int k = j-gap;
while(k>=0&&a[k]>tmp){
a[k+gap] = a[k];
k-=gap;
}
a[k+gap] = tmp;
}
}
}
}
/**
* 改良的希爾排序2<br>
* 在接收shellSortAdvanced思惟的基本上，采取insertAdvanced2的做法；<br>即無序區首元素經由過程朝前冒泡的情勢挪動的恰當的地位；<br>
* @param a
*/
public static void shellSortAdvanced2(int[] a){
for(int gap = a.length/2; gap>0; gap/=2){
for(int i=gap; i<a.length; i++){
if(a[i]<a[i-gap]){
for(int j=i-gap; j>=0&&a[j+gap]>a[j]; j-=gap){
int tmp = a[j];
a[j] = a[j+gap];
a[j+gap] = tmp;
}
}
}
}
}
/**
* 堆排序<br>
* 堆的界說：堆是一個完整，或近似完整的二叉樹，堆頂元素的值年夜於閣下孩子的值，閣下孩子也須要知足這個前提；<br>
* 依照堆的界說，堆可所以年夜頂堆(maxHeap)，或小頂堆(minHeap)；<br>
* 普通用數組便可模仿二叉樹，關於隨意率性元素i，左孩子為2*i+1,右孩子為2*i+2;父節點為(i-1)/2;
* @param a
*/
public static void heapSort(int[] a){
// 先從最初一個非葉子節點往上調劑，使知足堆構造；
for(int i=(a.length-2)/2; i>=0; i--){
maxHeapAdjust(a, i, a.length);
}
// 每次拿最初一個節點和第一個交流，然後調劑堆；直到堆頂；
for(int i=a.length-1; i>0; i--){
int tmp = a[i]; a[i] = a[0]; a[0] = tmp;
maxHeapAdjust(a, 0, i);
}
}
/**
* 調劑堆<br>
* 把以i為跟節點的二叉樹調劑為堆；<br>
* 可以這麼來思慮這個進程：這個完整二叉樹就像一個金字塔，塔頂的小元素沿著樹構造，往下沉降；<br>
* 調劑的成果是最年夜的元素在金字塔頂，然後把它從堆中刪除(把它交流到堆尾，然後堆壓縮一格)；<br>
* 堆排序快的緣由就是依據二叉樹的特色，一個節點要沉降到適合的地位，只須要logn步；同時後期調劑的成果(年夜小次序)會被記載上去，從而加速後續的調劑；<br>
* @param a 待排數組
* @param i 堆頂
* @param len 堆長度
*/
public static void maxHeapAdjust(int[] a, int i, int len){
int tmp = a[i];
// j是左孩子節點
int j = i*2+1;
//
while(j<len){
// 從閣下孩子中遴選年夜的
// j+1是右孩子節點
if((j+1)<len && a[j+1]>a[j]){
j++;
}
// 找到適當的地位就不再找
if(a[j]<tmp){
break;
}
// 不然把較年夜者沿著樹往上挪動；
a[i] = a[j];
// i指向適才的較年夜的孩子；
i = j;
// j指向新的左孩子節點；
j = 2*i + 1;
}
// 把要調劑的節點值下沉到恰當的地位；
a[i] = tmp;
}
/**
* 二叉樹排序<br>
* 二叉樹的界說是嵌套的：<br>節點的值年夜於左葉子節點的值，小於右葉子節點的值；葉子節點異樣知足這個請求；<br>
* 二叉樹的結構進程就是排序的進程：<br>
* 先結構跟節點，然後挪用add辦法添加後續節點為跟節點的子孫節點；這個進程也是嵌套的;<br>
* <br>
* 中序遍歷二叉樹即獲得有序成果；<br>
* 二叉樹排序用法特別，應用情況要視情形而定；<br>
* @param a
*/
public static void binaryTreeSort(int[] a){
// 結構一個二叉樹節點外部類來完成二叉樹排序算法；
class BinaryNode{
int value;
BinaryNode left;
BinaryNode right;
public BinaryNode(int value){
this.value = value;
this.left = null;
this.right = null;
}
public void add(int value){
if(value>this.value){
if(this.right!=null){
this.right.add(value);
}
else{
this.right = new BinaryNode(value);
}
}
else{
if(this.left!=null){
this.left.add(value);
}
else{
this.left = new BinaryNode(value);
}
}
}
/**
* 按中序遍歷二叉樹，就是有序的。
*/
public void iterate(){
if(this.left!=null){
this.left.iterate();
}
// 在測試的時刻要把輸入關失落，以避免影響機能；
// System.out.print(value + ", ");
if(this.right!=null){
this.right.iterate();
}
}
}
BinaryNode root = new BinaryNode(a[0]);
for(int i=1; i<a.length; i++){
root.add(a[i]);
}
root.iterate();
}
}
