10种排序算法总结(Python 版)

1. 冒泡排序( O ( n 2 ) O(n^2) O(n2))

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

def bubbleSort(nums):
    if not nums:
        return None
    
    for i in range(0, len(nums)):
        for j in range(0, len(nums)-i-1):
            if nums[j+1] < nums[j]:
                temp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = temp
    
    return nums

# test
nums = [4,1,5,2,3]
bubbleSort(nums)

[1, 2, 3, 4, 5]

2. 快速排序( O ( n l o g n ) O(nlogn) O(nlogn))

原理：利用分治的思想，将原数组分成两个部分，其中左边比中间数字小，右边比中间数字大。而这这划分的数字就是每个子数组的最后一个。
使用partition函数对数组进行重排，并返回当前划分的位置，再利用递归调用，对每个子数组进行重排，直到所有元素都完成重排。

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            temp = A[j]
            A[j] = A[i]
            A[i] = temp
    temp = A[r]
    A[r] = A[i+1]
    A[i+1] = temp
    return i+1 

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

A = [2, 8, 7, 1, 3, 5, 6, 4]
quicksort(A, 0, len(A)-1)
A

[1, 2, 3, 4, 5, 6, 7, 8]

3. 简单插入排序( O ( n 2 ) O(n^2) O(n2))

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

def insertionSort(nums):
    if not nums:
        return None
    
    for i in range(len(nums)-1):
        current = nums[i+1]
        preIndex = i
        while preIndex >=0 and current < nums[preIndex]:
            nums[preIndex + 1] = nums[preIndex]
            preIndex -= 1
        nums[preIndex + 1] = current
    
    return nums

# test
nums = [4,1,5,2,3]
insertionSort(nums)

[1, 2, 3, 4, 5]

4. 希尔排序( O ( n log ⁡ n ) O(n\log n) O(nlogn))

1. 我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
2. 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
3. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
4. 按增量序列个数k，对序列进行k 趟排序；
5. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

def shellSort(nums):
    if not nums:
        return None
    
    length = len(nums)
    gap = length // 2
    
    while gap > 0:
        for i in range(gap, length):
            temp = nums[i]
            preIndex = i - gap
            while preIndex >= 0 and nums[preIndex] > temp:
                nums[preIndex + gap] = nums[preIndex]
                preIndex -= gap
            nums[preIndex + gap] = temp
        gap = gap // 2
    
    return nums

#test
nums = [4,1,5,2,3]
shellSort(nums)

[1, 2, 3, 4, 5]

5. 简单选择排序( O ( n 2 ) O(n^2) O(n2))

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

1. 初始状态：无序区为R[1…n]，有序区为空；
2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化了。

def selectionSort(nums):
    if not nums:
        return None
    
    for i in range(len(nums)):
        minIndex = i
        for j in range(i, len(nums)):
            if nums[j] < nums[minIndex]:
                minIndex = j
        temp = nums[i]
        nums[i] = nums[minIndex]
        nums[minIndex] = temp
        
    return nums

# test
nums = [4,1,5,2,3]
selectionSort(nums)

[1, 2, 3, 4, 5]

6. 堆排序[ O ( n log ⁡ n ) O(n\log n) O(nlogn)]

原理：通过构造最大堆，每次把堆顶元素放到数组尾部，再调整最大堆的结构，直到最大堆的元素个数小于2。

伪代码：

维护最大堆： MAX-HEAPIFY
MAX-HEAPIFY(A, i):
​ l = LEFT(i) #(2i)
​ r = RIGHT(i) #(2i + 1)
​ if l <= A.heap_size and A[l] > A[i]:
​ largest = l
​ else:
​ largest = i
​ if r <= A.heap_size and A[r] > A[largest]:
​ largest = r
​ if largest != i:
​ exchange A[i] with A[largest]
​ MAX-HEAPIFY(A, largest)

生成最大堆：BUILD-MAX-HEAPIFY(A)
BUILD-MAX-HEAPIFY(A):
​ A.heap_size = A.length
​ for i = [A.length/2] downto 2:
​ MAX-HEAPIFY(A, i)

堆排序：HEAPSORT(A)
HEAPSORT(A):
​ BUILD-MAX-HEAPIFY(A)
​ for i = A.length downto 2:
​ exchange A[1] with A[i]
​ A.heap_size = A.heap_size - 1
​ MAX-HEAPIFY(A, 1)

def max_heapify(A, i, len):
    '''
    维护最大堆
    '''
    l = 2*i + 1
    r = 2*i + 2
    
    if l < len and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < len  and A[r] > A[largest]:
        largest = r
    
    if largest != i:
        temp = A[i]
        A[i] = A[largest]
        A[largest] = temp
        max_heapify(A, largest, len)
    return A

