排序
文章目錄
- 排序
- 排序的概念及其應用
- 常見的排序演算法
- 插入排序
- 直接插入排序
- 希爾排序
- 選擇排序
- 直接選擇排序
- 堆排序
排序的概念及其應用
排序的概念:
排序: 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作，
穩定性: 假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序演算法是穩定的；否則稱為不穩定的，
比如說這里有一些資料, 若需要我們從小到大依次排列, 其中有兩個位置的元素是相同的, 如果我們排列之后, 這兩個元素的相對位置沒有發生改變, 則我們認為這個排列是穩定的; 否則是不穩定的;
內部排序：資料元素全部放在記憶體中的排序，
外部排序：資料元素太多不能同時放在記憶體中，根據排序程序的要求不能在內外存之間移動資料的排序，
常見的排序演算法
插入排序
直接插入排序
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 ，
此時的插入排序并不穩定, 但只需要將arr[end] >= data改成arr[end] > data, 它就是一個穩定的排序方式了;
直接插入排序的特性總結：
- 元素集合越接近有序，直接插入排序演算法的時間效率越高
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)，它是一種穩定的排序演算法
- 穩定性：穩定
希爾排序
希爾排序的特性總結：
- 希爾排序是對直接插入排序的優化，
- 當gap > 1時都是預排序，目的是讓陣列更接近于有序，當gap == 1時，陣列已經接近有序的了，這樣就
會很快，這樣整體而言，可以達到優化的效果，我們實作后可以進行性能測驗的對比， - 希爾排序的時間復雜度不好計算，需要進行推導，推匯出來平均時間復雜度： O(N^1.3— N^2）
- 穩定性：不穩定
選擇排序
直接選擇排序
直接選擇排序的特性總結：
- 直接選擇排序思考非常好理解，但是效率不是很好，實際中很少使用
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
- 穩定性：不穩定
堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法，它是選擇排序的一種，它是通過堆來進行選擇資料，需要注意的是排升序要建大堆，排降序建小堆，
直接選擇排序的特性總結：
- 堆排序使用堆來選數，效率就高了很多，
- 時間復雜度：O(N*logN)
- 空間復雜度：O(1)
- 穩定性：不穩定
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290084.html
標籤：其他
上一篇：Docker-安全、CPU限額、記憶體限制、IO限制、安全加固
下一篇：??《資料結構入門》導航??