java幾種排序算法的完成及簡略剖析。本站提示廣大學習愛好者：（java幾種排序算法的完成及簡略剖析）文章只能為提供參考，不一定能成為您想要的結果。以下是java幾種排序算法的完成及簡略剖析正文
本文實例講述了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;
else
lo = 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法式設計有所贊助。