def build_max_heapify(A):
    '''
    构建最大堆
    '''
    for i in range(len(A) // 2-1, -1, -1):
        max_heapify(A, i, len(A))
        
def heapsort(A):
    '''
    堆排序
    '''
    build_max_heapify(A)
    for i in range(len(A)-1, 0, -1):
        temp = A[i]
        A[i] = A[0]
        A[0] = temp
        max_heapify(A, 0, i)
    


a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
heapsort(a)
a

[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

7. 归并排序( O ( n log ⁡ n ) O(n\log n) O(nlogn))

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

def mergeSort(nums):
    if len(nums) < 2:
        return nums
    mid = len(nums) // 2
    left = nums[ :mid]
    right = nums[mid: ]
    
    return merge(mergeSort(left), mergeSort(right))

def merge(left, right):
    res = []
    l, r = 0, 0
    for i in range(len(left)+len(right)):
        if l >= len(left):
            res.append(right[r])
            r += 1
        elif r >= len(right):
            res.append(left[l])
            l += 1
        elif left[l] > right[r]:
            res.append(right[r])
            r += 1
        else:
            res.append(left[l])
            l += 1
    
    return res

# test
nums = [4,1,5,2,3]
mergeSort(nums)

[1, 2, 3, 4, 5]

8. 计数排序( O ( n + k ) O(n+k) O(n+k))

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
   【只能对整数进行排序】

def countingSort(nums):
    if not nums:
        return None
    
    minNum, maxNum = nums[0], nums[0]
    for i in range(len(nums)):
        if nums[i] > maxNum:
            maxNum = nums[i]
        if nums[i] < minNum:
            minNum = nums[i]
    
    bias = 0 - minNum
    counter = [0]*(maxNum - minNum + 1)
    for i in nums:
        counter[bias + i] += 1
    
    index = 0
    i = 0
    while index < len(nums):
        if counter[i] != 0:
            nums[index] = i - bias
            counter[i] -= 1
            index += 1
        else:
            i += 1
    return nums

# test
nums = [4,1,5,2,3]
countingSort(nums) 

[1, 2, 3, 4, 5]

9. 桶排序( O ( n + k ) O(n+k) O(n+k))

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把数据一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

def bucketSort(nums, bucketSize):
    if not nums or bucketSize < 1:
        return None
    
    buckets = [[] for i in range(bucketSize)]
    
    # find max and min
    minNum, maxNum = nums[0], nums[0]
    for i in nums:
        if i > maxNum:
            maxNum = i
        if i < minNum:
            minNum = i
    
    gap = (maxNum+1 - minNum) / bucketSize
    
    for num in nums:
        insert(buckets[int((num - minNum) / gap)], num)
        
    # concat all bucket
    res = []
    for i in buckets:
        res += i
    
    return res
    
def insert(array, num):
    if array == [] or array[-1] <= num:
        array.append(num)
    else:
        for i in range(len(array)):
            if array[i] > num:
                array.insert(i, num)
                break


# test
nums = [63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109]
res = bucketSort(nums, 5)
print(sorted(nums))
print(res)

[13, 28, 47, 51, 63, 67, 98, 101, 109, 117, 121, 133, 139, 141, 156, 157, 157, 181, 189, 194]
[13, 28, 47, 51, 63, 67, 98, 101, 109, 117, 121, 133, 139, 141, 156, 157, 157, 181, 189, 194]

10. 基数排序( O ( n ∗ k ) O(n*k) O(n∗k))

1. 取得数组中的最大数，并取得位数；
2. arr为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）。

def radixSort(nums):
    if not nums:
        return 
    
    # 1. calculate the maximum number
    maxNum = nums[0]
    for i in nums:
        if maxNum < i:
            maxNum = i
            
    # 2. calculate the maximum digit
    maxDigit = 0
    while maxNum != 0:
        maxNum = maxNum // 10
        maxDigit += 1
    
    # 3. radix sort
    bucket = [[] for i in range(10)]
    div = 1
    for i in range(maxDigit):
        # save to bucket
        for j in range(len(nums)):
            bucket[(nums[j] // div) % 10].append(nums[j])
        
        # release to nums
        index = 0
        for k in range(10):
            while len(bucket[k]) != 0:
                nums[index] = bucket[k].pop(0)
                index += 1
        
        div *= 10
    
    return nums

# test
nums = [63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109]
res = radixSort(nums)
print(res)

[13, 28, 47, 51, 63, 67, 98, 101, 109, 117, 121, 133, 139, 141, 156, 157, 157, 181, 189, 194]