Swift - 快速排序_app

概述思想基本思想 : 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再递归每一部分，得到最后结果步骤设置一个pivot,一般取第一个元素从后向前找一个比pivot元素小的数,交换位置(将大元素与pivot交换) 从前向后找一个比pivot大的元素,交换位置(小元素与交换后的pivot位置交换.此时得到一大一小分治于pivot的两边) 重复思想

基本思想 : 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再递归每一部分，得到最后结果

步骤设置一个pivot,一般取第一个元素从后向前找一个比pivot元素小的数,交换位置(将大元素与pivot交换) 从前向后找一个比pivot大的元素,交换位置(小元素与交换后的pivot位置交换.此时得到一大一小分治于pivot的两边) 重复递归1.2.3步骤代码

import Foundation//快速排序 var unsortedList : [Int] = []//排序20个 0-99的随机整数 for i in 0..<20 {     unsortedList.append(Int(arc4random_uniform(UInt32(100)))) }print("快排原始数组 : \(unsortedList)\n\n")//统计一下快排的次数var sortCount : Int = 0//时间复杂度为O(NlogN)quickSort(&unsortedList,low: 0,high: unsortedList.count - 1)//递归调用private func quickSort(_ List : inout [Int],low : Int,high : Int){    if low < high {        let prePivot = quickSortNode(&List,low: low,high: high)        quickSort(&List,high: prePivot - 1)        quickSort(&List,low: prePivot + 1,high: high)    }}//单次快排private func quickSortNode(_ List : inout [Int],high : Int) -> Int{    var low = low    var high = high    let pivot = List[low]    //上下未相遇    while low < high {        //从后面找一个比pivot小的数,填入pivot位置        while low < high && List[high]>=pivot {            high -= 1        }        List[low] = List[high]        //从前面找一个比pivot大的数,填入刚刚放入位置        while low < high && List[low]<=pivot {            low += 1        }        List[high] = List[low]    }    //pivot放入坑    List[low] = pivot    //统计快排次数的    sortCount += 1    print("第\(sortCount)次快排后的结果 result:\(List)\n")    return low}