快速排序Python代码实现
快速排序(Quick Sort)是通过分治的思想来进⾏排序。它的主要思想是：取数组中的⼀个数作为
基准值(往往取数组中的第⼀个数)，把所有⼩于基准值的数都放在它的左侧，再把所有⼤于基准值的数都放在它的右侧。随后，对基准值左右两侧的数组分别进⾏快速排序。
快速排序的平均时间复杂度是O（)，最好情况下的时间复杂度是O()。最坏情况下，快速排序的时间复杂度可能退化为O()，但这种情况很少见。快速排序是⼀个不稳定的算法，如果使⽤得当，快速排序的速度可以达到归并排序和堆排序的数倍，所以快速排序是⼀种极其常⽤的算法。
写了三种⽅法，思路都是⼀样的，具体细节不⼀样。
第⼀种⽅法⽐较简单，也好理解
nums = [5, 6, 4, 5, 3, 1, 8, 9, 7]
def QuickSort(num):
# 若列表长度为1，直接输出不⽤排序
if len(num) <= 1:
return num
# 取数组的第⼀个数作为基值
key = num[0]
# 定义空列表⽤来储存⼤于/⼩于/等于基准值的元素
llist, mlist, rlist = [], [], []
# 定义空列表⽤来储存⼤于/⼩于/等于基准值的元素
for i in range(0, len(num)):            # 遍历列表，把元素归类到三个列表中
if num[i] < key:
llist.append(num[i])
elif num[i] > key:
rlist.append(num[i])
else:
mlist.append(num[i])
# 对左右两个列表进⾏快排，拼接三个列表并返回
return QuickSort(llist) + mlist + QuickSort(rlist)
print(QuickSort(nums))
以这种⽅法来实现快速排序需要额外的开辟空间给⽤于归类的列表。并且相似的思路⽤于其他的编程语⾔是效率低。
那么，我们就需要对这种⽅法来进⾏优化。此时，⽤⼀个变量来储存基准值，然后⽤两个指针，⼀个在最左边从左往右遍历，另⼀个在最右边从⼜往左遍历。开始遍历的时候可以把基准值在数组中的位置，也就是第⼀个元素，视作⼀个没有元素的空位。
第⼀步，先移动右指针，从右往左移动，直到指针指向的元素⼩于基准值为⽌。并把右指针指向的值赋给左指针指向的位置
第⼆部，移动左指针，从左往右移动，直到指针指向的元素⼤于等于基准值时停下。并把左指针指向的值赋给右指针指向的位置。
第三步，重复以上操作，不断交替移动左右指针并赋值。
第四步，当左右指针重合时，所有必要的移动都已经完成。左右指针共同指向的位置就是基准值在有序数组中的位置。它的值⼤于它左侧所有的元素并⼩于它右侧所有的元素。剩余操作为递归排序左右⼦数组，直到全部数组排序完成。
# QSort
nus = [4, 5, 1, 2, 3, 5, 4, 1]
# left,right分别为⼦数组中第⼀个元素和最后⼀个元素在原数组中的位置
def QSort(left, right):
# 边界条件
if left >= right:
return
# 初始化左右指针的初始值
l, r, key = left, right, nus[left]
# 调整元素的位置
while l < r:
while l < r and nus[r] >= key:
r -= 1
nus[l] = nus[r]
while l < r and nus[l] <= key:
l += 1
nus[r] = nus[l]
# 把基准值赋给左右指针共同指向的位置
nus[r] = key
# 对左侧数组排序
QSort(left, l-1)
# 对右侧数组排序
QSort(l+1, right)
QSort(0, len(nus) - 1)
print(nus)
相对于第⼀种⽅法，这种⽅法解决了需要开辟空间的问题，元素与元素之间在原来的数组内部进⾏位置的交换，。但是这中⽅法没有采⽤直接将数组传⼊函数的⽅法，⽽是把⼦数组第⼀个和最后⼀个元素的位置穿⼊函数中，就导致了在实际使⽤的时候并不⽅便，因为每次使⽤的时候就需要调整。
python 定义数组这就需要第三种⽅法，既包含了前两种⽅法的优点使⽤起来也⾮常⽅便，⾸先这种⽅法需要需要把数组
传⼊函数当中，然后再运⽤指针交换的形式来进⾏快速排序。
def QSort(lst, left, right):
if left >= right:
return
l, r, key = left, right, lst[left]
while l < r:
while l < r and lst[r] >= key:
r -=1
lst[l] = lst[r]
while l < r and lst[l] < key:
l += 1
lst[r] = lst[l]
lst[l] = key
QSort(lst, left, l-1)
QSort(lst, l+1, right)
return lst
nus = [4, 5, 1, 2, 3, 5, 4, 1]
print(QSort(nus, 0, len(nus) - 1))

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。