Swift实现七大排序算法

一、排序概念

• 排序：对一序列对象根据某个关键字进行排序。

• 稳定：如果 a 原本在 b 前面，而 a 与 b 的值相等，排序之后 a 仍然在 b 的前面；
  不稳定：如果 a 原本在 b 的前面，而 a 与 b 的值相等，排序之后 a 可能会出现在b的后面；

• 内排序：所有排序操作都在内存中完成；
  外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

• 排序耗时的操作：比较、移动；

• 排序分类：

  • 交换类：冒泡排序、快速排序；此类的特点是通过不断的比较和交换进行排序；
  • 插入类：简单插入排序、希尔排序；此类的特点是通过插入的手段进行排序；
  • 选择类：简单选择排序、堆排序；此类的特点是看准了再移动；
  • 归并类：归并排序；此类的特点是先分割后合并；

• 历史进程：一开始排序算法的复杂度都是在O(n^2)，希尔排序的出现打破了这个僵局。

二、排序算法

最简单的排序算法

最简单的排序实现，缺点是每次找最小值都是单纯的找，而没有为下一次寻找做出铺垫；

C 代码

//最简单的排序, arr表示数组首地址，count表示数组的元素个数
void simpleSort(int *arr, int count)
{
    for (int i = 0; i < count; i++) {
        for (int j = i+1; j < count; j++) {
            if (arr[i] > arr[j]) {
                swap(arr+i, arr+j);
            }
        }
    }
}

Swift 代码

func simpleSort(_ arr: [Int]) -> [Int] {
    var sortArr = arr;
    
    for i in 0..<sortArr.count {
        for j in (i+1)..<sortArr.count {
            if sortArr[i] > sortArr[j] {
                swap(&sortArr[i], &sortArr[j]);
            }
        }
    }
    return sortArr;
}

1. 冒泡排序

• 冒泡排序相对于最简单的排序有了改进，即每次交换都是对后续有帮助的，大数将会越来越大，小的数将会越来越小；
• 思想：两两相邻元素之间的比较，如果前者大于后者，则交换；

C 代码

//arr表示数组的首地址，count表示数组元素的个数
void bubbleSort(int *arr, int count)
{
    for (int i = 0; i < count; i++) {
        for (int j = 0; j < count - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr+j, arr+j+1);
            }
        }
    }
}

Swift 代码

func bubbleSort(_ arr: [Int]) -> [Int] {
    var sortArray = arr;
    
    //循环按照从后往前的顺序确定位置，依次确定最后一个位置、倒数第二个位置...
    for i in 0..<sortArray.count {
        for j in 0..<(sortArray.count-i-1) {
            if sortArray[j] > sortArray[j+1] {
                swap(&sortArray[j], &sortArray[j+1]);
            }
        }
    }
    return sortArray;
}

改进冒泡排序

• 如果出现一个序列，此序列基本是有序的，如果是标准的冒泡排序，则还是需要进行不断的比较；
• 改进方法：通过填加一个boolean类型的变量，如果一次循环中没有交换过元素，则说明已经排好序。
  C 代码

//最好：n-1次比较，不移动。因此时间复杂度为O(n)，不占用辅助空间。
//最坏：n(n-1)/2次比较和移动，因此为O(n^2)，占用交换的临时空间，大小为1；
void bubbleSort1(int *arr, int count)
{
    bool isChanged = true;
    for (int i = 0; i < count && isChanged; i++) {
        
        isChanged = false;
        for (int j = 0; j < count - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr+j, arr+j+1);
                isChanged = true;
            }
        }
    }
}

Swift 代码

//改进冒泡排序
//最好：n-1次比较，不移动位置。时间复杂度为O(n)，不占用辅助空间。
//最坏：n(n-1)/2次比较和移动，因此O(n^2)，占用交换的临时空间，大小为1。
func bubbleSort2(_ arr: [Int]) -> [Int] {
    var sortArray = arr;
    
    var isChanged = true;
    for i in 0..<sortArray.count {
        if !isChanged {
            break;
        }
        
        isChanged = false;
        for j in (i..<sortArray.count-1).reversed() {
            if sortArray[j] > sortArray[j+1] {
                swap(&sortArray[j], &sortArray[j+1]);
                isChanged = true;
            }
        }
    }
    return sortArray;
}

