程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> JAVA 實現各種排序算法和復雜度分析1

JAVA 實現各種排序算法和復雜度分析1

編輯:關於JAVA

第一種:冒泡排序

public static int[] bubbleSort(int[] a) {

for (int i = 0; i < a.length; i++) {

for (int j = 0; j a[j + 1]) {

int temp = a[j];

a[j] = a[j + 1];

a[j + 1] = temp;

}

}

}

return a;

}

復雜度分析:冒泡排序是不穩定的排序算法,一共要比較((n-1)+(n-2)+...+3+2+1)=n*(n-1)/2次,所以時間復雜度是O(n^2)。

第二種:選擇排序

public static int[] selecitonSort(int[] a) {

for (int i = 0; i < a.length; i++) {

int max = a[0];

int count = 0;

int k = a.length - i - 1;

for (int j = 0; j < a.length - i; j++) {

if (max < a[j]) {

max = a[j];

count = j;

}

}

a[count] = a[k];

a[k] = max;

}

return a;

}

復雜度分析:選擇排序是不穩定算法,最好的情況是最好情況是已經排好順序,只要比較

n*(n-1)/2次即可,最壞情況是逆序排好的,那麼還要移動 O(n)次,由於是低階故而不考慮

不難得出選擇排序的時間復雜度是 O(n^2)

第三種:插入排序

待續。。。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved