Swift实现常用排序算法集合

sort.swift

//
//  main.swift
//  SortDemo
//
//  Created by jackyshan on 2018/8/7.
//  Copyright © 2018年 GCI. All rights reserved.
//

import Foundation

print("Hello, World!")

func bubbleSort() {//冒泡排序
    var list = [61,5,33,44,22]
    for i in 0..<list.count {//找到符合条件的数进行交换
        for j in i+1..<list.count {
            if list[j] > list[i] {
                let temp = list[j]
                list[j] = list[i]
                list[i] = temp
            }
        }
    }
    
    print(list)
}

func chooseSort() {//选择排序
    var list = [61,5,33,44,22]
    for i in 0..<list.count {
        var max = i//记录当前最大的数，比较i+1后更大的数进行记录
        for j in i+1..<list.count {
            if list[j] > list[max] {
                max = j
            }
        }
        
        let temp = list[max]
        list[max] = list[i]
        list[i] = temp
    }
    
    print(list)
}

func insertSort() {//插入排序
    var list = [61,5,33,44,22]
    
    var nlist = [list[0]]//建立一个空数，符合条件的插入，没插入的尾后添加
    for i in 1..<list.count {
        var max: Int? = nil
        for j in 0..<nlist.count {
            if list[i] > nlist[j] {
                max = i
                nlist.insert(list[i], at: j)
                break
            }
        }
        
        if max == nil {
            nlist.append(list[i])
        }
    }
    
    print(nlist)

}

func insertSortOne() {//插入排序 通过交换
    var list = [61,5,33,44,22]
    
    for i in 1..<list.count {
        var y = i//从i往前找，符合条件交换
        
        while y>0 && list[y] > list[y-1] {
            let temp = list[y]
            list[y] = list[y-1]
            list[y-1] = temp
            y -= 1
        }
    }
    
    print(list)
    
}

func insertSortTwo() {//插入排序 通过移动
    var list = [61,5,33,44,22]
    
    for i in 1..<list.count {
        var y = i//从i往前找，符合条件移动
        let temp = list[y]
        while y>0 && temp > list[y-1] {
            list[y] = list[y-1]
            y -= 1
        }
        
        list[y] = temp//找到y赋值
    }
    
    print(list)
    
}

func quickSort(list: inout [Int], left: Int, right: Int) {
    if left > right {//左边往右边移，右边往左边移动，最后过了就停止
        return
    }
    
    var i, j, pivot: Int
    
    i = left
    j = right
    pivot = list[left]
    
    while i != j {
        
        while list[j] <= pivot && i < j {//右边大的往左移动
            j -= 1
        }
        
        while list[i] >= pivot && i < j {//左边小的往右移动
            i += 1
        }
        
        if i < j {//找到两个对方区域的值进行交换
            let temp = list[i]
            list[i] = list[j]
            list[j] = temp
        }
    }
    
    list[left] = list[i]//此时i和j相等，处于中间位置，替换pivot值
    list[i] = pivot
    
    //重复以上动作
    quickSort(list: &list, left: left, right: i-1)
    quickSort(list: &list, left: i+1, right: right)
}


func heapSort(arr:inout Array<Int>) {
    //1.构建大顶堆
    for i in (0...(arr.count/2-1)).reversed(){//从二叉树的一边的最后一个节点开始
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(arr: &arr, i: i, length: arr.count)
    }
    //2.调整堆结构+交换堆顶元素与末尾元素
    for j in (1...(arr.count-1)).reversed(){
        arr.swapAt(0, j)//将堆顶元素与末尾元素进行交换
        adjustHeap(arr: &arr, i: 0, length: j)//重新对堆进行调整
    }
}

/**
 * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
 */
func adjustHeap(arr:inout Array<Int>,i:Int,length:Int) {
    var i = i;
    let temp = arr[i];//先取出当前元素i
    var k=2*i+1
    while k<length {//从i结点的左子结点开始，也就是2i+1处开始
        if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
            k+=1;
        }
        if(arr[k] > temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            arr[i] = arr[k];
            i = k;//记录当前节点
        }else{
            break;
        }
        k=k*2+1//下一个节点
    }
    arr[i] = temp;//将temp值放到最终的位置
}

func shellSort(arr: inout [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
    }
}

var list = [61,5,33,44,22]
shellSort(arr: &list)
print(list)