摘要:排序算法是最基本最常用的算法,不同的排序算法在不同的場景或應用中會有不同的表現,我們需要對各種排序算法熟練才能將它們應用到實際當中,才能更好地發揮它們的優勢。今天,來總結下各種排序算法。
排序算法是最基本最常用的算法,不同的排序算法在不同的場景或應用中會有不同的表現,我們需要對各種排序算法熟練才能將它們應用到實際當中,才能更好地發揮它們的優勢。今天,來總結下各種排序算法。
下面這個表格總結了各種排序算法的復雜度與穩定性:
各種排序算法復雜度比較.png
冒泡排序
冒泡排序可謂是最經典的排序算法了,它是基于比較的排序算法,時間復雜度為O(n^2),其優點是實現簡單,n較小時性能較好。
算法原理
相鄰的數據進行兩兩比較,小數放在前面,大數放在后面,這樣一趟下來,最小的數就被排在了第一位,第二趟也是如此,如此類推,直到所有的數據排序完成
c++代碼實現
void bubble_sort(int arr[], int len) { for (int i = 0; i < len - 1; i++) { for (int j = len - 1; j > i; j--) { if (arr[j] < arr[j - 1]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } }
}
選擇排序
算法原理
先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續尋找最小(大)元素,然后放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
c++代碼實現
void select_sort(int arr[], int len)
{
for (int i = 0; i < len; i++) { int index = i; for (int j = i + 1; j < len; j++) { if (arr[j] < arr[index]) index = j; } if (index != i) { int temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } }
插入排序
算法原理
將數據分為兩部分,有序部分與無序部分,一開始有序部分包含第1個元素,依次將無序的元素插入到有序部分,直到所有元素有序。插入排序又分為直接插入排序、二分插入排序、鏈表插入等,這里只討論直接插入排序。它是穩定的排序算法,時間復雜度為O(n^2)
c++代碼實現
void insert_sort(int arr[], int len) { for (int i = 1; i < len; i ++) { int j = i - 1; int k = arr[i]; while (j > -1 && k < arr[j] ) { arr[j + 1] = arr[j]; j --; } arr[j + 1] = k; } }
快速排序
算法原理
快速排序是目前在實踐中非常高效的一種排序算法,它不是穩定的排序算法,平均時間復雜度為O(nlogn),最差情況下復雜度為O(n^2)。它的基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然后再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。
c++代碼實現
void quick_sort(int arr[], int left, int right)
{ if (left < right) { int i = left, j = right, target = arr[left]; while (i < j) { while (i < j && arr[j] > target) j--; if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] < target) i++; if (i < j) arr[j] = arr[i]; } arr[i] = target; quick_sort(arr, left, i - 1); quick_sort(arr, i + 1, right); } }
歸并排序
算法原理
歸并排序具體工作原理如下(假設序列共有n個元素):
將序列每相鄰兩個數字進行歸并操作(merge),形成floor(n/2)個序列,排序后每個序列包含兩個元素
將上述序列再次歸并,形成floor(n/4)個序列,每個序列包含四個元素
重復步驟2,直到所有元素排序完畢
歸并排序是穩定的排序算法,其時間復雜度為O(nlogn),如果是使用鏈表的實現的話,空間復雜度可以達到O(1),但如果是使用數組來存儲數據的話,在歸并的過程中,需要臨時空間來存儲歸并好的數據,所以空間復雜度為O(n)
c++代碼實現
void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index)
{
int i = start_index, j = mid_index + 1; int k = 0; while (i < mid_index + 1 && j < end_index + 1) { if (arr[i] > arr[j]) temp_arr[k++] = arr[j++]; else temp_arr[k++] = arr[i++]; } while (i < mid_index + 1) { temp_arr[k++] = arr[i++]; } while (j < end_index + 1) temp_arr[k++] = arr[j++]; for (i = 0, j = start_index; j < end_index + 1; i ++, j ++) arr[j] = temp_arr[i];
} void merge_sort(int arr[], int temp_arr[], int start_index, int end_index) { if (start_index < end_index) { int mid_index = (start_index + end_index) / 2; merge_sort(arr, temp_arr, start_index, mid_index); merge_sort(arr, temp_arr, mid_index + 1, end_index); merge(arr, temp_arr, start_index, mid_index, end_index); } }
堆排序
二叉堆
二叉堆是完全二叉樹或者近似完全二叉樹,滿足兩個特性
父結點的鍵值總是大于或等于(小于或等于)任何一個子節點的鍵值
每個結點的左子樹和右子樹都是一個二叉堆
當父結點的鍵值總是大于或等于任何一個子節點的鍵值時為最大堆。當父結點的鍵值總是小于或等于任何一個子節點的鍵值時為最小堆。一般二叉樹簡稱為堆。
堆的存儲
一般都是數組來存儲堆,i結點的父結點下標就為(i – 1) / 2。它的左右子結點下標分別為2 i + 1和2 i + 2。如第0個結點左右子結點下標分別為1和2。存儲結構如圖所示:
堆排序原理
堆排序的時間復雜度為O(nlogn)
算法原理(以最大堆為例)
先將初始數據R[1..n]建成一個最大堆,此堆為初始的無序區
再將關鍵字最大的記錄R[1](即堆頂)和無序區的最后一個記錄R[n]交換,由此得到新的無序區R[1..n-1]和有序區R[n],且滿足R[1..n-1].keys≤R[n].key
由于交換后新的根R[1]可能違反堆性質,故應將當前無序區R[1..n-1]調整為堆。
重復2、3步驟,直到無序區只有一個元素為止。
c++代碼實現
/**
* 將數組arr構建大根堆 * @param arr 待調整的數組 * @param i 待調整的數組元素的下標 * @param len 數組的長度
*/ void heap_adjust(int arr[], int i, int len) { int child; int temp; for (; 2 * i + 1 < len; i = child) { child = 2 * i + 1; // 子結點的位置 = 2 * 父結點的位置 + 1 // 得到子結點中鍵值較大的結點 if (child < len - 1 && arr[child + 1] > arr[child]) child ++; // 如果較大的子結點大于父結點那么把較大的子結點往上移動,替換它的父結點 if (arr[i] < arr[child]) { temp = arr[i]; arr[i] = arr[child]; arr[child] = temp; } else break; } } /** * 堆排序算法 */ void heap_sort(int arr[], int len) { int i; // 調整序列的前半部分元素,調整完之后第一個元素是序列的最大的元素 for (int i = len / 2 - 1; i >= 0; i--) { heap_adjust(arr, i, len); } for (i = len - 1; i > 0; i--) { // 將第1個元素與當前最后一個元素交換,保證當前的最后一個位置的元素都是現在的這個序列中最大的 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 不斷縮小調整heap的范圍,每一次調整完畢保證第一個元素是當前序列的最大值 heap_adjust(arr, 0, i); } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/75925.html
摘要:整個數據流序列 Rxjs入門實踐-各種排序算法排序過程的可視化展示 這幾天學習下《算法》的排序章節,具體見對排序的總結,想著做點東西,能將各種排序算法的排序過程使用Rxjs通過可視化的方式展示出來,正好練系一下Rxjs的使用本文不會太多介紹Rxjs的基本概念,重點介紹如何用響應式編程的思想來實現功能 在線演示地址 源碼 效果圖 showImg(https://segmentfault...
摘要:整個數據流序列 Rxjs入門實踐-各種排序算法排序過程的可視化展示 這幾天學習下《算法》的排序章節,具體見對排序的總結,想著做點東西,能將各種排序算法的排序過程使用Rxjs通過可視化的方式展示出來,正好練系一下Rxjs的使用本文不會太多介紹Rxjs的基本概念,重點介紹如何用響應式編程的思想來實現功能 在線演示地址 源碼 效果圖 showImg(https://segmentfault...
摘要:如果有錯誤或不嚴謹的地方,歡迎批評指正,如果喜歡,歡迎點贊收藏 算法對大多數前端工程師來說都是一個比較不愿意提及的話題,因為學了,感覺在工作中直接應用的場景不多,不學,大廠面試必考算法,總結來說就是:沒有學習算法的源動力,為面試學習算法總不會令人動力去學習,沒有動力想要學好算法自然也很難,對我來說,學習算法的動力就是希望寫出更高效率的代碼,更好的理解各種前端框架的設計思路,因此,后面會...
閱讀 3499·2023-04-25 15:52
閱讀 581·2021-11-19 09:40
閱讀 2573·2021-09-26 09:47
閱讀 1023·2021-09-22 15:17
閱讀 3548·2021-08-13 13:25
閱讀 2200·2019-08-30 15:56
閱讀 3460·2019-08-30 13:56
閱讀 2095·2019-08-30 11:27