衡量算法的指標
- 時間複雜度: 執行這個算法需要消耗的時間
- 空間複雜度: 這個算法需要佔用多少內存空間
- 穩定性: 假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的.
- In-place是指不佔用額外內存, Out-place需要佔用額外內存.
十大排序算法比較
- 冒泡排序, 選擇排序, 插入排序, 希爾排序, 歸併排序, 快速排序, 堆排序都屬於比較排序比較排序的優勢是, 適用於各種規模的數據, 也不在乎數據的分佈, 都能進行排序
- 計數排序, 桶排序, 基數排序屬於非比較排序 非比較排序只要確定每個元素之前的已有的元素個數即可, 所有一次遍歷即可解決。算法時間複雜度O(n), 但需要佔用空間來確定唯一位置. 所以對數據規模和數據分佈有一定的要求.
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
length = a.length;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
length = a.length;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
) { aux =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
high) {int
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小的值, 然後交換;
快速排序的優化:
- 對於小數組來說, 快速排序不如插入排序, 所以當數組比較少時, 可以切換到插入排序
- 迪傑斯特拉的"三向切分的快速排序"(TODO)
<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
(j < length && less(a, j, j+1
)) { 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
] = a[j -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
.length];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
) Math.pow(10
, k -1
) %10
; }private
static
void
int
[] a) { System.out
.println(Arrays.toString(a)); } }/<code>
十大排序應用場景
- 若n較小(如n≤50)，可採用直接插入或直接選擇排序。當記錄規模較小時，直接插入排序較好, 因為當數組基本有序時, 直接插入移動次數較少; 否則應選擇Selection sort為宜.
- 若文件初始狀態`基本有序(指正序), 則應選用插入排序, 冒泡或隨機的快速排序為宜
- 若n較大，則應採用時間複雜度為O(nlgn)的排序方法:快速排序, 堆排序或歸併排序快速排序是目前基於比較的內部排序中被認為是最好的方法,當待排序的關鍵字是隨機分佈時, 快速排序的平均時間最短.堆排序所需的輔助空間少於快速排序, 並且不會出現快速排序可能出現的最壞情況. 但這兩種排序都是不穩定的.若要求排序穩定, 則可選用歸併排序. 但從單個記錄起進行兩兩歸併的排序算法並不值得提倡, 通常可以將它和直接插入排序結合在一起使用. 先利用直接插入排序求得較長的有序子序列, 然後再兩兩歸併之. 因為直接插入排序是穩定的, 所以改進後的歸併排序仍是穩定的
