9种排序方法及python实现(冒泡,插入,希尔,选择,堆,快速,桶,基数,归并排序)_小言_互联网的博客

9种排序方法及python实现(冒泡,插入,希尔,选择,堆,快速,桶,基数,归并排序)

2020-05-06 14:21 535人阅读评论(0)

1. 排序算法分类

排序算法可以分为外部排序和内部排序：
（1）外部排序 (External sorting）是指能够处理极大量数据的排序算法。

通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。

在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。

（2）内部排序还可以细分：
需要额外内存空间（out-place,即空间复杂度不是 $O(1)$ ）的算法有：桶排序，基数排序，归并排序; 其他算法一般只需常量的内存空间(in-place,原地排序)。

以下介绍9种内部排序：

2. 冒泡法

冒泡法的步骤：从左到右遍历，遍历的元素和后一个比较，如果前一个比后一个大，则交换；第一次遍历后，最大的元素在最右的位置。以相同的方式遍历，次大的元素放置在倒数第2的位置；直到需要比较的元素只有1个为止。

import numpy as np
import time
def bubbleSort(arr):
    # 冒泡法
    for i in range(len(arr)-1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr 
def get_arr(num=10):
	# 生成随机的大小为num的数组
    np.random.seed(1)
    arr = np.random.randint(0,num,(num,))
    return arr 
    
if __name__ == "__main__":
    # 冒泡法
    arr = get_arr()
    print('arr',arr)
    arr = bubbleSort(arr)
    print(arr)

运行结果：

arr [5 8 9 5 0 0 1 7 6 9]
#排序后 
arr [0 0 1 5 5 6 7 8 9 9]

3. 插入排序

插入排序，是把当前的数插入到前面排序好的序列相应位置，使得序列保持单调性。

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def insertionSort(arr):
    for i in range(len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:
                swap(arr, j, j-1)
            else:
                break
    return arr 

arr = insertionSort(arr)

4. 希尔排序

希尔排序对插入排序改进，定义一个步长序列，不再只是相邻的两个元素进行比较。

步长序列	最坏情况下复杂度
$n/2^i$	$\mathcal{O} {\displaystyle (n^{2})}$
$2^{k}-1$	${\displaystyle {\mathcal {O}}} (n^{3/2})$
$2^{i}3^{j}$	${\displaystyle {\mathcal {O}}}( n\log^2 n )$

def shellSort(arr):
    # 希尔排序
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap, len(arr)):
            j = i
            while (j >= gap) and (arr[j] < arr[j-gap]):
                swap(arr, j, j-gap)
                j = j-gap
        gap = gap//2
    return arr

5. 选择排序

选择排序是，遍历一遍，找到最小的元素，然后交换到最左边，重复这个过程。和冒泡法相比，它遍历一遍，只交换一次。

def selectSort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        swap(arr, min_idx, i)
    return arr

6. 堆排序

堆排序使用二叉树的数据结构，需要满足，父节点值不小于儿子节点。
堆排序，通过建立一个最大堆，即根节点的值最大,然后把根节点和最后一个叶节点交换；剩下的数重新建立一个最大堆，获得次大值，继续和叶节点交换；重复这个过程，直到堆的大小为1。

def heapSort(arr):
    def siftDown(arr, index, length=None):
        '''sift_down'''
        if length is None:
            length = len(arr)
        # 最大堆；子节点总小于父节点, O(n)
        while True:
            left = 2*index + 1
            right = 2*index + 2
            max_idx = left
            if left >= length:
                break
            if right<length and arr[right] > arr[left]:
                max_idx = right
            if arr[index] < arr[max_idx]:
                arr[index], arr[max_idx] = arr[max_idx],arr[index]
                index = max_idx
            else:
                break
    # 初始化最大堆 O(n)
    for idx in range(len(arr)//2-1, -1, -1):
        siftDown(arr, idx, len(arr))

    # 堆排序，交换最大值和最后一个叶节点, O(nlogn)
    for length in range(len(arr)-1, -1, -1):
        arr[length], arr[0] = arr[0], arr[length]
        siftDown(arr, 0, length)
    return arr

7. 快速排序

快速排序是常用的排序算法。思想是，选择一个基准，遍历一遍，把数分成两堆，比基准小的放在数组左边，比基准大的放在数组右边，最后，交换基准到两者的分界处；对基准左边和右边的子数组重复进行快速排序，直到子数组只有1个元素。

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
    
def qsort(arr, low, high):
    left, right = low, high
    if left < right:
        while left < right:
            pivot = select_base(arr, low, high)
            # 基准放在最左边low
            swap(arr, low, pivot)
            # 从右到左遍历，选择比基准小的元素
            while left < right and arr[right] >= arr[low]:
                right -= 1
            # 从左到右遍历，选择比基准大的元素
            while left < right and arr[left] <= arr[low]:
                left += 1
            swap(arr, left, right)
        # 最终 left = right，该位置元素不大于基准
        swap(arr, low, right)
        qsort(arr, low, right-1)
        qsort(arr,right+1, high)
        
def quickSort(arr):
    qsort(arr,0,len(arr)-1)

quickSort(arr)

直到一提是，常见选择基准可以取最左边的元素，但是可能最左边的元素是数组的最小值或者最大值，导致左右子数组的数量相差悬殊，排序效率低的情形。因此，取三个数的平均值作为基准。

此外，在遍历数组时，这里使用了双指针两个方向进行遍历，但如单链表只有一个方向进行遍历，实现的话定义两个指针，一个指针记录两堆的分界，一个指针向前遍历直到找到比基准小的值，然后和分界后一个元素交换，更新两堆的分界。

8. 桶排序和计数排序

桶排序是，把值映射函数后，得到索引，根据索引放入相应的有大小排序的桶，然后桶内的元素进行排序（如插入排序），然后合并所有的桶，获得排序后的序列。

如果桶的数量足够多，和序列的范围一样，那么，每个桶放入和桶本身值一样的数值，并且累积数量。最后遍历所有的桶，按照数量来打印桶的值，得到排序后的序列，这也叫计数排序。

def bucketSort(arr, radix=10):
    '''radix,基数代表一个桶最大容纳多少个不同的数；
    当radix=1, 桶排序相当于计数排序.'''
    def get_index(val, min_a):
        return (val - min_a) // radix
    max_a = max(arr)
    min_a = min(arr)
    bucket_num = (max_a - min_a)//radix + 1
    bucket = [[] for _ in range(bucket_num)]
    # 放入桶中
    for val in arr:
        index = get_index(val, min_a)
        bucket[index].append(val)
    index = 0
    for bk in bucket:
        # 桶内进行排序
        bk = insertionSort(bk)
        for val in bk:
            arr[index] = val
            index += 1
    return arr

这里桶排序有点像哈希表，都是经过散列函数（映射函数），把值放入相应的键（桶）中。和哈希表不同之处，在于桶排序要求的映射函数必须是单调函数，这样才有意义，哈希表的散列函数需要满足不同的值映射后的值尽可能不一样。

9. 基数排序

基数排序是，先根据各个数的低位，进行排序；排序后的数组，根据次低位进行排序，重复直到完成最高位的比较，输出排序的序列。

def radixSort(arr,radix=10):
    '''基数排序，radix为基数'''
    K = len(str(max(arr)))
    for i in range(K):
        bucket = [[] for _ in range(10)]
        for val in arr:
            if len(str(val))-i >= 1:
                num = int(str(val)[len(str(val))-i-1])
                bucket[num].append(val)
            else:
                bucket[0].append(val)
        # 合并桶
        del arr
        arr = []
        for bk in bucket:
            arr.extend(bk)
    return arr

这里为了方便，使用了10为基数。基数代表值由什么进制表示。radix 可以取2，当时取位的时候，也得先把值转化成2进制：

val%(radix**i)//(radix**(i-1))

这里 $i$ 代表取值 val 在 radix 进制下的第几位。

10. 归并排序

归并排序是通过不断的划分成两个子数组，直到子数组只有1个值(相当于排序好了)，然后不断合并两个排序好的子数组，直到合并成原来大小的数组。

def merge(arr, left, mid, right):
    l = left
    r = mid+1
    n_arr = [0 for _ in range(right-left+1)]
    index = 0
    while l <= mid and r<=right:
        if arr[l] > arr[r]:
            n_arr[index] = arr[r]
            r += 1
        else:
            n_arr[index] = arr[l]
            l += 1
        index += 1
    while l <= mid:
        n_arr[index] = arr[l]
        index += 1
        l += 1
    while r <= right:
        n_arr[index] = arr[r]
        index += 1
        r += 1
    # 拷贝排序完成的arr
    for i in range(len(n_arr)):
        arr[left+i] = n_arr[i]
        
def mSort(arr, left, right):
    if left < right:
        mid = (left+right)//2
        mSort(arr, left, mid)
        mSort(arr, mid+1, right)
        merge(arr, left, mid, right)
        
def mergeSort(arr):
    mSort(arr, 0, len(arr)-1)
    return arr
arr = mergeSort(arr)

11. 总结

不同排序方法的复杂度：

实践测试，选择大小为10000的随机数组，经过这几种算法排序，花费的时间：
比如：

import time
# 冒泡法
arr = get_arr()
start = time.time()
arr = bubbleSort(arr)
end = time.time()
print('冒泡法use {:.4f}'.format(end-start))

运行结果：

# O(n + k)
桶排序use 0.0160
# O(n*k)
基数排序use 0.0748
# O(nlogn)
归并排序use 0.0917
# O(nlogn)
快排use 0.1123
# O(nlogn)
堆排序use 0.1207
# O(nlogn)
希尔排序use 0.1466

# O(n^2)
选择排序use 11.3514
# O(n^2)
插入排序use 17.5552
# O(n^2)
冒泡法use 21.4438

参考：

转载：https://blog.csdn.net/rosefun96/article/details/105945212

查看评论

小言_互联网的博客

小言_互联网的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章