Python排序算法

Posted on   |   Updated on | In | | Visitors

快速排序

快排算是应用中广泛的排序算法了。由于实现简单，适用于不同的输入数据且在一般应用中比其他排序算法要快。快排的一个特点是原地排序，内循环比大多数排序算法要短小。它的主要缺点是非常脆弱，在实现中要非常小心才能避免低劣的性能。

快排是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。快排和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序，递归调用发生在处理整个数组之前；而快排将数组排序的方式则是当两个子数组都有序时整个数组自然也就有序了，递归调用发生在处理整个数组之后。

按照《算法第4版》中的例子，实现一个标准的python解法。

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
import random

def quick_sort(a):
    random.shuffle(a)  # 消除输入依赖，保持随机性，也可使用随机选取切分元素
    quick_sort_divide(a, 0, len(a)-1)  

def quick_sort_divide(a, lo, hi):
    if hi <= lo:
        return
    j = partition(a, lo, hi)
    quick_sort_divide(a, lo, j-1)
    quick_sort_divide(a, j+1, hi)
    
def partition(a, lo, hi):
    i, j = lo+1, hi
    pivot = a[lo]  # 选取第一个元素作为切分元素
    while True:
        while a[i]<pivot and i<hi:  # 遇到大于等于pivot时停止，某些情况可以避免算法运行时间变为平方级别
            i += 1
        while a[j]>pivot and j>lo:
            j -= 1
        if i >= j:
            break
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    a[lo], a[j] = a[j], a[lo]
    return j

写法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def sortArray(self, nums: List[int]) -> List[int]:

    def q_sort(lo, hi):
        if lo >= hi: return 
        m = (lo + hi) // 2
        l, r = lo, hi
        pivot = nums[m]
        while l <= r:
            while l<=r and nums[l]<pivot:
                l += 1
            while l<=r and nums[r]>pivot:
                r -= 1
            if l<=r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
        q_sort(lo, r)
        q_sort(l, hi)

    random.shuffle(nums)
    q_sort(0, len(nums)-1)

性能分析：

  • 内循环使用一个递增的索引将数组元素和一个定值比较，相对于归并和希尔的在内循环中移动数据的方法更快，更简洁。
  • 比较的次数很少。排序效率依赖切分数组的效果。

基于Dijkstra-三路快排实现：当数组中包含大量重复的元素时，上述快排做出了一些无意义的切分。从左到右遍历数组，维护一个指针lt使a[lo..lt-1]中的元素都小于p，一个指针gt使得a[gt+1..hi]中的元素都大于p，一个指针i使得a[lt..i-1]中的元素都等于p，由于Python可以返回元组，所以改写成三路非常简单。

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
import random

def q3_sort(a):
    random.shuffle(a)
    q_divide(a, 0, len(a)-1)
    
def q_divide(a, lo, hi):
    if lo >= hi:
        return
    i, j = partition(a, lo, hi)
    q_divide(a, lo, i)
    q_divide(a, j, hi)
    
def partition(a, lo, hi):
    lt, i, gt = lo, lo+1, hi
    p = a[lo]
    while i <= gt:
        if a[i] < p:
            a[i], a[lt] = a[lt], a[i]
            lt += 1
            i += 1
        elif a[i] > p:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1
        else:
            i += 1
    return lt-1, gt+1

冒泡排序

1
2
3
4
5
6
7
8
9
def sortArray(self, nums: List[int]) -> List[int]:
    n = len(nums)
    for i in range(n):
        flag = True
        for j in range(n-i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                flag = False
        if flag: break

选择排序

1
2
3
4
5
6
7
8
def select_sort(nums: list) -> list:
    n = len(nums)
    for i in range(n-1):
        min_i = i
        for j in range(i+1, n):
            if nums[min_i] > nums[j]:
                min_i = j
        nums[min_i], nums[i] = nums[i], nums[min_i]

插入排序

1
2
3
4
5
6
7
8
9
10
def insertion(ary: list) -> list:
    for i in range(1, len(ary)):
        val, index = ary[i], i
        for j in range(i-1, -1, -1):
            if ary[j] > val:
                ary[j+1] = ary[j]
                index = j
            else:
                break
        ary[index] = val

希尔排序

使用切片的方式实现了一个简单的希尔排序，但是希尔排序应该是不产生空间的。

1
2
3
4
5
6
7
8
9
def shell_sorted(nums):
    res = list(nums)
    n = len(res)
    step = round(n/2)
    while step > 0:
        for i in range(step):
            res[i:n:step] = insert_sorted(res[i:n:step])
        step = round(step/2)
    return res

归并排序

原地归并

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
def merge_sort(nums: list):
    _merge_divide(nums, 0, len(nums)-1)

def _merge_divide(a, l, r):
    if l >= r:
        return
    mid = (l + r) // 2
    _merge_divide(a, l, mid)
    _merge_divide(a, mid+1, r)
    _merge(a, l, mid, r)
	
def _merge(a, l, mid, r):
    aux = []
    i, j = l, mid + 1
    if a[mid] <= a[mid+1]:	# 有序则跳出
        return
    while i<=mid and j<=r:
        if a[i] <= a[j]:
            aux.append(a[i])
            i += 1
        else:
            aux.append(a[j])
            j += 1
    aux += a[i:mid+1] or a[j:r+1]
    a[l:r+1] = aux

自底向上的归并排序。_merge方法都是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge_sort_bu(nums: list):
    sz, n = 1, len(nums)
    while sz <= n:
        for i in range(0, n-sz, sz*2):	# sz 表示子数组大小
            # 把两个大小为sz的数组归并成一个
            _merge(nums, i, i+sz-1, min(i+sz*2-1, n-1))
        sz *= 2
        
def _merge(a, l, mid, r):
    aux = []
    i, j = l, mid + 1
    if a[mid] <= a[mid+1]:
        return
    while i<=mid and j<=r:
        if a[i] <= a[j]:
            aux.append(a[i])
            i += 1
        else:
            aux.append(a[j])
            j += 1
    aux += a[i:mid+1] or a[j:r+1]
    a[l:r+1] = aux

堆排序

将数组构建成堆，从最后一个非叶子节点n//2-1对每个节点进行sink操作，完成heapify。

从堆顶最大的元素，和末尾互换，然后将堆顶元素下沉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def heap_sort(ary):
    n = len(ary)
    # heapify array
    for i in range(n//2-1, -1, -1):
        __sink(ary, n, i)
       
    # move maximum to the end, then sink first
    for j in range(n-1, 0, -1):
        ary[j], ary[0] = ary[0], ary[j]
        __sink(ary, j, 0)
        
def __sink(ary, n, p):
    while p * 2 + 1 < n:
        j = p * 2 + 1        # sink swap with j
        if j + 1 < n and ary[j+1] > ary[j]:	# 找到叶子节点中较大的进行替换。
            j += 1
        if ary[p] >= ary[j]:
            break
        ary[p], ary[j] = ary[j], ary[p]
        p = j