本文實例講述了java幾種排序算法的實現及簡單分析。分享給大家供大家參考。具體如下：
package test;public class first {/*普通的插入排序*/public void insertSort(int[] list) {int i, j;list[0] = -999;//相當於設置一個監視哨兵，不用判斷是否越界，//但要求數組從第二個數開始即i=1開始存儲for (i = 1; i < list.length; i++) {j = i;while (list[j] < list[j - 1 ]) {int temp = list[j];list[j] = list[j - 1];list[j - 1] = temp;j = j - 1;}}}/*折半插入，在直接插入的基礎上，添加二叉查找*/public void binInsertSort(int[] r, int low, int high) {for (int i = low + 1; i <= high; i++){int temp = r[i]; // 保存待插入元素int hi = i - 1;int lo = low; // 設置初始區間while (lo <= hi){ // 折半確定插入位置int mid = (lo + hi) / 2;if ( temp < r[mid])hi = mid - 1;elselo = mid + 1;}for (int j = i - 1; j > hi; j--)r[j + 1] = r[j]; / / 移動元素r[hi + 1] = temp; // 插入元素}}/*希爾排序或shell */public void shellSort(int[] r, int low, int high, int[] delta){for ( int k=0;k<delta.length;k++)shellInsert(r, low, high, delta[k]);}private void shellInsert(int[] r, int low, int high, int deltaK){for (int i=low+deltaK; i<=high; i++)if (r[i]<r[i-deltaK]){int temp = r[i];int j = i-deltaK;for(; j>=low&&temp <r[j]; j=j-deltaK)r[j+deltaK] = r[j];r[j+deltaK] = temp;}}/*簡單的選擇交換*/public void selectSort(int[] r, int low, int high) {for (int k = low; k < high - 1; k++) { // 作n-1 趟選取int min = k;for (int i = min + 1; i <= high; i++)// 選擇關鍵字最小的元素if (r[i] < r[min])min = i;if (k != min) {int temp = r[k]; // 關鍵字最小的元素與元素r[k]交換r[k] = r[min];r[min] = temp;}// end of if}}/*堆排序-大頂堆*/public void heapSort(int[] r){int n = r.length - 1;for (int i=n/2; i>=1; i--)heapAdjust(r,i,n);for (int i=n; i>1; i--){int temp = r[1];r[1] = r[i];r[i] = temp;heapAdjust(r,1,i-1);}}//調整堆private void heapAdjust (int[] r, int low, int high){int temp = r[low];for (int j = 2 * low; j <= high; j = j * 2) {if (j < high && r[ j] < r[j + 1])j++;if (temp > r[j])break;r[low] = r[j];low = j;}r[low] = temp;}public static void main (String[] args) {first fs = new first();int[] a = { 100, 9, 8, 9, 9, 7, 7, 0, 0, 99, 55, 7, 6, 5, 4 , 3, 2, 1 };int[] k={5,3,1};// fs.insertSort(a);//fs.binInsertSort(a, 0, a.length - 1);//fs .shellSort(a, 0,a.length-1,k);//fs.selectSort(a, 0, a.length-1);fs.heapSort(a);for (int i = 0; i < a .length; i++) {System.out.println(a[i]);}}}插入排序、交換排序、選擇排序、歸併排序等排序方法，都有一個共同的特點，那就是它們都是通過比較元素的大小來確定元素之間的相對位置的，即上述排序方法都是基於比較的排序方法。下面，我們就基於比較的排序方法進行一個對比和總結。
我們主要從算法的平均時間複雜度、最壞時間複雜度、空間複雜度以及排序的穩定性等方面，對各中排序方法加以比較。
排序方法平均時間複雜度最壞時間複雜度空間複雜度穩定性直接插入排序Ο(n2) Ο(n2) Ο(1) 穩定起泡排序Ο(n2) Ο(n2) Ο(1) 穩定快速排序Ο(n log n) Ο(n2) Ο(log n) 不穩定簡單選擇排序Ο(n2) Ο(n2) Ο(1) 不穩定堆排序Ο(n log n) Ο(n log n) Ο( 1) 不穩定歸併排序Ο(n log n) Ο(n log n) Ο(n) 穩定
從時間性能上看，快速排序是所有排序算法中實際性能最好的，然而快速排序在最壞情況下的時間性能不如堆排序和歸併排序。這一點可以通過對快速排序進行改進來避免，一種通過隨機選擇樞軸元素的隨機快速排序，可以使得出現最壞情況出現的機率非常小，在實際的運用中可以認為不存在。在堆排序和歸併排序的比較中，當n 較大時，歸併排序所需時間較少，然而它需要較多的輔助存儲空間。
從方法穩定性上來看，大多數時間複雜度為Ο(n2)的排序均是穩定的排序方法，除簡單選擇排序之外。而多數時間性能較好的排序方法，例如快速排序、堆排序、希爾排序都是不穩定的。一般來說，排序過程中的比較是在相鄰的兩個元素之間進行的排序方法是穩定的。
並且，排序方法的穩定性是由方法本身決定的，對於不穩定的排序方法而言，不管其描述形式如何，總能找到一種不穩定的實例。
綜上所述，上面討論的所有排序方法中，沒有哪一個是絕對最優的，在實際的使用過程中，應當根據不同情況選擇適當的排序方法。
希望本文所述對大家的java程序設計有所幫助。