算法学习：快速排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法学习：快速排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1652字，纯文字阅读大概需要3分钟。

内容图文

1、基本思想

取待排序数组第一个数作为参照数，建立left和right数组，left存储小于参照数的数组集合，right存储大于参照数的数组集合，然后分别对left和right进行递归调用排序。 ? 2、举例

[11,2,3,43,23,5,6,9,10]
取任意的一个数为基准数
temp = arr[0]
遍历数组，将比temp小的元素放在temp的左边，比temp大的元素放在temp的右边
left+【temp】+right
然后对左边和右边的元素分别进行quicksort
[3,21,1,999,9,2,2]
temp =3 
left = [1]
right = [21]

[1,3,21]

 

3、实现步骤

先从数列中取出一个数作为基准数
分区过程，将比这个数大的数全放到它的右边
将小于或等于它的数全放到它的左边
再对左右区间重复第二步，直到各区间只有一个数

 

4、实现方法1

def quickSort(start_idx,end_idx,arr): 
    """start_idx和end_idx确定排序区间""" 
    if start_idx>=end_idx:
        return arr
    low,high = start_idx,end_idx#设定2个指针分别执行待排序数组的起始和结束位置 
    temp=arr[low]#设置基准数temp = arr[low]
    while low<high:
        while low< high and arr[high]>=temp:#从队尾向前扫描，如果队尾的数小于temp将队尾的数放在low的位置 
            high-=1
        arr[low] = arr[high]
        while low<high and arr[low]<temp:#从队首向后扫描，如果队首的数大于temp将队首的数放在high的位置
            low+=1 
        arr[high] = arr[low]
    arr[low] = temp 
    quickSort(start_idx,low,arr) 
    quickSort(low+1,end_idx,arr) 
    return arr

 

5、实现方法2

def quickSort02(arr):
    if not arr:
        return arr
    temp = arr[0]
    left = [x for x in arr[1:] if x<=temp]
    right= [x for x in arr[1:] if x>temp]
    return quickSort02(left)+[temp]+quickSort02(right)


print(quickSort02([1,45,23,28,33,22,1,-1]))
#结果 [-1, 1, 1, 22, 23, 28, 33, 45]

 

 6、快速排序的时间复杂度和空间复杂度

??时间复杂度:为O(nlogn) ? 空间复杂度:快速排序使用递归，递归使用栈，因此它的空间复杂度为O(logn) ? 稳定性:快速排序无法保证相等的元素的相对位置不变，因此它是不稳定的排序算法

内容总结

以上是互联网集市为您收集整理的算法学习：快速排序全部内容，希望文章能够帮你解决算法学习：快速排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---