常见十大排序算法：
冒泡排序、选择排序、插入排序、快速排序、堆排序
希尔排序、归并排序、计数排序、基数排序、桶排序
冒泡排序
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
排序原理:
- 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
- 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。
func bubbleSort (array: Array<Int>) -> Array<Int> {
var tempArray = array;
for i in 0..<tempArray.count {
for j in 0..<tempArray.count-1-i { // 相邻两个进行比较
if tempArray[j] < tempArray[j+1] { // 交换
tempArray.swapAt(j, j+1)
}
}
}
return tempArray;
}
时间复杂度分析: 冒泡排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，
时间复杂度：O(N^2)
空间复杂度：O(1)
选择排序
选择排序是一种更加简单直观的排序方法。
排序原理:
1.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引
2.交换第一个索引处和最小值所在的索引处的值
func selectSort (array: Array<Int>) -> Array<Int> {
var tempArray = array;
for i in 0..<tempArray.count {
var index = i;
for j in (i+1)..<tempArray.count { // 相邻两个进行比较
if tempArray[index] < tempArray[j]{ // 交换
index = j;
}
}
tempArray.swapAt(index,i)
}
return tempArray;
}
时间复杂度分析: 选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据交换次数和数据比较次数：
时间复杂度：O(N^2)
空间复杂度：O(1)
插入排序
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。
排序原理:
1.把所有的元素分为两组，已经排序的和未排序的；
2.找到未排序的组中的第一个元素，向已经排序的组中进行插入；
3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；
方式1 for-while：
func insertSort (array: Array<Int>) -> Array<Int> {
var tempArray = array;
for i in 1..<tempArray.count {
var j = i
while j > 0 && tempArray[j - 1] < tempArray[j] { // 3
tempArray.swapAt(j - 1, j)
j -= 1
}
}
return tempArray;
}
方式2 for-for：
func insertSort (array: Array<Int>) -> Array<Int> {
var tempArray = array;
for i in 1..<tempArray.count {
for j in stride(from: i, to: 0, by:-1) { // 递减遍历 不包括0
if tempArray[j-1] < tempArray[j]{ // 交换
tempArray.swapAt(j - 1, j)
}else{
break;
}
}
}
return tempArray;
}
时间复杂度分析: 插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码：
时间复杂度：O(N^2)
空间复杂度：O(1)
快速排序
快速排序是对冒泡排序的一种改进。
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
排序原理:
首先设定一个分界值，通过该分界值将数组分成左右两部分；
2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
func quickSort (array:inout Array<Int> ,lo :Int, hi:Int) -> Array<Int> {
if lo >= hi {
return array;
}
let sortIndex = partition(array: &array, low: lo, high: hi)
quickSort(array: &array, lo: lo, hi: sortIndex-1)
quickSort(array: &array, lo: sortIndex+1, hi: hi)
return array
}
func partition (array: inout Array<Int> ,low :Int, high:Int) -> Int {
let pivot = array[high]
var index = low;
for i in low...high-1 {
if array[i] > pivot { // 基准值比较
array.swapAt(i, index)
index = index+1
}
}
if high != index { // 基准值归位
array.swapAt(high,index)
}
return index
}
时间复杂度分析: 插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码：
时间复杂度：O(nlogn)
空间复杂度：O(1)
希尔排序
希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
排序原理:
1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
2.对分好组的每一组数据完成插入排序；
3.减小增长量，最小减为1，重复第二步操作。
func shellSort (array: Array<Int>) -> Array<Int> {
var tempArray = array;
let count:Int = array.count
var gap:Int = 1
let base:Int = 3 // 最小步长 3
while (gap < count / base) {
gap = base * gap + 1; // 首次最大步长，至少为数组的一半+1
}
while gap > 0 { //当增长量h小于1，排序结束
for i in gap..<count { //tempArraya[i]就是待插入的元素
for j in (gap...i).reversed() {
if tempArray[j] < tempArray[j-gap]{
tempArray.swapAt(j, j-gap)
}
}
}
gap = gap / base
}
时间复杂度分析: 插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码：
时间复杂度：O(N^2)
空间复杂度：O(1)
归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
排序原理:
1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是
1为止。
2.将相邻的两个子组进行合并成一个有序的大组；
3.不断的重复步骤2，直到最终只有一个组为止。
// 递归方式
func mergeSort(array:Array<Int>) ->Array<Int> {
guard array.count > 1 else { return array }
let middleIndex = array.count / 2 // 均分数组
let leftArray = mergeSort(array:Array(array[0..<middleIndex])) // 数组左半区
let rightArray = mergeSort(array:Array(array[middleIndex..<array.count])) // 数组右半区
return merge(left: leftArray, right: rightArray) // 合并最终数组
}
func merge(left: Array<Int>, right: Array<Int>) -> Array<Int>{
var leftIndex = 0
var rightIndex = 0
var tempArray = [Int]();
while leftIndex < left.count && rightIndex < right.count { // 存在数据
if left[leftIndex] < right[rightIndex] { // 添加左半区元素
tempArray.append(left[leftIndex])
leftIndex+=1;
}else if left[leftIndex] > right[rightIndex] {
tempArray.append(right[rightIndex]) // 添加右半区元素
rightIndex+=1;
}else {
tempArray.append(left[leftIndex])
leftIndex+=1;
tempArray.append(right[rightIndex])
rightIndex+=1;
}
}
while leftIndex < left.count { // 添加剩余全部左半区元素
tempArray.append(left[leftIndex])
leftIndex+=1;
}
while rightIndex < right.count {
tempArray.append(right[rightIndex]) // 添加剩余全部右半区元素
rightIndex+=1;
}
return tempArray
}
时间复杂度分析: 插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码：
时间复杂度：O(nlogn)
空间复杂度：O(n) 以空间换时间的操作。
网友评论