数组-快速排序

采用快速方式对数组进行排序

快速排序百科:快速排序(Quicksort)是对冒泡排序算法的一种改进.
快速排序是通过多次比较和交换来实现排序.

摘一个示例做个说明.
示例 1：
输入: [0,5,9,3,12,7]
输出: [0,3,5,7,9,12]

算法原理:

1. 首先设定一个分界值,通过该分界值将数组分成左右两部分
2. 将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组左边.此时左边部分中各元素都小于或等于分界值,而右边部分各元素都大于或等于分界值
3. 然后左边和右边的数据可以独立排序.对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样左边放小值,右边放大值.右侧的数组数据也可以做类似处理
4. 重复上述步骤,可以看出,这是一个递归.通过递归将左侧部分排好序后,再递归排好右侧部分的顺序.等左右都排好时,数组的排序就完成了

性能分析:

1. 时间复杂度
   理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过 log ₂n 趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(n log ₂n).

   最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n²).

   快速排序的平均时间复杂度也是O( n log ₂n )。因此，该排序方法被认为是目前最好的一种内部排序方法.

2. 空间复杂度
   从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log₂(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(log₂n).

3. 算法稳定性
   快速排序就是把比分界值小的元素往前调,然后再找分界值继续比较,会打乱相同元素的顺序.
   综上,快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动.

代码实现-Swift版本:

func quickSort(nums: inout [Int], low: Int, high: Int){
    // 通过循环判断,让小数据添加到分界值左边,大的在右边组成数组数据
    if low > high {
        return
    }
    var i = low
    var j = high
    
    let key = nums[i]//分界值
    while i < j {// 如果左指针小于右指针
        while i < j && nums[j] > key {//先找到第一个右指针比分界值小的数据
            j -= 1
        }
        nums[i] = nums[j] //赋值分界值位置数据为右指针小数据
        while i < j && nums[i] <= key {//再找到左边第一个比分界值大的数据
            i += 1
        }
        nums[j] = nums[i] // 赋值右指针数据为左指针大数据
    }
    nums[i] = key // 恢复分界值位置数据(循环后,分界值位置数据已经被覆盖,随着i的递增,分界位置也发生变化)
    quickSort(nums: &nums, low: low, high: i - 1)// 左递归
    quickSort(nums: &nums, low: i + 1, high: high)// 右递归
}

测试用例:

var nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

参考:

• 快排百科
  在这说明一下未引用大神动图的原因,是因为,根据百科原理,发现动图和百科不匹配.所以这篇文章就没有动图了哈.看这个不要参考那个动图,思路是对不上滴.

考察要点:

• 数组
• 排序