2. 简单选择排序

• 特点：每次循环找到最小值，并交换。因此交换次数始终为n-1次。
• 相对于最简单的排序，对不必要的交换做了改进，每个循环不断比较后记录最小值，只做了一次交换。（也可能不交换，当最小值已经在正确的位置）

C 代码

void selectSort(int *arr, int count)
{
    for (int i = 0; i < count; i++) {
        int min = i;
        for (int j = i+1; j < count; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        
        if (min != i) {
            swap(arr+i, arr+min);
        }
    }
}

Swift 代码

//最差：n(n-1)/2次比较，n-1次交换，因此时间复杂度为O(n^2)
//最好：n(n-1)/2次比较，不交换，因此时间复杂度为O(n^2)
//好于冒泡排序

func selectSort(_ arr: [Int]) -> [Int] {
    var sortArray = arr;
    
    for i in 0..<sortArray.count {
        var min = i;
        for j in i+1..<sortArray.count {
            if sortArray[min] > sortArray[j] {
                min = j;
            }
        }
        
        if min != i {
            swap(&sortArray[min], &sortArray[i]);
        }
    }
    return sortArray;
}

3. 简单插入排序

• 思想：给定序列，存在一个分界线，分界线的左边被认为是有序的，分界线的右边还没被排序。每次取没被排序的最左边一个和已排序的做比较，并插入到正确位置；我们默认索引 0 的子数组有序；每次循环将分界线右边的一个元素插入到有序数组中，并将分界线向右移一位；

C 代码

void insertSort(int *arr, int count)
{
    int j;
    for (int i = 1; i < count; i++) {
        int temp = arr[i];
        
        for (j = i; j > 0 && temp < arr[j-1]; j--) {
            arr[j] = arr[j-1];
        }
        
        //注意要插入的位置
        arr[j] = temp;
    }
}

Swift 代码

//最好：n-1次比较，0次移动，时间复杂度为O(n)
//最差：n(n-1)/2次比较，n(n-1)/2次移动，时间复杂度为O(n^2)
func insertSort(_ arr: [Int]) -> [Int] {
    var sortArray = arr;
    
    for i in 1..<sortArray.count {
        
        if sortArray[i] < sortArray[i-1] {
            let temp = sortArray[i];
            
            var index = i;
            for j in (0..<i).reversed() {
                
                if sortArray[j] > temp {
                    //如果没找到位置，继续寻找
                    sortArray[j+1] = sortArray[j];
                    
                    //记录位置
                    index = j;
                    continue;
                }
            }
            
            //找到位置, 插入数值
            sortArray[index] = temp;
        }
    }
    
    return sortArray;
}

4. 希尔排序

• 希尔排序是第一个突破O(n^2)的排序算法，是简单插入排序的改进版；
• 思想：由于简单插入排序对于记录较少或基本有序时很有效，因此我们可以通过将序列进行分组排序，使得每组容量变小，再进行分组排序，然后进行一次简单插入排序即可；
• 增量的选择十分重要，可以选择length/2这样的方式，也是希尔建议的增量，称为希尔增量。另外，增量最小为1。
  C 代码

//希尔排序的步长选择从length/2开始，每次再减半，直到最后为1。其实也可以有另外的更高效的步长选择，不过最后需要保证增量为1。
void shellSort(int *arr, int count)
{
    int increment = count;
    do {
        //设置希尔初始增量为数组长度的一半
        increment = increment / 2;
        if (increment == 0) {
            increment = 1;
        }
        
        int j;
        for (int i = increment; i < count; i++) {
            int temp = arr[i];
            
            //j指向有序区的最后一个元素
            for (j = i-increment; j >= 0 && temp < arr[j]; j -= increment) {
                arr[j+increment] = arr[j];
            }
            
            //找到合适的位置，插入元素
            arr[j+increment] = temp;
        }
    } while (increment > 1);
}

Swift 代码

//希尔排序的步长选择从length/2开始，每次再减半，直到最后为1。其实也可以有另外的更高效的步长选择，不过最后需要保证增量为1。
func shellSort(_ arr: [Int]) -> [Int] {
    var sortArray = arr;
    
    var increment = arr.count;
    repeat {
        //设置希尔初始增量为数组长度的一半
        increment = increment / 2;
        if increment == 0 {
            increment = 1;
        }
        
        for i in increment..<sortArray.count {
            let temp = sortArray[i];
            
            //j指向有序区的最后一个元素
            var j = i - increment;
            
            //循环找到合适的位置插入元素
            while j >= 0 && temp < sortArray[j] {
                sortArray[j+increment] = sortArray[j];
                j -= increment;
            }
            
            sortArray[j+increment] = temp;
        }
    } while increment > 1;
    return sortArray;
}

5. 堆排序

• 大根堆：任意父结点都比子结点大；
  小根堆：任意父结点都比子结点小；
• 堆排序是不稳定的排序算法，是简单选择排序的改进版。
• 堆的存储：一般用数组来表示堆，若根结点存在序号 0 处，i 结点的父结点下标就为 (i-1)/2。i 结点的左、右子结点下标分别为 2*i+1 和 2*i+2。如果根节点是从 1 开始，则左、右子结点分别是 2i 和 2i+1。
• 完全二叉树有 n 个结点，则拥有 n/2 个非叶子结点。（取整）
• 思想：构建一颗完全二叉树。首先构建大根堆，然后每次把根节点（最大值）和最后的节点（最小值）互换，然后将数组长度减一。之后重新构建大根堆，以此类推。
• 注意：此排序方法不适用于个数少的序列，因为初始构建需要时间。
  C 代码

//堆排序
void heapSort(int *arr, int count)
{
    //1.首先构建大根堆
    for (int i = (count-1)/2; i >= 0; i--) {
        heapAdjust(arr, i, count);
    }
    
    //2.将根结点与尾结点互换，数组长度减去1，重新构建大根堆
    for (int i = 1; i < count; i++) {
        swap(arr, arr+count-i);
        heapAdjust(arr, 0, count-i);
    }
}

//调整数组为大根堆，parent表示根节点的下标，count表示要调整的数组长度
void heapAdjust(int *arr, int parent, int count)
{
    //保存根结点的数值
    int temp = arr[parent];
    
    //获取根节点的左子节点（下标从0开始）
    for (int i = parent * 2 + 1; i < count; i = i * 2 + 1) {
        //找到左、右子结点的较大者
        if (i < count-1 && arr[i] < arr[i+1]) {
            i = i + 1;
        }
        
        //根结点大于等于左、右子结点
        if (temp >= arr[i]) {
            break;
        }
        
        //将根结点与左、右子结点较大者替换
        arr[parent] = arr[i];
        
        //再次检查子结点的子结点
        parent = i;
    }
    
    arr[parent] = temp;
}

Swift 代码

func heapSort(_ arr: [Int]) -> [Int] {
    var sortArray = arr;
    let count = sortArray.count;
    
    //首先建立大根堆
    //先找到最后一个拥有子结点的根结点
    var i = count / 2 - 1;
    while i >= 0 {
        heapAdjust(&sortArray, parent: i, count: count);
        i -= 1;
    }
    
    //进行排序
    for i in 1..<count {
        //将最后一个元素和第一个元素进行交换
        swap(&sortArray[0], &sortArray[count-i]);
        
        //数组的长度减一，然后将剩下的无序数组调整为大根堆
        //由于只是头结点无序，所以只需要调整头结点即可，其他结点不需要调节
        heapAdjust(&sortArray, parent: 0, count: count-i);
    }
    return sortArray;
}

//调整指定结点以下为大根堆，parent表示父结点的下标，count表示要调整的数组长度
func heapAdjust(_ arr: inout [Int], parent: Int, count: Int) {
    //保存根结点的数值
    let temp = arr[parent];
    var parent = parent;
    
    //获取根结点的左子结点
    var i = parent * 2 + 1;
    while i < count {
        if i < count-1 && arr[i] < arr[i+1] {
            //记录左右子结点的较大者
            i = i + 1;
        }
        
        //如果根节点数大于子结点数，则中止循环，否则沿着一路循环下去
        if temp >= arr[i] {
            break;
        }
        
        //将较大值赋值到根结点
        arr[parent] = arr[i];
        
        //更新当前根结点的位置
        parent = i;
        
        //寻找parent的左子结点进行下一轮循环
        i = i * 2 + 1;
    }
    arr[parent] = temp;
}

6. 归并排序

• 稳定的排序算法
• 思想：利用递归进行分割和合并，分割直到长度为1为止，并在合并前保证两序列原本各自有序，合并后也有序。
  C 代码

//归并排序
void mergeSort(int *arr, int count)
{
    for (int gap = 1; gap < count; gap = 2 * gap) {
        mergePass(arr, gap, count);
    }
}

//gap表示字表的长度，count表示数组的个数
void mergePass(int *arr, int gap, int count)
{
    
    //需要合并的两个序列的计算：
    //low = 2 * gap * i;
    //mid = low + gap - 1;
    //high = low + 2 * gap - 1;
    //这里的i就代表low，要合并的第一个序列的最小下标
    
    int i = 0;
    for (i = 0; i + 2 * gap - 1 < count; i = i + 2 * gap) {
        mergeArray(arr, i, i + gap - 1, i + 2 * gap - 1);
    }
    
    //可能有奇数个元素，有则合并剩下的序列
    if (i + gap - 1 < count) {
        mergeArray(arr, i, i + gap - 1, count - 1);
    }
}

//合并数组元素，low表示第一段序列的最小下标，mid表示第一段序列的最大下标，high表示第二段序列的最高下标
void mergeArray(int *arr, int low, int  mid, int high)
{
    int i = low;            //第一段序列的下标
    int j = mid + 1;        //第二段序列的下标
    int k = 0;              //k是存放合并序列的下标
    
    int *array = (int *)malloc((high - low + 1) * sizeof(int));    //申请临时空间
    
    //扫描第一段和第二段序列，直到有一个扫描结束
    while(i <= mid && j <= high) {
        //判断第一段和第二段取出的数哪个更小，将其加入合并序列，并继续向下扫描
        if (arr[i] < arr[j]) {
            array[k] = arr[i];
            i++;
            k++;
        } else {
            array[k] = arr[j];
            j++;
            k++;
        }
    }
    
    //若第一段序列还没扫描完，将其全部复制到合并序列
    while (i <= mid) {
        array[k] = arr[i];
        i++;
        k++;
    }
    
    //若第二段序列还没扫描完，将其全部复制到合并序列
    while (j <= high) {
        array[k] = arr[j];
        j++;
        k++;
    }
    
    //将合并序列复制到原始序列中
    for (k = 0, i = low; i <= high; i++, k++) {
        arr[i] = array[k];
    }
    
    //释放空间
    free(array);
}

Swift 代码

//归并排序
func mergeSort(_ arr: inout [Int]) {
    var gap = 1;
    while gap < arr.count {
        mergePass(&arr, gap: gap);
        
        gap *= 2;
    }
}

//分解合并序列
func mergePass(_ arr: inout [Int], gap: Int) {
    var i = 0;
    let count = arr.count;
    
    while i + 2 * gap - 1 < count {
        mergeArray(&arr, low: i, mid: i + gap - 1, high: i + 2 * gap - 1);
        
        i += 2 * gap;
    }
    
    //合并剩余的序列
    if i + gap - 1 < count {
        mergeArray(&arr, low: i, mid: i + gap - 1, high: count - 1);
    }
}

//合并两个序列
func mergeArray(_ arr: inout [Int], low: Int, mid: Int, high: Int) {
    
    var i = low;
    var j = mid + 1;
    var k = 0;
    
    var array = Array<Int>(repeating: 0, count: high - low + 1);
    
    while i <= mid && j <= high {
        if arr[i] < arr[j] {
            array[k] = arr[i];
            i += 1;
            k += 1;
        } else {
            array[k] = arr[j];
            j += 1;
            k += 1;
        }
    }
    
    while i <= mid {
        array[k] = arr[i];
        i += 1;
        k += 1;
    }
    
    while j <= high {
        array[k] = arr[j];
        j += 1;
        k += 1;
    }
    
    //将排序好的序列复制回原数组
    k = 0;
    for i in low...high {
        arr[i] = array[k];
        
        k += 1;
    }
}

7. 快速排序

• 冒泡排序的升级版，现在用的最多的排序方法；
• 思想：选取pivot，将pivot调整到一个合理的位置，使左边的值都小于它，右边的值都大于它；
• 注意，如果序列基本有序或者序列个数较少，则可以采用简单插入排序。因为快速排序对这些情况效率不高。
  C 代码

//快速排序
void quickSort(int *arr, int low, int high)
{
    if (low < high) {
        int key = partition(arr, low, high);
        
        //对数组左边进行排序
        quickSort(arr, 0, key);
        
        //对数组右边 进行排序
        quickSort(arr, key+1, high);
    }
}

//划分数组，左边的数据都小于piovt，右边的数据都大于piovt
int partition(int *arr, int low, int high)
{
    int piovtKey = arr[low];            //这个地方可以优化
    
    while (low < high) {
        //遍历右边，直到小于piovtKey
        while (low < high && arr[high] >= piovtKey) {
            high--;
        }
        arr[low] = arr[high];
        
        //遍历左边，直到大于piovtKey
        while (low < high && arr[low] <= piovtKey) {
            low++;
        }
        arr[high] = arr[low];
    }
    //将piovtKey赋值到中间位置
    arr[low] = piovtKey;
    
    //返回中间位置，low和high都可以，此时low与high相等
    return low;
}

Swift 代码

//快速排序
func quickSort(_ arr: inout [Int], low: Int, high: Int) {
    if low < high {
        let p = partition(&arr, low: low, high: high);
        //左边递归排序
        quickSort(&arr, low: 0, high: p);
        
        //右边递归排序
        quickSort(&arr, low: p+1, high: high);
    }
}

//将数组分成两部分，左边部分小于pivotKey的值，右边部分大于pivotKey的值
func partition(_ arr: inout [Int], low: Int, high: Int) -> Int {
    var low = low;
    var high = high;
    let pivotKey = arr[low];
    
    while low < high {
        //循环右边，直到小于pivotKey
        while low < high && arr[high] >= pivotKey {
            high -= 1;
        }
        arr[low] = arr[high];
        
        //循环左边，直到大于pivotKey
        while low < high && arr[low] <= pivotKey {
            low += 1;
        }
        arr[high] = arr[low];
    }
    
    //将pivotKey放置到中间的位置，返回划分的位置
    arr[low] = pivotKey;
    return low;
}

快速排序优化方案

• 选取pivot：选取pivot的值对于快速排序至关重要，理想情况，pivot应该是序列的中间数。前面我们只是简单的取第一个数作为pivot，这点可以进行优化。
• 优化方法：抽多个数后取中位数作为pivot。
• 对于小数组使用插入排序：因为快速排序适合大数组排序。如果是小数组，则效果没有简单插入排序效果好。

三、排序总结

• 数组长度不大的情况下不宜使用归并排序，其它排序差别不大。
• 数组长度很大情况下希尔排序最快，快速排序其次，冒泡排序最慢。

总结：每个排序都有各自的特点，我们需要在适当的时候用适当的算法。比如在基本有序、数组规模小的时候用直接插入排序；比如在大数组时用快速排序；比如想要稳定性，则使用归并排序；

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	稳定
直接插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
希尔排序	O(n^1.3)	O(n)	O(n^2)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn) ~ O(n)	不稳定