衡量算法的指標
時間複雜度十大排序算法比較
Bubble sort(冒泡排序)
<code>
public
class
BubbleSort
{public
static
void
main
(String[] args
) { Integer [] arr = {18
,23
,11
,1
,9
,25
,33
,46
}; sort(arr); print(arr); }private
static
void
sort
(Comparable[] a
) {int
for
(int
i =0
; i < length; i++) {for
(int
j = i +1
; j < length; j++) {if
(a[i].compareTo(a[j]) >0
) { exch(a, i, j); } } } }private
static
void
exch
(Comparable[] a,
int
i,int
min) { Comparable temp = a[i]; a[i] = a[min]; a[min] = temp; }private
static
void
Comparable[] a
) { System.out
.println(Arrays.toString(a)); } }/<code>
Selection sort(選擇排序)
選擇排序, 對於長度為N的數組, 需要1 + 2 + ... + (N-1) = N(N-1)/2 約等於N2/2次比較, 需要N次交換.
選擇排序的步驟:
從第一個元素開始逐個和後面的元素比較, 然後找到最小元素的下標.交換當前元素和最小元素.<code>
public
class
SelectionSort
{public
static
void
main
(String[] args
) { Integer [] arr = {18
,23
,11
,1
,9
,25
,33
,46
}; sort(arr); print(arr); }private
static
void
sort
(Comparable[] a
) {int
length = a.length;for
(int
i =0
; i < length; i++) {int
min = i;for
(int
j = i +1
; j < length; j++) {if
(a[j].compareTo(a[min])0
) { min = j; } } exch(a, i, min); } }private
static
void
exch
(Comparable[] a,
int
i,int
min) { Comparable temp = a[i]; a[i] = a[min]; a[min] = temp; }private
static
void
Comparable[] a
) { System.out
.println(Arrays.toString(a)); } }/<code>Inserting sort(插入排序)
插入排序最壞需要進行N2/2次比較和N2/2次交換. 最好情況是隻需要進行N - 1次比較和0次交換.
注: 適合接近有序的數組進行排序, 類似於打撲克抓牌的過程
<code>
public
class
InsertionSort
{private
static
void
sort
(Comparable[] a)
{int
for
(int
i =1
; i < length; i++) {for
(int
j = i; j >0
; j--) {if
(a[j].compareTo(a[j-1
])0
) { exch(a, j, j -1
); } } } } }/<code>Shell sort(希爾排序)
希爾排序是對插入排序的一種改進(減少了元素的移動). 希爾排序的思想是使數組中任意間隔為h的元素都是有序的.它權衡了數組的規模和有序性.
該算法主要是, h的選擇.
<code>
public
class
ShellSort
{private
static
void
sort
(Comparable[] a)
{int
length = a.length;int
h =1
;while
(h < length/3
) { h =3
*h +1
; }while
(h >=1
) {for
(int
i = h; i < length; i++) {for
(int
j = i; j >= h; j-=h) {if
(a[j].compareTo(a[j-h])0
) { exch(a, j, j - h); } } } h = h/3
; } } }/<code>Merge sort(歸併排序)
歸併排序將數組分成兩個子數組分別排序, 並將有序的子數組歸併以將整個數組排序;
<code>
public
class
MergeSort
{private
static
Comparable[] aux;public
static
void
main
(String[] args
) { Integer [] arr = {18
,23
,11
,1
,9
,25
,33
,46
}; sort(arr); print(arr); }private
static
void
sort
(Comparable[] a
)new
Comparable[a.length]; sort(a,0
, a.length -1
); }private
static
void
sort
(Comparable[] a,
int
low,int
high) {if
(high <= low) {return
; }int
mid = low + (high - low)/2
; sort(a, low, mid); sort(a, mid +1
, high); merge(a, low, mid, high); }private
static
void
merge
(Comparable[] a,
int
low,int
mid,int
highint
i = low, j = mid +1
;for
(int
k = low; k <= high; k++) { aux[k] = a[k]; }for
(int
k = low; k <= high; k++) {if
(i > mid) { a[k] = aux[j++]; }else
if
(j > high) { a[k] = aux[i++]; }else
if
(aux[j].compareTo(aux[i])0
) { a[k] = aux[j++]; }else
{ a[k] = aux[i++]; } } }private
static
void
exch
(Comparable[] a,
int
i,int
min) { Comparable temp = a[i]; a[i] = a[min]; a[min] = temp; }private
static
void
Comparable[] a
) { System.out
.println(Arrays.toString(a)); } }/<code>Quick sort(快速排序)
快速排序和歸併排序是互補的, 快速排序是一種分治的排序算法, 它將一個數組分成兩個子數組, 將兩部分獨立地排序; 當兩個子數組都有序時整個數組也就自然有序了.
注: 此排序的關鍵是partition方法, 找到partition值. partition必須滿足
左邊的元素都小於等於partition值;右邊的元素都大於等於partition值;查找的方法是從左邊掃描比partition大的值,從數組尾部掃描比partition小的值, 然後交換;
快速排序的優化:
對於小數組來說, 快速排序不如插入排序, 所以當數組比較少時, 可以切換到插入排序迪傑斯特拉的"三向切分的快速排序"(<code>
public
class
QuickSort
{private
static
void
sort
(Comparable[] a)
{ sort(a,0
, a.length -1
); }private
static
void
sort
(Comparable[] a,
int
low,int
high) {if
(high <= low) {return
; }int
j = partition(a, low, high); sort(a, low, j); sort(a, j+1
, high); }private
static
int
partition
(Comparable[] a,
int
low,int
high) {int
i = low, j = high +1
; Comparable v = a[low];while
(true
) {while
(a[++i].compareTo(v)0
) {if
(i == high) {break
; } }while
(a[--j].compareTo(v) >0
) {if
(j == low) {break
; } }if
(i >= j) {break
; } exch(a, i, j); } exch(a, low, j);return
j; } }/<code>Heap sort(堆排序)
堆排序分為兩個階段:
堆的構造階段, 將原始數組安排進一個堆中下沉階段, 遞減取出所有元素並得出排序結果<code>
public
class
HeapSort
{public
static
void
main
(String[] args)
{ Integer [] arr = {18
,23
,11
,1
,9
,25
,33
,46
}; sort(arr); print(arr); }private
static
void
sort
(Comparable[] a)
{int
length = a.length;for
(int
k = length/2
; k >=1
; k--) { sink(a, k, length); }while
(length >1
) { exch(a,1
, length--); sink(a,1
, length); } }private
static
void
sink
(Comparable[] a,
int
k,int
length) {while
(2
* k <= length) {int
j =2
* k;if
(j1
)) { j++; }if
(!less(a, k, j)) {break
; } exch(a, k, j); k = j; } }private
static
boolean
less
(Comparable[] a,
int
i,int
j) {return
a[i -1
].compareTo(a[j -1
])0
; }private
static
void
exch
(Comparable[] a,
int
i,int
j) { Comparable temp = a[i -1
]; a[i -1
1
]; a[j -1
] = temp; }private
static
void
(Comparable[] a)
{ System.out.println(Arrays.toString(a)); } }/<code>Counting sort(計數排序)
計數排序分為4步驟:
得到數列的最大值與最小值,並算出差值d創建統計數組並計算統計對應元素個數統計數組變形,後面的元素等於前面的元素之和倒序遍歷原始數組,從統計數組找到正確位置,輸出到結果數組<code>
public
class
CountingSort
{public
static
void
main
(String[] args)
int
[] arr = {18
,23
,11
,1
,9
,25
,33
,46
}; print(sort(arr)); }private
static
int
[] sort(int
[]array
) {int
max =array
[0
];int
min =array
[0
];for
(int
i =1
; iarray
.length; i++) {if
array
[i] > max) { max =array
[i]; }if
(array
[i] < min) { min =array
[i]; } }int
d = max - min;int
[] countArray =new
int
[d +1
];for
(int
i =0
; iarray
.length; i++) { countArray[array
[i] - min]++; }int
sum =0
;for
(int
i =0
; i < countArray.length; i++) { sum += countArray[i]; countArray[i] = sum; }int
[] sortedArray =new
int
[array
for
(int
i =array
.length -1
; i >=0
; i--) { sortedArray[countArray[array
[i] - min] -1
] =array
[i]; countArray[array
[i] - min]--; }return
sortedArray; }private
static
void
(
int
[] a) { System.out.println(Arrays.toString(a)); } }/<code>Bucket sort(桶排序)
桶排序步驟:
找出數組最大值, 得到桶的數量把數字出現的次數放入對應數組中打印次數大於0的數組元素<code>
public
class
BucketSort
{public
static
void
main
(String[] args
) {int
[] arr = {18
,23
,11
,1
,9
,25
,33
,46
}; sort(arr); print(arr); }private
static
void
sort
(int
[] arr) {if
(arr ==null
|| arr.length2
) {return
; }int
max = Integer.MIN_VALUE;for
(int
i =0
; i < arr.length; i++) { max = Math.max(max, arr[i]); }int
[] bucket =new
int
[max +1
];for
(int
i =0
; i < arr.length; i++) { bucket[arr[i]]++; }int
i =0
;for
(int
j =0
; j < bucket.length; j++) {while
(bucket[j]-- >0
) { arr[i++] = j; } } }private
static
void
int
[] a) { System.out
.println(Arrays.toString(a)); } }/<code>Radix sort(基數排序)
基數排序的步驟:
求出數組中所有數據的最大位數循環按照每位上的數據進行排序<code>
public
class
RadixSort
{public
static
void
main
(String[] args
) {int
[] arr = {18
,23
,11
,1
,9
,25
,33
,46
189
,389
}; sort(arr); print(arr); }private
static
void
sort
(int
[] arr) {int
[] count =new
int
[arr.length];int
[] bucket =new
int
[arr.length];int
digits = getMaxDigits(arr);for
(int
k =1
; k <= digits; k++) {for
(int
i =0
; i < arr.length; i++) { count[i] =0
; }for
int
value
: arr) { count[getFigure(value
, k)]++; }for
(int
i =1
; i < arr.length;i++) { count[i] = count[i] + count[i-1
]; }for
(int
i = arr.length -1
; i >=0
; i--) {int
j = getFigure(arr[i], k); bucket[count[j] -1
] = arr[i]; count[j]--; }for
(int
i =0
, j =0
; i < arr.length; i++, j++) { arr[i] = bucket[j]; } } }private
static
int
getMaxDigits
(int
[] a)int
maxDigits =1
;for
(int
value
: a) {int
digits =1
;while
(value
/ (int
) (Math.pow(10
, digits)) >0
) { digits++; } maxDigits = Math.max(maxDigits, digits); }return
maxDigits; }private
static
int
getFigure
(int
value
,int
k) {return
value
/ (int
10
, k -1
) %10
; }private
static
void
int
[] a) { System.out
.println(Arrays.toString(a)); } }/<code>