算法好難鞍俳摇！寫點(diǎn)簡單的蜓席。然后用JavaScript實(shí)現(xiàn)器一。
排序算法（Sorting Algorithm）
概念
一種能將一串資料依照特定排序方式進(jìn)行排列的一種算法
一般規(guī)則
- 輸出結(jié)果為遞增（遞減）序列
- 輸出結(jié)果是原輸入的一種排列或是重組
分類方式
- 依據(jù)計算的 時間復(fù)雜度 分類
- 概念：完成一個算法所用的時間
- 表示：O()，變量為 n（表示輸入的長度）
- 最好：O(n log n)
- 最壞：O(n2)
- O(n): 無序數(shù)組的搜索
- O(log n): 二分搜索
- O(n log n):
- 比較排序（最好的）
- 快速排序（最好的）
- 堆排序
- O(n2):
- 冒泡排序
- 插入排序
- 選擇排序
- 依據(jù) 記憶體使用量（以及其他電腦資源的使用） 分類
- 依據(jù) 穩(wěn)定性 分類
- 例如對 (1,2) (1,3) (2,1) 中的第一個數(shù)字排序厨内，會有兩種結(jié)果
- (1,2) (1,3) (2,1)
- (1,3) (1,2) (2,1)
- 這種現(xiàn)象就是不穩(wěn)定性
- 不穩(wěn)定排序算法可能會在相等的鍵值中改變紀(jì)錄的相對次序
- 穩(wěn)定的排序：
- 冒泡排序
- 插入排序
- 歸并排序
- 計數(shù)排序 O(n + m)
- 基數(shù)排序 O(k*n)
- 桶排序
- 不穩(wěn)定的排序：
- 快速排序
- 選擇排序
- 希爾排序 O(n log2 n)
- 堆排序
- 例如對 (1,2) (1,3) (2,1) 中的第一個數(shù)字排序厨内，會有兩種結(jié)果
- 依據(jù) 排序的方式 分類
- 插入
- 插入排序
- 希爾排序
- 選擇
- 選擇排序
- 堆排序
- 交換
- 冒泡排序
- 快速排序
- 歸并
- 歸并排序
- 分布
- 基數(shù)排序
- 計數(shù)排序
- 桶排序
- 并發(fā)
- 混合
- 其他
- 插入
冒泡排序（Bubble Sort）
原理：
- 比較相鄰兩個元素 a祈秕，b 的大小，如果 a < b 隘庄，b 就和 a 互換位置
（遍歷一輪之后踢步，最后一個元素最小癣亚，最后一個元素不參與下一輪比較） - 然后再次遍歷
- 直到?jīng)]有元素需要交換位置
舉例說明：
有數(shù)組 arr = [a,b,c,d]丑掺，
- 那么 arr[0] 和 arr[1] 比較胳喷， arr[1] 和 arr[2] 比較即彪， arr[2] 和 arr[3] 比較驳庭，
- 得到新的 arr1肘交，那么 arr1[0] 和 arr1[1] 比較， arr1[1] 和 arr1[2] 比較唆缴，
- 得到新的 arr2鳍征，那么 ar2r[0] 和 arr2[1] 比較，
- 完成面徽！
所以外層循環(huán)次數(shù)為 (arr.length - 1)
內(nèi)層循環(huán)次數(shù)由 (arr.length - 1) 開始艳丛，每次減一
代碼實(shí)現(xiàn)：
function BubbleSort(arr){
var n = arr.length
var temp
for(var i = 0; i < n - 1; i++){
for(var j = 0; j < n - 1 - i; j++){
if(arr[j] < arr[j + 1]){
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
var arr = [9,14,2,7,3]
SelectionSort(arr)
選擇排序（Selection Sort）
原理：
- 從一堆元素中找出最大（小）的元素趟紊，放在第一位
- 從剩下的元素中繼續(xù)找出最大（械）的元素，放在第二位
- 依次類推
- 直到完成
- 通過位置交換進(jìn)行排序
舉例說明：
有數(shù)組 arr = [a,b,c,d]霎匈，
- 假設(shè) arr[0] 為最小值戴差，然后和其他元素比較，如果遇到更小的铛嘱，交換位置
- 遍歷一輪后暖释，交換位置后的 arr[0] 為最小值
- 然后將剩余的元素按這種方法繼續(xù)排序
- 完成！
代碼實(shí)現(xiàn)：
function SelectionSort(arr){
var n = arr.length
var temp
for(var i = 0; i < n -1; i++){
for(var j = 1 + i; j < n; j++){
if(arr[i] > arr[j]){
temp = arr[j]
arr[j] = min
arr[i] = temp
}
}
}
return arr
}
var arr = [9,14,2,7,3]
SelectionSort(arr)
插入排序（Insertion Sort）
原理：
- 以第一個元素為基準(zhǔn)墨吓，開始排序
- 后面的元素依次從后往前與前面的元素比較球匕，如果小，則插到該元素之前
舉例說明：
有數(shù)組 arr = [a,b,c,d]
- 先將 arr[0] 排在第一位
- 然后排 arr[1] 肛真，與 arr[0] 比較
- 然后排 arr[2] 谐丢，依次和 arr[1]，arr[0] 比較
- 然后排 arr[3] 蚓让，依次和 arr[2]乾忱，arr[1]，arr[0] 比較
- 完成历极！
動畫示例：
代碼實(shí)現(xiàn)：
function InsertionSort(arr){
for(var i = 1; i < arr.length; i++){
for(var j = 0; j < i; j++){
if(arr[i] < arr[j]){
arr.splice(j,0,arr[i])
arr.splice(i+1,1)
}
}
}
return arr
}
var arr = [9,14,2,7,3]
InsertionSort(arr)
希爾排序（遞減增量排序算法）（Shell Sort）
原理：
舉例說明：
代碼實(shí)現(xiàn)：
function ShellSort(){
}
歸并排序（Merge Sort）
原理：
舉例說明：
代碼實(shí)現(xiàn)：
function MergeSort(){
}
動畫示例：
快速排序（Quick Sort）
原理：
舉例說明：
代碼實(shí)現(xiàn)：
function QuickSort(){
}
堆排序（Heap Sort）
原理：
舉例說明：
代碼實(shí)現(xiàn)：
function HeapSort(){
}
桶排序（Bucket Sort）
原理：
- 利用映射關(guān)系窄瘟，準(zhǔn)備一些桶，將需要排序的元素放到對應(yīng)的桶里趟卸，最后去掉空的桶
舉例說明：
有數(shù)組 arr = [1,9,2,4]蹄葱，這里列舉最理想的情況一個元素對應(yīng)一個桶
- 準(zhǔn)備九個桶（最大元素個數(shù)個桶），從1~9排好
- 將arr[0] 放到1號桶锄列，arr[1] 放到9號桶图云，arr[2] ，放到2號筒邻邮，arr[3]竣况，放到4號桶
- 去掉空的桶
- 完成！
代碼實(shí)現(xiàn)：
function BucketSort(arr){
var newArr = [] //數(shù)組的每個位置可以看成是一個桶
var result = [] //用來存放結(jié)果
var len = [] //這里優(yōu)化對浮點(diǎn)數(shù)的桶排序
var buckets = 0
for(var k = 0; k < arr.length; k++){
if(parseInt(arr[k]) !== arr[k]){
len.push(String(arr[k]).split('.')[1].length)
}
}
if(len.length !== 0){
buckets = Math.pow(10,Math.max.apply(null,len))
}
for(var i = 0; i < arr.length; i++){
newArr[arr[i]*buckets] = arr[i]
}
for(var j = 0; j < newArr.length; j++){
if(newArr[j] !== undefined){
result.push(newArr[j])
}
}
return result
}
var arr = [9,2.33,3.14,5.998,23,7]
BucketSort(arr)
計數(shù)排序（Counting Sort）
原理：
舉例說明：
代碼實(shí)現(xiàn)：
function CountingSort(){
}
基數(shù)排序（Radix Sort）
原理：
舉例說明：
代碼實(shí)現(xiàn)：
function RadixSort(){
}
