常見比較排序
1.冒泡排序
2.選擇排序：簡單選擇排序和堆排序
3.插入排序：直接插入排序和希爾排序
4.快速排序
5.歸并排序
常見非比較排序
1.計數(shù)排序
2.基數(shù)排序
3.桶排序
常見算法的穩(wěn)定性：
堆排序蕉陋、快速排序、希爾排序键耕、直接選擇排序是不穩(wěn)定的排序算法，
基數(shù)排序柑营、冒泡排序屈雄、直接插入排序、歸并排序官套、折半插入排序是穩(wěn)定的排序算法酒奶。
復雜度和穩(wěn)定性（如圖）
注釋：
n 數(shù)據(jù)規(guī)模
k 桶的個數(shù)
In-place 占用常數(shù)內存，不占用額外內存
Out-place 占用額外內存
一奶赔、冒泡排序（Bubble Sort）--惩锖浚考
冒泡排序是一種簡單的排序算法。它重復地走訪要排序的數(shù)列站刑，一次比較兩個元素另伍，如果他們的順序錯誤就把他們交換過來，走訪數(shù)列的工作是重復地進行直到?jīng)]有要交換的為止，也就是說該數(shù)列已排序完成摆尝。這個算法的名字由來是因為越小的元素會經(jīng)過不斷交換慢慢浮到數(shù)列的頂端温艇。
1.1 算法描述
- 步驟1：比較相鄰的元素，如果第一個比第二個大堕汞，就交換它們兩個勺爱，大的靠后
- 步驟2：對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對讯检，這樣在最后的元素應該是最大的
- 步驟3：針對所有的元素重復以上的步驟琐鲁，除了最后一個
- 步驟4：重復步驟1~3，直到排序完成人灼。
1.2 動圖展示
1.3 代碼演示
function bubbleSort (arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]) {
let temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
// 或者用 [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
1.4 算法分析
- 最佳情況：T(n) = O(n)
- 最差情況：T(n) = O(n^2)
- 平均情況：T(n) = O(n^2)
二围段、選擇排序（Selection Sort）
選擇排序是表現(xiàn)最穩(wěn)定的排序算法之一，因為無論什么數(shù)據(jù)進去都是O(n^2)的時間復雜度挡毅，所以用到它的時候蒜撮，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內存空間了跪呈。
選擇排序的工作原理是：首先在未排序的序列中找到最卸文ァ（大）元素，存放到排序序列的起始位置耗绿，然后苹支，再從剩余未排序元素中繼續(xù)尋找最小（大）元素误阻，然后放到已排序序列的末尾债蜜，以此類推，直到排序完成究反。
2.1 算法描述
n個記錄的直接選擇排序結果可經(jīng)過n-1趟直接選擇排序得到有序結果寻定。
- 步驟1：取出未排序序列的第一個元素，設為初始最小值精耐，遍歷該元素之后的部分并比較大小狼速。
- 步驟2：如果有更小的元素，與該元素交換位置卦停，設為最小的向胡。
- 步驟3：每次遍歷找出剩余元素中的最小值并放在已排序序列的最后，如此惊完，n-1趟結束僵芹，數(shù)組有序化了。
2.2 動圖展示
2.3 代碼演示
function selectionSort (arr) {
for (let i = 0; i < arr.length; i++) {
let min_index = i;
for (let j = i+1; j < arr.length; j++) {
if (arr[j] < arr[min_index]) min_index = j
}
// 交換兩個元素
let temp = arr[min_index]
arr[min_index] = arr[i]
arr[i] = temp
// 或者[arr[min_index], arr[i]] = [arr[i], arr[min_index]]
}
return arr
}
2.4 算法分析
- 最佳情況：T(n) = O(n^2)
- 最差情況：T(n) = O(n^2)
- 平均情況：T(n) = O(n^2)
三小槐、堆排序（Heap Sort）--衬磁桑考
堆排序是利用堆這種數(shù)據(jù)結構所設計的一種選擇排序算法。堆是一種近似完全二叉樹的數(shù)據(jù)結構，并同時滿足堆積的性質：即子節(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點攀痊。
1桐腌、堆是樹的一種，當堆的父節(jié)點都大于或者都小于子節(jié)點時苟径，分別稱為最大堆或最小堆案站。
2、可以用數(shù)組來表示樹（堆）棘街。從0開始蟆盐，以數(shù)組的第index個元素為堆的父節(jié)點，其左右子節(jié)點分別為數(shù)組的第2index+1和2index+2個元素遭殉。
3石挂、已排序的元素將放在數(shù)組尾部。
3.1 算法描述
- 步驟1：把數(shù)組整理為最大堆的順序险污，那么堆的根節(jié)點或者說數(shù)組的第一個元素痹愚，就是最大的值
- 步驟2：排序：把最大值與未排序部分的最后一個元素交換，剩余的部分繼續(xù)調整為最大值蛔糯，每次建堆都能找到剩余元素中最大的一個拯腮。
注意： - 第一次建堆時只需要遍歷數(shù)組左側一半元素就夠了，并且要從中點向左側倒序遍歷蚁飒，這樣才能保證把最大的元素移動到數(shù)組頭部
- 排序時动壤，當然就要遍歷數(shù)組里所有元素了
3.2 動圖展示
3.3 代碼演示
function heapSort (arr) {
let len = arr.length
if (len <= 1) return arr
// 1. 建最大堆
// 遍歷一半元素即可，必須從中點開始向左遍歷
for (let middle = Math.floor(len/2); middle >= 0; middle--) {
maxHeapify(arr, middle, len)
}
// 2.排序淮逻，遍歷所有元素
for (let j = len; j >= 1; j--) {
// 2.1 將最大的根元素arr[0]與最后一個元素arr[j-1]交換
swap(arr, 0, j-1)
// 2.2 剩余的元素繼續(xù)建最大堆
maxHeapify(arr, 0, j-2)
}
return arr
}
// 建最大堆
function maxHeapify (arr, middle_index, length) {
// 1. 假設父節(jié)點位置的值最大
let largest_index = middle_index
// 2. 計算左右節(jié)點位置
let left_index = 2*middle_index + 1,
right_index = 2*middle_index + 2
// 3. 判斷父節(jié)點是否最大
// 如果沒有超出數(shù)組長度琼懊，并且子節(jié)點比父節(jié)點大，那么修改最大節(jié)點的索引
// 左邊更大
if (left_index <= length && arr[left_index] > arr[largest_index])
largest_index = left_index
// 右邊更大
if (right_index <= length && arr[right_index] > arr[largest_index])
largest_index = right_index
// 4. 如果largest_index發(fā)生了更新爬早，那么交換父子位置哼丈，遞歸計算
if (largest_index !== middle_index) {
swap(arr, middle_index, largest_index)
// 因為這時一個較大的元素提到了前面，一個較小的元素移到了后面
// 小元素的新位置之后可能還有比它更大的筛严，需要遞歸
maxHeapify(arr, largest_index, length)
}
}
function swap (arr, a, b) {
let temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
}
3.4 算法分析
- 最佳情況：T(n) = O(nlogn)
- 最差情況：T(n) = O(nlogn)
- 平均情況：T(n) = O(nlogn)
四醉旦、插入排序（Insertion Sort）
插入排序是一種簡單直觀的排序算法。其工作原理是通過構建有序序列脑漫，對于未排序數(shù)據(jù)髓抑，在已排序序列中從后向前掃描咙崎，找到相應位置并插入优幸。插入排序在實現(xiàn)上，通常采用In-place排序（即只需要用到O(1)的額外空間排序）褪猛，因此從后向前掃描過程中网杆，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
注：插入排序將已排序的數(shù)組放在數(shù)組前面碳却。
4.1 算法描述
- 步驟1：從第一個元素開始队秩，該元素可以認定為已排序
- 步驟2：取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
- 步驟3：如果該元素（已排序）大于新元素昼浦，將該元素向后挪一位置
- 步驟4： 重復步驟3馍资，直到找到已排序的元素小于或者等于新元素的位置
- 步驟5：將新元素插入到該位置后。
- 步驟6：重復步驟2-5
4.2 動圖展示
4.3 代碼演示
// 第一種一般寫法
function insertionSort (arr) {
for (let index = 1; index < arr.length; index++) {
// 取出一個未排序元素
let current_ele = arr[index]
// 已排序元素的最后一個的位置
let ordered_index = index - 1
while (arr[ordered_index] >= current_ele && ordered_index >= 0) {
// 使用前面的值覆蓋當前的值
arr[ordered_index + 1] = arr[ordered_index]
// 向前移動一個位置
ordered_index--
}
// 遍歷完成关噪，前面的元素都比當前元素小鸟蟹，把未排序元素賦值進去
arr[ordered_index + 1] = current_ele
}
return arr
}
// 第二種結合冒泡排序的寫法
function insertionSort (arr) {
for (let i = 0; i < arr.length; i++) {
// 對前面已排序的數(shù)組和新選出來的元素執(zhí)行一趟冒泡排序
for (let j = i + 1; j >= 0; j--) {
if (arr[j] < arr[j-1]) {
let temp = arr[j]
arr[j] = arr[j-1]
arr[j-1] = temp
}
}
}
return arr
}
4.4 算法分析
- 最佳情況：T(n) = O(n)
- 最差情況：T(n) = O(n^2)
- 平均情況：T(n) = O(n^2)
五、希爾排序（Shell Sort）
希爾排序也是一種插入排序使兔，它是簡單插入排序經(jīng)過改進之后的一個更高效的版本建钥，也稱為縮小增量排序，它與插入排序的不同之處在于虐沥，它會優(yōu)先比較距離比較遠的元素熊经。首先指定一個增量gap，對數(shù)組分組欲险，使得每相距gap-1的元素為一組镐依，共分成gap組，對每組執(zhí)行插入排序盯荤，逐步縮小gap的大小并繼續(xù)執(zhí)行插入排序馋吗，直到為1，也就是整個數(shù)組為一組秋秤，對整個數(shù)組進行插入排序宏粤。gap對排序結果沒有影響，只是影響了算法效率灼卢。
5.1 算法描述
設置增量gap=length/2绍哎，縮小增量繼續(xù)以gap=gap/2的方式，
- 步驟1：共三層循環(huán)鞋真，外層循環(huán)用來逐步減少gap的值
- 步驟2：中層與內層兩層循環(huán)基本上就是插入排序崇堰，細節(jié)上的不同直接看代碼就好。
5.2 動圖展示
5.3 代碼演示
// 第一種寫法
function shellSort (arr) {
// 外層循環(huán)逐步縮小增量gap的值
for (let gap = 5; gap > 0; gap = Math.floor(gap/2)) {
// 中層和內層是插入排序
// 普通插入排序從第1個元素開始涩咖，這里分組了海诲，要看每個組的第1個元素
// 共分成了gap組，第一組的第1個元素索引為gap
// 第一組元素索引為0檩互，0+gap特幔，0+2+gap，...闸昨，第二組元素索引為1蚯斯，1+gap薄风，2+2+gap，...
for (let i = gap; i < arr.length; i++) {
let current_ele = arr[i]
// i每次減少gap拍嵌，只會與當前元素相隔n*(gap-1)的元素比較遭赂，也就是只會與同組的元素比較
let ordered_index = i - gap
// 對分組后的數(shù)組進行插入排序
while (ordered_index >= 0 && arr[ordered_index] > current_ele) {
arr[ordered_index + gap] = arr[ordered_index]
ordered_index -= gap
}
arr[ordered_index + gap] = current_ele
}
}
return arr
}
// 第二種寫法，口訣：3 for + 1 if
function shellSort (arr) {
let length = arr.length
for (let gap = Math.floor(length/2); gap > 0; gap = Math.floor(gap/2)) {
for (let i = gap; i < length; i++) {
for (let j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
[arr[j], arr[j + gap]] = [arr[j + gap], arr[j]] // 交換兩個元素
}
}
}
}
return arr
}
5.4 算法分析
- 最佳情況：T(n) = O(nlog2n)
- 最壞情況：T(n) = O(nlog2n)
- 平均情況：T(n) = O(nlog2n)
六横辆、快速排序（Quick Sort）--称菜考
快速排序的工作原理是：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小狈蚤，則可分別對這兩部分記錄繼續(xù)進行排序逆粹，以達到整個序列有序§懦停快速排序是對冒泡排序的一種改進僻弹，第一趟排序時將數(shù)據(jù)分成兩部分，一部分比另一部分的所有數(shù)據(jù)都要小他嚷。然后遞歸調用蹋绽，在兩邊都實行快速排序。
6.1 算法描述
快速排序使用分治法將一個串分為兩個子串筋蓖，具體步驟如下：
- 步驟1：從數(shù)列里挑一個元素卸耘，稱為基準（pivot）。比如第一個元素
- 步驟2：重新排序數(shù)列粘咖，所有比基準小的元素擺放在基準前面蚣抗，建一個數(shù)組；所有比基準大的元素擺放在基準后面瓮下，也建一個數(shù)組翰铡；相同的數(shù)可以放在任一邊。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置，這個稱為分區(qū)操作坏挠。
- 步驟3：遞歸地把小于基準元素的子數(shù)列和大于基準元素的子數(shù)列排序。繼續(xù)執(zhí)行步驟1白群，直到數(shù)組只剩1個元素；遞歸的同時把這三部分連接起來
普通快速排序沒有考慮與
pivot相等的情況，只建了更小和更大的兩個數(shù)組。
像上面考慮與pivot相等的情況時漠秋，又叫做[三路快排]。
6.2 動圖展示
6.3 代碼演示
function quickSort (arr) {
// 只剩1個元素的話抵屿，不能再分割了
if (arr.length <= 1) return arr
// 取第1個元素為基準值
let pivot = arr[0]
// 分割為左小右大兩個數(shù)組庆锦，以及包含元素本身的中間數(shù)組
let left = [], middle = [pivot], right = []
for (let i = 1; i < arr.length; i++) {
if (arr[i] === pivot) middle.push(arr[i])
else if (arr[i] < pivot) left.push(arr[i])
else right.push(arr[i])
}
// 遞歸并連接
return quickSort(left).concat(middle, quickSort(right))
}
6.4 算法分析
- 最佳情況：T(n) = O(nlogn)
- 最差情況：T(n) = O(n^2)
- 平均情況：T(n) = O(nlogn)
七、歸并排序（Merge Sort）--成胃茫考
歸并排序始終都是O(nlogn）的時間復雜度肥荔，代價是需要額外的內存空間。歸并排序是建立在歸并操作上的一種有效的排序算法朝群。該算法是采用分治法的典型應用燕耿，它是一種穩(wěn)定的排序算法。通過將已有序的子序列合并姜胖，得到完全有序的序列誉帅，即先使每個子序列有序，再使子序列段間有序右莱，若將兩個有序表合并成一個有序表蚜锨，稱為2路歸并。
7.1 算法描述
- 步驟1：把長度為n的序列分為兩個長度為n/2的子序列
- 步驟2：對這兩個子序列分別采用歸并排序
- 步驟3：將兩個排序好的子序列合并成一個最終的排序序列慢蜓。
7.2 動圖展示
7.3 代碼演示
// 分割
function mergeSort (arr) {
// 如果只剩1個元素亚再，分割結束
if (arr.length <= 1) return arr
// 否則繼續(xù)分成2部分
let middle_index = Math.floor(arr.length / 2),
left = arr.slice(0, middle_index),
right = arr.slice(middle_index)
return merge(mergeSort(left), mergeSort(right))
}
function merge (left, right) {
let result = []
// 當左右兩個數(shù)組都還沒有取完的時候，比較大小然后合并
while (left.length && right.length) {
if (left[0] < right[0]) result.push(left.shift()) // 將左邊數(shù)組中的第一個元素取出存入result
else result.push(right.shift())
}
// 其中一個數(shù)組空了晨抡，另一個還剩下一些元素
// 因為是已經(jīng)排序過的氛悬，所以直接concat就好了
// 注意 concat 不改變原數(shù)組
if (left.length) result = result.concat(left)
if (right.length) result = result.concat(right)
return result
}
// 合并
7.4 算法分析
- 最佳情況：T(n) = O(nlogn)
- 最差情況：T(n) = O(n^2)
- 平均情況：T(n) = O(nlogn)
八、二分查找（Binary Search）
二分查找算法耘柱，也叫折半查找如捅。它的工作原理是：針對一個有序的數(shù)據(jù)集合，每次通過跟區(qū)間的中間元素對比调煎，將待查找的區(qū)間縮小為之前的一半镜遣，直到找到要查找的元素，或者區(qū)間縮小為0士袄。
8.1 算法描述
- 步驟1：從有序數(shù)組的最中間元素開始查找悲关，如果該元素正好是指定查找的值，則查找過程結束娄柳，否則進行下一步坚洽。
- 步驟2：如果指定要查找的元素大于或者小于中間元素，則在數(shù)據(jù)大于或小于中間元素的那一半?yún)^(qū)域查找西土，然后重復第一步
- 步驟3：重復以上過程讶舰，直到找到目標元素的索引，查找成功需了；或者直到子數(shù)組為空跳昼，查找失敗。
8.2 動圖展示
8.3 代碼演示
// 循環(huán)查找法
function binarySearch (arr, target) {
let low = 0, high = arr.length - 1
while (low <= high) {
let mid = Math.floor((low + high) / 2)
if ( target > arr[mid]) {
low = mid + 1
} else if (target < arr[mid]) {
high = mid - 1
} else { // mid = target
return mid
}
}
return -1
}
8.4 算法分析
二分查找的時間復雜度為O(logn)肋乍。雖然二分查找的時間復雜度為O(logn)但是比很多O(1)的速度都要快鹅颊，因為O(1)可能標示一個非常大的數(shù)值。
