排序算法可以說是數(shù)據(jù)結(jié)構(gòu)與算法當(dāng)中最為基礎(chǔ)的部分，針對的是數(shù)組這一數(shù)據(jù)結(jié)構(gòu)。將數(shù)組中的無序數(shù)據(jù)元素通過算法整理為有序的數(shù)據(jù)元素即為排序
算法一：插入排序
插入排序（Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
步驟如下：
1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置中
6. 重復(fù)步驟2
//MARK:- 插入排序
func insertSort(inout arr: [Int]) -> [Int] {
for i in 1 ..< arr.count {
let key = arr[i]
var j = i - 1
while j >= 0 && arr[j] > key {
arr[j + 1] = arr[j]
j -= 1
}
arr[j + 1] = key
}
return arr
}
算法二：希爾排序
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。
步驟如下：
* 希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；
* 隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
//MARK:- 希爾排序
func shellSort(inout arr: [Int]) -> [Int] {
var j: Int
var gap = arr.count / 2
while gap > 0 {
for i in 0 ..< gap {
j = i + gap
while j < arr.count {
if arr[j] < arr[j - gap] {
let temp = arr[j]
var k = j - gap
while (k >= 0 && arr[k] > temp) {
arr[k + gap] = arr[k]
k -= gap
}
arr[k + gap] = temp
}
j += gap
}
}
gap /= 2
}
return arr
}
算法三：選擇排序
選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到排序序列末尾。以此類推，直到所有元素均排序完畢。
步驟如下：
* 遍歷數(shù)組，找到最小的元素，將其置于數(shù)組起始位置。
* 從上次最小元素存放的后一個(gè)元素開始遍歷至數(shù)組尾，將最小的元素置于開始處。
* 重復(fù)上述過程，直到元素排序完畢。
//MARK:- 選擇排序
func selectionSort(inout arr: [Int]) -> [Int] {
for i in 0 ..< arr.count - 1 {
var min = i
for j in i+1 ..< arr.count {
if arr[min] > arr[j] {
min = j
}
}
let temp = arr[min]
arr[min] = arr[i]
arr[i] = temp
}
return arr
}
算法四：冒泡排序
冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端。
步驟如下：
* 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)，直到把最大的元素放到數(shù)組尾部。
* 遍歷長度減一，對剩下的元素從頭重復(fù)以上的步驟。
* 直到?jīng)]有任何一對數(shù)字需要比較時(shí)完成。
//MARK:- 冒泡排序
func bubbleSort(inout arr: [Int]) -> [Int] {
for i in 0 ..< arr.count {
for j in 0 ..< arr.count - 1 - i {
if arr[j] > arr[j + 1] {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
算法五：歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。
步驟如下：
1. 申請空間，創(chuàng)建兩個(gè)數(shù)組，長度分別為兩個(gè)有序數(shù)組的長度
2. 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3. 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動(dòng)指針到下一位置
4. 重復(fù)步驟3直到某一指針達(dá)到序列尾
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
//MARK:- 歸并排序
func mergeSort(inout arr: [Int]) -> [Int] {
func merge (inout arr: [Int], low: Int, mid: Int, high: Int, inout temp: [Int]) {
var i = low
var j = mid + 1
let m = mid
let n = high
var k = 0
while (i <= m && j <= n) {
if (arr[i] <= arr[j])
{
temp[k] = arr[i]
k += 1
i += 1
}
else
{
temp[k] = arr[j]
k += 1
j += 1
}
}
while i <= m {
temp[k] = arr[i]
k += 1
i += 1
}
while j <= n {
temp[k] = arr[j]
k += 1
j += 1
}
for f in 0 ..< k {
arr[low + f] = temp[f]
}
}
func internalMergeSort(inout arr: [Int], low: Int, high: Int, inout temp: [Int]) {
if high <= low {
return
}
let mid = low + (high - low) / 2
// 左邊有序
internalMergeSort(&arr, low: low, high: mid, temp: &temp)
// 右邊有序
internalMergeSort(&arr, low: mid + 1, high: high, temp: &temp)
// 將兩邊合起來
merge(&arr, low: low, mid: mid, high: high, temp: &temp)
}
var temp: [Int] = arr// 輔助數(shù)組
internalMergeSort(&arr, low: 0, high: arr.count - 1, temp: &temp)
return arr
}
算法六：快速排序
快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
步驟：
* 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot），
* 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
* 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
//MARK:- 快速排序
func quickSort(inout arr: [Int]) -> [Int] {
func partition(p: Int, _ r: Int) -> Int {
var i = p - 1
let key = arr[r]
for j in p ..< r {
if arr[j] < key {
i = i + 1
let temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
}
}
arr[r] = arr[i + 1]
arr[i + 1] = key
return i + 1
}
func internalQuickSort(p: Int, _ r: Int) {
if p < r {
let q = partition(p, r)
internalQuickSort(p, q - 1)
internalQuickSort(q + 1, r)
}
}
internalQuickSort(0, arr.count - 1)
return arr
}
算法七：堆排序
堆排序（Heap Sort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
步驟如下：
* 按堆的定義將數(shù)組R[0..n]調(diào)整為堆（這個(gè)過程稱為創(chuàng)建初始堆），交換R[0]和R[n]；
* 將R[0..n-1]調(diào)整為堆，交換R[0]和R[n-1]；
* 重復(fù)上述過程，直到交換了R[0]和R[1]為止。
//MARK:- 堆排序
func heapSort(inout arr: [Int]) -> [Int] {
func buildheap(inout arr: [Int]) {
let length = arr.count
let heapsize = length
var nonleaf = length / 2 - 1
while nonleaf >= 0 {
heapify(&arr, i: nonleaf, heapsize: heapsize)
nonleaf -= 1
}
}
func heapify(inout arr: [Int], i : Int, heapsize: Int){
var smallest = i
let left = 2*i+1
let right = 2*i+2
if(left < heapsize){
if(arr[i]>arr[left]){
smallest = left
}
else {
smallest = i
}
}
if(right < heapsize){
if(arr[smallest] > arr[right]){
smallest = right
}
}
if(smallest != i){
var temp: Int
temp = arr[i]
arr[i] = arr[smallest]
arr[smallest] = temp
heapify(&arr,i: smallest,heapsize: heapsize)
}
}
func internalHeapSort(inout arr: [Int]) {
var heapsize = arr.count
buildheap(&arr)
for _ in 0 ..< arr.count - 1 {
var temp: Int
temp = arr[0]
arr[0] = arr[heapsize - 1]
arr[heapsize - 1] = temp
heapsize = heapsize - 1
heapify(&arr, i: 0, heapsize: heapsize)
}
}
internalHeapSort(&arr)
return arr
}
參考
http://codecloud.net/sort-2208.html
http://wenzhiquan.github.io/2016/03/28/seven_sort/
