常用的排序算法

思路：以数组中的第一个元素作为基准，对数组进行调整，使得左边的元素都小于基本，右边的元素都大于等于基准；然后再分别对左右两边的数组进行如上方法的排序

import numpy
def partition(nums, l, r):
    t = nums[l]
    start = l
    l+=1
    while l <= r:
        while l<=r and nums[l] <= t:
            l += 1
        while l<=r and nums[r] >= t:
            r -= 1
        if l > r:
            break
        nums[l], nums[r] = nums[r], nums[l]
        
    nums[start], nums[r] = nums[r], nums[start]
    return r

def quick_sort(nums, l, r):
    if l < r:
        parti_index = partition(nums, l, r)
        quick_sort(nums, l, parti_index - 1)
        quick_sort(nums, parti_index + 1, r)
    return nums

if __name__ == '__main__':
    nums = numpy.random.randint(0, 20, 8)
    nums = list(nums)
    l = 0
    r = len(nums)-1
    nums_sort = quick_sort(nums, l, r)
    print(nums_sort)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

归并排序

思路：首先将数组拆分成单个元素，然后取一对元素进行合并，直到所有的元素都合并后，得到的就是排序后的结果
```
def merge(arr1, arr2):
    i, j = 0, 0
    res = []
    while i
```

堆排序

思路：首先建堆，将数组看作是二叉树，然后自底向上进行调整，使得根节点的值大于等于左右子树的值，最终二叉树的根是最大值；

然后，将根节点从数组中移出，重新调整剩余数组的堆，每次调整后，堆顶元素就是当前数组的最大值。

也就是说，建成堆之后，不断对堆顶进行调整，每次获取当前的最大值

def heapify(arr, i, n):
    largest = i
    left = 2*i+1
    right = 2*i+2
    if leftarr[largest]:
        largest = left
    if rightarr[largest]:
        largest = right
    if largest!=i:
        arr[largest],arr[i] = arr[i],arr[largest]
        heapify(arr, largest, n)


def heap_sort(arr):
    n = len(arr)
    for i in range(n-1, -1,-1):
        heapify(arr,i,n)

    for j in range(n-1, 0, -1):
        arr[0], arr[j] = arr[j], arr[0]
        heapify(arr, 0, j)
    return arr

import numpy
arr = numpy.random.randint(0,20,8)
arr = list(arr)
# arr = [3,6,2,4,7]
print(arr)
arr_sort = heap_sort(arr)
print(arr_sort)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#快速排序衍生题目
def partition(arr, l, r):
    index = l
    p = arr[index]
    l +=1
    while(l<=r ):
        while(l<=r and arr[l]<=p):
            l+=1
        while(l<=r and arr[r]>=p):
            r-=1
        if(l>r):
            break
        arr[l], arr[r] = arr[r], arr[l]
    arr[index], arr[r] = arr[r], arr[index]
    return r
    
"""
最数组进行快速排序
"""
def quick_sort(arr, l, r):
    if(lk):
            r = m-1


"""
求最小的K个数
"""
def cal_small_k_nums(arr, l, r, k):
    if(k>=len(arr)):
        return arr
    while(l<=r):
        m = partition(arr, l, r)
        if(m==k):
            return arr[0:k]
        elif(m>k):
            r = m-1
        elif(m