排序算法可以说是数据结构与算法当中最为基础的部分，针对的是数组这一数据结构。将数组中的无序数据元素通过算法整理为有序的数据元素即为排序
算法一：插入排序
插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
步骤如下：
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置中
6. 重复步骤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)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
步骤如下：
* 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
* 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
//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)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
步骤如下：
* 遍历数组，找到最小的元素，将其置于数组起始位置。
* 从上次最小元素存放的后一个元素开始遍历至数组尾，将最小的元素置于开始处。
* 重复上述过程，直到元素排序完毕。
//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）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
步骤如下：
* 比较相邻的元素。如果第一个比第二个大，就交换他们两个，直到把最大的元素放到数组尾部。
* 遍历长度减一，对剩下的元素从头重复以上的步骤。
* 直到没有任何一对数字需要比较时完成。
//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）的一个非常典型的应用。
步骤如下：
1. 申请空间，创建两个数组，长度分别为两个有序数组的长度
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
//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// 辅助数组
internalMergeSort(&arr, low: 0, high: arr.count - 1, temp: &temp)
return arr
}
算法六：快速排序
快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤：
* 从数列中挑出一个元素，称为 “基准”（pivot），
* 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
* 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
//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
}
算法七：堆排序
s007.gif
堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
步骤如下：
* 按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；
* 将R[0..n-1]调整为堆，交换R[0]和R[n-1]；
* 重复上述过程，直到交换了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/
