排序算法
排序算法是《資料結構與算法》中最基本的算法之一。
排序算法可以分為内部排序和外部排序,内部排序是資料記錄在記憶體中進行排序,而外部排序是因排序的資料很大,一次不能容納全部的排序記錄,在排序過程中需要通路外存。常見的内部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括:
1.冒泡排序
**冒泡排序(Bubble Sort)**也是一種簡單直覺的排序算法。它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。
1.1 排序原理
- 比較相鄰的元素。如果前一個元素比後一個元素大,就交換這兩個元素的位置。
- 對每一對相鄰元素做同樣的工作,從開始第一對元素到結尾的最後一對元素。最終最後位置的元素就是最大值。
1.2 算法示範
最快的時候:輸入資料已經是
正序
, 這時候隻需要循環确定一遍,時間複雜度為
O(n)
最慢的時候:輸入資料是
反序
,這時候需要嵌套式循環移動,時間複雜度為
O(n^2)
1.3 代碼實作
升序排序
public static int[] ascendingSort(int[] source) {
// 對 arr 進行拷貝,不改變參數内容
int[] arr = Arrays.copyOf(source, source.length);
for (int i = 0; i < source.length - 1; i++) {
for (int j = 0; j < source.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}
複制
降序排序
public static int[] descendingSort(int[] source) {
// 對 arr 進行拷貝,不改變參數内容
int[] arr = Arrays.copyOf(source, source.length);
for (int i = 0; i < source.length - 1; i++) {
for (int j = 0; j < source.length - 1 - i; j++) {
if (arr[j] < arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}
複制
代碼測試
public static void main(String[] args) {
int[] source = {4, 2, 3, 1};
//升序排序
int[] ascendingSort = ascendingSort(source);
//降序排序
int[] descendingSort = descendingSort(source);
System.out.println("============冒泡排序=============");
System.out.println("原有數組為:" + Arrays.toString(source));
System.out.println("升序數組為:" + Arrays.toString(ascendingSort));
System.out.println("降序數組為:" + Arrays.toString(descendingSort));
}
複制
2.選擇排序
選擇排序是一種簡單直覺的排序算法,無論什麼資料進去都是 O(n²) 的時間複雜度。是以用到它的時候,資料規模越小越好。唯一的好處就是不占用額外的記憶體空間。
2.1 排序原理
首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。
重複第二步,直到所有元素均排序完畢。
2.2 算法示範
無論什麼資料進去都是
O(n²)
的時間複雜度
2.3 代碼實作
升序排序
public static int[] ascendingSort(int[] source) {
// 對 arr 進行拷貝,不改變參數内容
int[] arr = Arrays.copyOf(source, source.length);
for (int i = 0; i < source.length - 1; i++) {
int min = i;
for (int j = i + 1; j < source.length; j++) {
//比較值,使 min 的值是最小的值的索引
if (arr[min] > arr[j]) {
min = j;
}
}
//交換 i 和 min 對應值
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
return arr;
}
複制
降序排序
public static int[] descendingSort(int[] source) {
// 對 arr 進行拷貝,不改變參數内容
int[] arr = Arrays.copyOf(source, source.length);
for (int i = 0; i < source.length - 1; i++) {
int min = i;
for (int j = i + 1; j < source.length; j++) {
if (arr[min] < arr[j]) {
min = j;
}
}
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
return arr;
}
複制
代碼測試
public static void main(String[] args) {
int[] source = {4, 2, 3, 1};
//升序排序
int[] ascendingSort = ascendingSort(source);
//降序排序
int[] descendingSort = descendingSort(source);
System.out.println("============選擇排序=============");
System.out.println("原有數組為:" + Arrays.toString(source));
System.out.println("升序數組為:" + Arrays.toString(ascendingSort));
System.out.println("降序數組為:" + Arrays.toString(descendingSort));
}
複制
3.插入排序
插入排序是一種最簡單直覺的排序算法,它的工作原理是通過建構有序序列,對于未排序資料,在已排序序列中從後向前掃描,找到相應位置并插入。
3.1 排序原理
将第一待排序序列第一個元素看做一個有序序列,把第二個元素到最後一個元素當成是未排序序列。
從頭到尾依次掃描未排序序列,将掃描到的每個元素插入有序序列的适當位置。(如果待插入的元素與有序序列中的某個元素相等,則将待插入元素插入到相等元素的後面。)
3.2 算法示範
插入排序使用了雙層for循環,其中内層循環的循環體是真正完成排序的代碼,是以,分析插入排序的時間複雜度,主要分析内層循環體的執行次數:
**最好情況:**正序排列,隻進行最外層的n次循環+n次的判斷,時間複雜度
O(n)
**最壞情況:**倒序排列,外層n次循環+ 1+2+…+n的判斷,時間複雜度
O(n^2)
3.3 代碼實作
升序排序
public static int[] ascendingSort(int[] source) {
// 對 arr 進行拷貝,不改變參數内容
int[] arr = Arrays.copyOf(source, source.length);
for (int i = 0; i < source.length; i++) {
//目前元素為a[i],依次和前面的元素比較,找到一個小于等于a[i]的元素
for (int j = i; j > 0; j--) {
if (arr[j - 1] > arr[j]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
} else {
break;
}
}
}
return arr;
}
複制
降序排序
public static int[] descendingSort(int[] source) {
// 對 arr 進行拷貝,不改變參數内容
int[] arr = Arrays.copyOf(source, source.length);
for (int i = 0; i < source.length; i++) {
//目前元素為a[i],依次和前面的元素比較,找到一個小于等于a[i]的元素
for (int j = i; j > 0; j--) {
if (arr[j - 1] < arr[j]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
} else {
break;
}
}
}
return arr;
}
複制
代碼測試
public static void main(String[] args) {
int[] source = {4, 2, 3, 1};
//升序排序
int[] ascendingSort = ascendingSort(source);
//降序排序
int[] descendingSort = descendingSort(source);
System.out.println("============插入排序=============");
System.out.println("原有數組為:" + Arrays.toString(source));
System.out.println("升序數組為:" + Arrays.toString(ascendingSort));
System.out.println("降序數組為:" + Arrays.toString(descendingSort));
}
複制
4.希爾排序
希爾排序,也稱遞減增量排序算法,是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的:
- 插入排序在對幾乎已經排好序的資料操作時,效率高,即可以達到線性排序的效率;
- 但插入排序一般來說是低效的,因為插入排序每次隻能将資料移動一位;
希爾排序的基本思想是:先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序,待整個序列中的記錄
基本有序
時,再對全體記錄進行依次直接插入排序。
4.1 排序原理
- 標明一個增長量step,按照增長量h作為資料分組的依據,對資料進行分組;
- 對分好組的每一組資料完成插入排序;
- 減小增長量,最小減為1,重複第二步操作。
4.2 算法示範
平均時間複雜度 :
O(n log n)
最好時間複雜度 :
O(nlog^2*n)
最壞時間複雜度 :
O(nlog^2*n)
4.3 代碼實作
升序排序
public static int[] ascendingSort(int[] source) {
// 對 arr 進行拷貝,不改變參數内容
int[] arr = Arrays.copyOf(source, source.length);
//控制增長量 從 arr.length / 2 開始
for (int step = arr.length / 2; step >= 1; step = step / 2) {
// a[i]就是待插入的元素
for (int i = step; i < arr.length; i++) {
//a[j]就是待插入元素,每次和前面的a[j-step]進行比較
for (int j = i; j >= step; j -= step) {
if (arr[j - step] > arr[j]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
} else {
break;
}
}
}
}
return arr;
}
複制
降序排序
public static int[] descendingSort(int[] source) {
// 對 arr 進行拷貝,不改變參數内容
int[] arr = Arrays.copyOf(source, source.length);
for (int step = arr.length / 2; step >= 1; step = step / 2) {
for (int i = step; i < arr.length; i++) {
for (int j = i; j >= step; j -= step) {
if (arr[j - step] < arr[j]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
} else {
break;
}
}
}
}
return arr;
}
複制
代碼測試
public static void main(String[] args) {
int[] source = {9,1,2,5,7,4,8,6,3,5};
//升序排序
int[] ascendingSort = ascendingSort(source);
//降序排序
int[] descendingSort = descendingSort(source);
System.out.println("============希爾排序=============");
System.out.println("原有數組為:" + Arrays.toString(source));
System.out.println("升序數組為:" + Arrays.toString(ascendingSort));
System.out.println("降序數組為:" + Arrays.toString(descendingSort));
}
複制
5.歸并排序
歸并排序(Merge sort)是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。
将已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若将兩個有序表合并成一個有序表,稱為
二路歸并
。
作為一種典型的分而治之思想的算法應用,歸并排序的實作由兩種方法:
- 自上而下的遞歸;(所有遞歸的方法都可以用疊代重寫,是以就有了第 2 種方法)
- 自下而上的疊代;
5.1 疊代
定義:定義方法時,在方法内部調用方法本身,稱之為遞歸.
作用:它通常把一個大型複雜的問題,層層轉換為一個與原問題相似的,規模較小的問題來求解。遞歸政策隻需要少量的程式就可以描述出解題過程所需要的多次重複計算,大大地減少了程式的代碼量。
注意:在遞歸中,不能無限制的調用自己,必須要有邊界條件,能夠讓遞歸結束,因為每一次遞歸調用都會在棧記憶體開辟新的空間,重新執行方法,如果遞歸的層級太深,很容易造成棧記憶體溢出。
遞歸Dome
1!: 1
2!: 2x1=2x1!
3!: 3x2x1=3x2!
4!: 4x3x2x1=4x3!
…
n!: nx(n-1)x(n-2)…x2x1=nx(n-1)!
public class Iterate {
// 階乘算法
public static int factorial(int n) {
if (n == 1) {
return 1;
}
return n * factorial(n - 1);
}
public static void main(String[] args) {
int result1 = factorial(1);
int result2 = factorial(2);
int result3 = factorial(3);
int result4 = factorial(4);
int result5 = factorial(5);
System.out.println("1!=" + result1);
System.out.println("2!=" + result2);
System.out.println("3!=" + result3);
System.out.println("4!=" + result4);
System.out.println("5!=" + result5);
}
}
複制
5.2 排序原理
- 盡可能的一組資料拆分成兩個元素相等的子組,并對每一個子組繼續拆分,直到拆分後的每個子組的元素個數是 1 為止。
- 将相鄰的兩個子組進行合并成一個有序的大組;
- 不斷的重複步驟2,直到最終隻有一個組為止。
5.3 算法示範
歸并算法時間複雜度
用樹狀圖來描述歸并,如果一個數組有8個元素,那麼它将每次除以2找最小的子數組,共拆
log8 = 3
,是以樹共有3層,那麼自頂向下第k層有
2^k
個子數組,每個數組的長度為
2^(3-k)
,歸并最多需要
2^(3-k)
次比較。是以每層的比較次數為
2^k * 2^(3-k) = 2^3
,那麼3層總共為
3 * 2^3
。
假設元素的個數為n,那麼使用歸并排序拆分的次數為
log2(n)
, 是以共
log2(n)
層,那麼使用 log2(n) 替換上面 3*2^3 中的3這個層數,最終得出的歸并排序的時間複雜度為:
log2(n) * 2^(log2(n)) = log2(n)*n
, 根據大O推導法則,忽略底數,最終歸并排序的時間複雜度為
O(nlogn)
;
歸并排序的缺點:
需要申請額外的數組空間,導緻空間複雜度提升,是典型的以空間換時間的操作。
希爾排序
和
歸并排序
在處理大批量資料時差别不是很大。
5.4 代碼實作
升序排序為例
//該方法用于分割數組,遞歸成有序的數組 歸并
public static int[] sort(int[] source) {
//複制數組
int[] arr = Arrays.copyOf(source, source.length);
//遞歸限制條件
if (arr.length < 2) {
return arr;
}
//中間值
int mid = (int) Math.floor(arr.length / 2);
//分割數組
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
//遞歸分割+歸并
return merge(sort(left), sort(right));
}
//歸并數組
public static int[] merge(int[] left, int[] right) {
//建立數組,承接排序後數組
int[] result = new int[left.length + right.length];
int i = 0;
//進行數組排序
while (left.length > 0 && right.length > 0) {
//下面的 if 進行判斷,可以降序或者升序
if (left[0] < right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
複制
代碼測試
public static void main(String[] args) {
int[] source = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
//排序
int[] sorted = sort(source);
System.out.println("============歸并排序=============");
System.out.println("原有數組為:" + Arrays.toString(source));
System.out.println("排序後數組為:" + Arrays.toString(sorted));
}
複制
6.快速排序
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下,排序 n 個項目要
Ο(nlogn)
次比較。在最壞狀況下則需要
Ο(n^2)
次比較,但這種狀況并不常見。事實上,快速排序通常明顯比其他 Ο(nlogn) 算法更快,因為它的内部循環可以在大部分的架構上很有效率地被實作出來。
快速排序使用分治法(Divide and conquer)政策來把一個串行(list)分為兩個子串行(sub-lists)。
快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看,快速排序應該算是在冒泡排序基礎上的遞歸分治法。
快速排序的最壞運作情況是 O(n²),比如說順序數列的快排。但它的平攤期望時間是 O(nlogn),且 O(nlogn) 記号中隐含的常數因子很小,比複雜度穩定等于 O(nlogn) 的歸并排序要小很多。是以,對絕大多數順序性較弱的随機數列而言,快速排序總是優于歸并排序。
6.1 排序原理
- 首先設定一個分界值,通過該分界值将數組分成左右兩部分;
- 将大于或等于分界值的資料放到到數組右邊,小于分界值的資料放到數組的左邊。此時左邊部分中各元素都小于或等于分界值,而右邊部分中各元素都大于或等于分界值;
- 然後,左邊和右邊的資料可以獨立排序。對于左側的數組資料,又可以取一個分界值,将該部分資料分成左右兩部分,同樣在左邊放置較小值,右邊放置較大值。右側的數組資料也可以做類似處理。
- 重複上述過程,可以看出,這是一個遞歸定義。通過遞歸将左側部分排好序後,再遞歸排好右側部分的順序。當左側和右側兩個部分的資料排完序後,整個數組的排序也就完成了。
6.2 算法示範
快速排序 和 歸并排序的差別:
快速排序是另外一種分治的排序算法,它将一個數組分成兩個子數組,将兩部分獨立的排序。
快速排序和歸并排序是互補的:
歸并排序
将數組分成兩個子數組分别排序,并将有序的子數組歸并進而将整個數組排序;
快速排序
的方式則是當兩個數組都有序時,整個數組自然就有序了。
在歸并排序中,一個數組被等分為兩半,歸并調用發生在處理整個數組之前,在快速排序中,切分數組的位置取決于數組的内容,遞歸調用發生在處理整個數組之後。
快速排序時間複雜度分析:
最優情況:每一次切分選擇的基準數字剛好将目前序列等分,共切分了
logn
次,是以,最優情況下快速排序的時間複雜度為
O(nlogn)
;
最壞情況:每一次切分選擇的基準數字是目前序列中最大數或者最小數,這使得每次切分都會有一個子組,那麼總共就得切分
n
次,是以,最壞情況下,快速排序的時間複雜度為
O(n^2)
;
平均情況:每一次切分選擇的基準數字不是最大值和最小值,也不是中值,這種情況,快速排序的時間複雜度為
O(nlogn)
6.3 代碼實作
以升序排序舉例
// 分割數組,排序
public static void sort(int[] source, int left, int right) {
if (left >= right) {
return;
}
//獲得基準值
int partition = partition(source, left, right);
//循環分割左半部分
sort(source, left, partition - 1);
//循環分割右半部分
sort(source, partition + 1, right);
}
public static int partition(int[] source, int left, int right) {
//基準值pivot
int pivot = left;
int index = pivot + 1;
//移動數組元素,小于基準的在前,大于基準的在後
for (int i = index; i <= right; i++) {
//if中條件可以控制 升序還是降序
if (source[pivot] > source[i]) {
int t = source[index];
source[index] = source[i];
source[i] = t;
index++;
}
}
//将基準元素交換到對應位置
int t = source[index - 1];
source[index - 1] = source[pivot];
source[pivot] = t;
//傳回基準元素索引值
return index - 1;
}
複制
代碼測試
public static void main(String[] args) {
int[] source = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
System.out.println("============快速排序=============");
System.out.println("原有數組為:" + Arrays.toString(source));
sort(source, 0, source.length - 1);
System.out.println("排序數組為:" + Arrays.toString(source));
}
複制
7.堆排序
堆排序
是指利用堆這種資料結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構,并同時滿足堆積的性質:即子結點的鍵值或索引總是小于(或者大于)它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法:
- 大頂堆:每個節點的值都大于或等于其子節點的值,在堆排序算法中用于升序排列;
- 小頂堆:每個節點的值都小于或等于其子節點的值,在堆排序算法中用于降序排列;
7.1 排序原理
堆構造原理
- 建立一個新數組,把原數組資料拷貝到新數組
- 再從新數組長度的一半處開始往0索引處掃描
- 然後對掃描到的每一個元素做下沉調整即可
堆排序原理
- 建立一個堆 H[0……n-1];
- 把堆首(最大值)和堆尾互換;
- 把堆的尺寸縮小 1,并調用 下沉函數,目的是把新的數組頂端資料調整到相應位置;
- 重複步驟 2,直到堆的尺寸為 1;
7.2 算法示範
7.3 代碼實作
以升序排序舉例
//交換
public static void exch(int[] source, int i, int j) {
int t = source[i];
source[i] = source[j];
source[j] = t;
}
//下沉函數
public static void sink(int[] heap, int i, int len) {
int m = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
//通過下面兩個if函數的比較,決定時升序還是降序
if (left < len && heap[m] < heap[left]) {
m = left;
}
if (right < len && heap[m] < heap[right]) {
m = right;
}
if (m != i) {
exch(heap, i, m);
sink(heap, m, len);
}
}
//排序算法
public static int[] sort(int[] source) {
int[] heap = Arrays.copyOf(source, source.length);
int len = heap.length;
//建立堆
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
sink(heap, i, len);
}
//最頂與最後一個元素進行交換,之後下沉新數組
while (len > 1) {
exch(heap, 0, len - 1);
len--;
sink(heap, 0, len);
}
return heap;
}
複制
代碼測試
public static void main(String[] args) {
int[] source = {2, 4, 5, 1, 5, 1, 7};
System.out.println("============堆排序=============");
System.out.println("原有數組為:" + Arrays.toString(source));
source = sort(source);
System.out.println("升序數組為:" + Arrays.toString(source));
}
複制
排序的穩定性
穩定性的定義:
數組arr中有若幹元素,其中A元素和B元素相等,并且A元素在B元素前面,如果使用某種排序算法排序後,能夠保證A元素依然在B元素的前面,可以說這個該算法是穩定的。
常見排序算法的穩定性:
冒泡排序:
隻有當
arr[i]>arr[i+1]
的時候,才會交換元素的位置,而相等的時候并不交換位置,是以冒泡排序是一種
穩定
排序算法。
選擇排序:
選擇排序是給每個位置選擇目前元素最小的,例如有資料
{5(1),8 ,5(2), 2, 9 }
, 第一遍選擇到的最小元素為
2
,是以
5(1)
會和
2
進行交換位置,此時
5(1)
到了
5(2)
後面,破壞了穩定性,是以選擇排序是一種
不穩定
的排序算法。
插入排序:
比較是從有序序列的末尾開始,也就是想要插入的元素和已經有序的最大者開始比起,如果比它大則直接插入在其後面,否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的,那麼把要插入的元素放在相等元素的後面。是以,相等元素的前後順序沒有改變,從原無序序列出去的順序就是排好序後的順序,是以插入排序是
穩定
的。
希爾排序:
希爾排序是按照不同步長對元素進行插入排序 ,雖然一次插入排序是穩定的,不會改變相同元素的相對順序,但在不同的插入排序過程中,相同的元素可能在各自的插入排序中移動,最後其穩定性就會被打亂,是以希爾排序是
不穩定
的。
歸并排序:
歸并排序在歸并的過程中,隻有
arr[i]<arr[i+1]
的時候才會交換位置,如果兩個元素相等則不會交換位置,是以它并不會破壞穩定性,歸并排序是
穩定
的。
快速排序:
快速排序需要一個基準值,在基準值的右側找一個比基準值小的元素,在基準值的左側找一個比基準值大的元素,然後交換這兩個元素,此時會破壞穩定性,是以快速排序是一種
不穩定
的算法。
個人部落格為:
MoYu’s HomePage