前言
說到算法饮睬，就不得不說一下排序了沈跨，相信很多人的算法是從排序開始的，哪怕是算法導(dǎo)論這本書煤杀，也是從排序開始講的算法眷蜈，所以在說完了之前的各種算法是思想之后，是時候真刀真槍的干活了沈自。這一篇就說說算法中經(jīng)常遇到的各種排序算法（代碼使用kotlin實現(xiàn)）
- 冒泡排序
- 選擇排序
- 插入排序
- 希爾排序
- 快速排序
- 歸并排序
冒泡排序和選擇排序
為什么把這兩個放一起說呢，說到排序算法辜妓，冒泡排序和選擇排序可謂是基礎(chǔ)中的基礎(chǔ)了枯途，拿這兩個熱身是再好不過了
冒泡排序
定義
冒泡排序（Bubble Sort）忌怎，是一種計算機科學(xué)領(lǐng)域的較簡單的排序算法。
它重復(fù)地走訪過要排序的元素列酪夷，依次比較兩個相鄰的元素榴啸，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來晚岭。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換鸥印，也就是說該元素已經(jīng)排序完成。
這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列）坦报，就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣库说，故名“冒泡排序”
具體實現(xiàn)
fun bubbleSort(arr: IntArray?) {
if (arr == null || arr.size == 0)
return
for (i in 0 until arr.size - 1) {
for (j in arr.size - 1 downTo i + 1) {
if (arr[j] < arr[j - 1]) {
swap(arr, j - 1, j)
}
}
}
}
選擇排序
定義
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最衅瘛（或最大）的一個元素潜的，存放在序列的起始位置，然后字管，再從剩余未排序元素中繼續(xù)尋找最袉病（大）元素，然后放到已排序序列的末尾嘲叔。以此類推亡呵，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法
具體實現(xiàn)
fun selectSort(arr: IntArray?) {
if (arr == null || arr.size == 0)
return
var minIndex = 0
for (i in 0 until arr.size - 1) { //只需要比較n-1次
minIndex = i
for (j in i + 1 until arr.size) { //從i+1開始比較硫戈，因為minIndex默認(rèn)為i了锰什，i就沒必要比了。
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
if (minIndex != i) { //如果minIndex不為i掏愁，說明找到了更小的值歇由，交換之。
swap(arr, i, minIndex)
}
}
}
冒泡排序和選擇排序最標(biāo)志性的特征就是雙重for循環(huán)了果港，這也說明了沦泌，效率低的時候簡直不忍直視，這里就不多說了
插入排序和希爾排序
說完了冒泡排序和選擇排序辛掠，就接下來說說這兩貨了谢谦，插入排序和希爾排序，這兩貨的思想相差不大萝衩，甚至可以用一篇代碼實現(xiàn)回挽，自然就放一起了
插入排序
定義
插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列猩谊，對于未排序數(shù)據(jù)千劈，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入牌捷。其實我們玩撲克牌時的排序墙牌，用的就是插入排序
具體實現(xiàn)
fun insertSort(arr: IntArray?) {
if (arr == null || arr.size == 0)
return
for (i in 1 until arr.size) {
var j = i
val target = arr[i]
//后移
while (j >= 1 && target < arr[j - 1]) {
arr[j] = arr[j - 1]
j--
}
//插入
arr[j] = target
}
}
希爾排序
定義
希爾排序涡驮，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本喜滨。希爾排序是非穩(wěn)定排序算法
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進(jìn)方法的：
插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時捉捅，效率高，即可以達(dá)到線性排序的效率
但插入排序一般來說是低效的虽风，因為插入排序每次只能將數(shù)據(jù)移動一位
具體實現(xiàn)
fun shellSort(arr: IntArray) {
if (arr == null || arr.size == 0)
return
var step = arr.size / 2
while (step > 0) {
for (i in step until arr.size) {
var j = i
var target = arr[i]
while (j >= step && target < arr[j - step]) { //從后向前棒口，找到比其小的數(shù)的位置
arr[j] = arr[j - step] //向后挪動
j -= step
}
if (j != i) //存在比其小的數(shù)
arr[j] = target
}
step /= 2
}
}
仔細(xì)看插入排序和希爾排序的代碼，是不是發(fā)現(xiàn)兩者很相似辜膝，如果將希爾排序中的step設(shè)置為1无牵，那么它就是插入排序了，所以我說内舟，這兩者甚至可以用一篇代碼實現(xiàn)
快速排序和歸并排序
接下來再說說快速排序和歸并排序合敦，之前在分治法的文中提到了這兩種排序算法，它們都是分治法思想的算法验游，所以這里也是放一起說明
快速排序
定義
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分充岛，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序耕蝉，整個排序過程可以遞歸進(jìn)行崔梗，以此達(dá)到整個數(shù)據(jù)變成有序序列
具體實現(xiàn)
例如如圖：
- 首先設(shè)置兩個變量分別從頭和尾進(jìn)行索引
- 將第一個元素3存儲起來temp
- 從尾向前索引，找到第一個比3小的元素垒在，放入3的位置蒜魄，尾部索引減1，然后再從頭向尾索引场躯，找到第一個比3大的元素9谈为，放入0的位置，頭部索引加1
- 重復(fù)2踢关，3兩步伞鲫，知道兩個索引變量在某次減1或者加1的時候相等時為一次快速排序，然后以這個相等的變量為分割签舞，分別將它左邊和右邊的數(shù)組再次進(jìn)行同樣的快速排序操作秕脓，直到排序結(jié)束
- 例如這個數(shù)組，第二次從尾部索引找比3小的元素2儒搭，放入9的位置吠架，然后從頭部索引找比3大的元素，當(dāng)頭部索引和尾部索引都指向2時搂鲫，雖然此時頭部索引還沒有找到比3大的元素傍药，但是已經(jīng)完成一次快速排序了，所以講3放入此時索引指向的位置，這樣一次快速排序就結(jié)束了怔檩，然后不斷是循環(huán)即可
//快速排序 左閉右開
fun quickSort(arr: IntArray, left: Int, right: Int) {
if (left >= right)
return
val pivotPos = partition(arr, left, right)
quickSort(arr, left, pivotPos - 1)
quickSort(arr, pivotPos + 1, right)
}
//一個循環(huán)
fun partition(arr: IntArray, left: Int, right: Int): Int {
var left = left
var right = right
val pivotKey = arr[left]
while (left < right) {
while (left < right && arr[right] >= pivotKey)
right--
arr[left] = arr[right] //把小的移動到左邊
while (left < right && arr[left] <= pivotKey)
left++
arr[right] = arr[left] //把大的移動到右邊
}
arr[left] = pivotKey //最后把pivot賦值到中間
return left
}
歸并排序
定義
歸并排序是一個典型分治法思想的排序褪秀，它的思想是蓄诽，如果兩個序列是有序的薛训，那么將它們合成，依然可以得到一個有序序列仑氛，而對于一個無需的序列乙埃，將它拆分為足夠小的序列然后進(jìn)行排序，最后將這些有序序列合并锯岖，那么就可以得到一個有序的序列
具體實現(xiàn)
//歸并排序
fun mergeSort(array: IntArray, left: Int, right: Int) {
if (left == right) {
return
} else {
val mid = (left + right) / 2
mergeSort(array, left, mid)//左邊
mergeSort(array, mid + 1, right)//右邊
merge(array, left, mid + 1, right)//合并
}
}
//合并
fun merge(array: IntArray, left: Int, mid: Int, right: Int) {
val leftSize = mid - left
val rightSize = right - mid + 1
//生成數(shù)組
val leftArray = IntArray(leftSize)
val rightArray = IntArray(rightSize)
//填充左邊的數(shù)組
for (i in left until mid) {
leftArray[i - left] = array[i]
}
//填充右邊的數(shù)組
for (i in mid..right) {
rightArray[i - mid] = array[i]
}
//合并數(shù)組
var i = 0
var j = 0
var k = left
while (i < leftSize && j < rightSize) {
if (leftArray[i] < rightArray[j]) {
array[k] = leftArray[i]
k++
i++
} else {
array[k] = rightArray[j]
k++
j++
}
}
while (i < leftSize) {//左邊剩余數(shù)據(jù)
array[k] = leftArray[i]
k++
i++
}
while (j < rightSize) {//右邊剩余數(shù)據(jù)
array[k] = rightArray[j]
k++
j++
}
}
當(dāng)然介袜，還有很多各式各樣的排序算法，這里就不一樣列舉了出吹，大家有興趣可以自行探索
參考資料：
https://www.cnblogs.com/onepixel/articles/7674659.html
