Bella's Blog
0%

数据结构之快速排序

发表于 分类于 Valine：
本文字数： 859 阅读时长 ≈ 1 分钟

自己做了一些动画深刻理解数据结构之快速排序

快速排序

原理

思想：让元素归位在它应该在的位置，即它左边的要比它小，它右边的要比它大。

原始数组

image-20240419105800362

左右指针分别从数组始末位置开始

image-20240419105846172

左指针的元素拿出来，空出位置

image-20240419110106686

右指针开始从末端向前移动寻找比5小的元素，比5大的元素不做任何操作，继续向前找

image-20240419110230572

直到找到2

image-20240419110323804

这时把数组右指针数值赋值给数组左指针位置

image-20240419110608848

右边空出，再从左边移动左指针找比5大的值，找到7

image-20240419110735465

交换赋值，空出左指针元素

image-20240419110843045

继续重复操作，直到左指针与右指针重合，整个过程如下

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def partion(data, left, right):
    tmp = data[left]
    while left<right:
        while left<right and data[right]>= tmp:   #移动右指针，找比tmp小的值
            right = right-1
        data[left]= data[right]
        while left<right and data[left]<= tmp:    #移动左指针，找比tmp大的值
            left = left+1
        data[left]= data[right]
     data[left]=tmp                               #直到左指针与右指针碰头
    return left
def sort_quick(data, left, right):
    if left<right:
    	mid = partion(data, left, right)
        sort_quick(data, left, mid-1)
        sort_quick(data, mid+1, right)
    return data

时间复杂度

不严谨理解，O(nlogn)

image-20240419114011832