Skip to content

Instantly share code, notes, and snippets.

@jackyshan jackyshan/sort.swift
Created Aug 10, 2018

Embed
What would you like to do?
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.