用Python实现常见的排序算法

插入排序

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成

• 直接插入排序

边比较边移动元素直到找到待插入元素的位置，最后插入

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定
比较次数：O(n)~O(n^2)

def insert_sort(a):
        n = len(a)
        if n <= 1:
            return

        for i in range(1, n):
            key = a[i]
            j = i -1
            while j > -1 and key < a[j]:
                a[j+1] = a[j]
                j -= 1
            a[j+1] = key

        pass

• 折半插入排序

将比较和移动操作分离开，先折半查找出待插入元素的位置，再统一移动待插入位置之后的所有元素

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定
比较次数：O(nlogn)

def binary_insert_sort(a):
        n = len(a)
        if n <= 1:
            return
        for i in range(1, n):
            key = a[i]
            low, high = 0, i - 1
            while low <= high:
                mid = (low + high) // 2
                if key < a[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            for j in range(i-1, high, -1):
                a[j+1] = a[j]
            a[high+1] = key
        pass

交换排序

根据两个元素关键字的比较结果来交换两个元素在序列中的位置

• 冒泡排序

每趟冒泡都会使一个元素被移动到最终位置

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定

def bubble_sort(a):
        n = len(a)
        if n <= 1:
            return

        flag = False
        for i in range(n-1):
            flag = False
            for j in range(n-1, i, -1):
                if a[j] < a[j-1]:
                    Sort.__swap(a, j-1, j)
                    flag = True
            if flag == False: #如果一趟冒泡过程没有发生一次交换，则列表已经有序
                break
        pass

• 快速排序

基于分治的思想，每次划分都有一个元素被移动到最终位置

时间复杂度：平均O(nlogn) 最坏O(n^2)
空间复杂度：O(1)
不稳定

def quick_sort(a):
        n = len(a)
        if n <= 1:
            return
        Sort.__quickSort(a, 0, n-1, partition = Sort.__partitionRandom)
        pass
def __quickSort(a, low, high, partition):
        if low < high:
            pos = partition(a, low, high)
            Sort.__quickSort(a, low, pos-1, partition)
            Sort.__quickSort(a, pos+1, high, partition)
        pass

def __partition(a, low, high):
        """
        以列表第一个元素为基准划分
        """
        key = a[low]
        while low < high:
            while low < high and a[high] >= key:
                high -= 1
            a[low] = a[high]
            while low < high and a[low] <= key:
                low += 1
            a[high] = a[low]
        a[low] = key
        return low
        pass

def __partitionRandom(a, low, high):
        """
        随机划分
        """
        k = random.randint(low, high)
        if k != low:
            Sort.__swap(a, k, low)
        return Sort.__partition(a, low, high)
        pass

选择排序

选择待排序列中最小或最大的元素作为有序子序列的尾元素，直到待排序列为一个元素

• 简单选择排序

时间复杂度：O(n^2)
空间复杂度：O(1)
不稳定

def select_sort(a):
        n = len(a)
        if n <= 1:
            return

        for i in range(n-1):
            min = i
            for j in range(i, n):
                if a[j] < a[min]:
                    min = j
            if min != i:
                Sort.__swap(a, i, min)
        pass

• 堆排序

以升序排序为例
a.建立大根堆
b.输出堆顶元素，即交换堆底元素与堆顶元素
c.将剩余元素调整为大根堆

时间复杂度：O(nlogn)
空间复杂度：O(1)
不稳定

def heap_sort(a):
        n = len(a)
        if n < 1:
            return

        Sort.__buildMaxHeap(a, n)   #建立大根堆
        for i in range(n-1, 0, -1):
            Sort.__swap(a, 0, i)    #将堆顶元素与堆底元素交换
            Sort.__adjustDown(a, 0, i)  #将数组前i-1个元素调整为大根堆
        pass

def __buildMaxHeap(a, n):
        #自下往上逐渐调整为大根堆
        for i in range(n//2, -1, -1):
            Sort.__adjustDown(a, i, n)
        pass

def __adjustDown(a, k, n):
        #将元素a[k]向下进行调整
        left = 2 * k + 1
        while left < n:
            #父节点与最大的子节点比较，若小于则交换
            max_child = left + 1 if left + 1 < n and a[left+1] > a[left] else left
            if a[k] < a[max_child]:
                Sort.__swap(a, k, max_child)
                k = max_child
                left = 2 * k + 1
            else:
                break
        pass

归并排序

递归形式的归并排序是基于分治的思想

首先将待排序列分成若干子序列
然后递归地对子序列进行排序
最后将已排序子序列合并

• 二路归并排序

时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定

def merge_sort(a):
        n = len(a)
        if n <= 1:
            return
        Sort.__mergeSort(a, 0, n-1)
        pass

def __mergeSort(a, low, high):
        if low < high:
            mid = (low + high) // 2
            Sort.__mergeSort(a, low, mid)
            Sort.__mergeSort(a, mid+1, high)
            Sort.__merge_other(a, low, mid, high)
        pass

def __merge(a, low, mid, high):
        """
        合并两个有序列表
        """
        b = a[:]
        i, j = low, mid+1
        k = low

        while i <= mid and j <= high:
            if b[i] <= b[j]:
                a[k] = b[i]
                i += 1
            else:
                a[k] = b[j]
                j += 1
            k += 1

        while i <= mid:
            a[k] = b[i]
            i += 1
            k += 1

        while j <= high:
            a[k] = b[j]
            j += 1
            k += 1
        pass

def __merge_other(a, low, mid, high):
        """
        合并两个有序序列，另一种写法
        """
        help = []
        i, j = low, mid+1

        while i <= mid and j <= high:
            if a[i] <= a[j]:
                help.append(a[i])
                i += 1
            else:
                help.append(a[j])
                j += 1

        while i <= mid:
            help.append(a[i])
            i += 1
            
        while j <= high:
            help.append(a[j])
            j += 1

        for i in range(low, high+1):
            a[i] = help.pop(0)
            
        pass

完整的代码 github

sort.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
several sorting algorithms
"""

import random

class Sort(object):

    def __init__(self):
        pass

# 插入排序

    def insert_sort(a):
        """
        直接插入排序
        时间复杂度：O(n^2)
        空间复杂度：O(1)
        稳定
        比较次数：O(n)~O(n^2)
        """
        n = len(a)
        if n <= 1:
            return

        for i in range(1, n):
            key = a[i]
            j = i -1
            while j > -1 and key < a[j]:
                a[j+1] = a[j]
                j -= 1
            a[j+1] = key

        pass

    def binary_insert_sort(a):
        """
        折半插入排序
        时间复杂度：O(n^2)
        空间复杂度：O(1)
        稳定
        比较次数：O(nlogn)
        """
        n = len(a)
        if n <= 1:
            return
        for i in range(1, n):
            key = a[i]
            low, high = 0, i - 1
            while low <= high:
                mid = (low + high) // 2
                if key < a[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            for j in range(i-1, high, -1):
                a[j+1] = a[j]
            a[high+1] = key
        pass

# 选择排序

    def select_sort(a):
        """
        简单选择排序
        时间复杂度：O(n^2)
        空间复杂度：O(1)
        不稳定
        """
        n = len(a)
        if n <= 1:
            return

        for i in range(n-1):
            min = i
            for j in range(i, n):
                if a[j] < a[min]:
                    min = j
            if min != i:
                Sort.__swap(a, i, min)
        pass

    def heap_sort(a):
        """
        堆排序
        时间复杂度：O(nlogn)
        空间复杂度：O(1)
        不稳定
        """
        n = len(a)
        if n < 1:
            return

        Sort.__buildMaxHeap(a, n)   #建立大根堆
        for i in range(n-1, 0, -1):
            Sort.__swap(a, 0, i)    #将堆顶元素与堆底元素交换
            Sort.__adjustDown(a, 0, i)  #将数组前i-1个元素调整为大根堆
        pass

    def __buildMaxHeap(a, n):
        #自下往上逐渐调整为大根堆
        for i in range(n//2, -1, -1):
            Sort.__adjustDown(a, i, n)
        pass

    def __adjustDown(a, k, n):
        #将元素a[k]向下进行调整
        left = 2 * k + 1
        while left < n:
            #父节点与最大的子节点比较，若小于则交换
            max_child = left + 1 if left + 1 < n and a[left+1] > a[left] else left
            if a[k] < a[max_child]:
                Sort.__swap(a, k, max_child)
                k = max_child
                left = 2 * k + 1
            else:
                break
        pass

# 归并排序
    
    def merge_sort(a):
        """
        归并排序
        时间复杂度：O(nlogn)
        空间复杂度：O(n)
        稳定
        """
        n = len(a)
        if n <= 1:
            return
        Sort.__mergeSort(a, 0, n-1)
        pass

    def __mergeSort(a, low, high):
        if low < high:
            mid = (low + high) // 2
            Sort.__mergeSort(a, low, mid)
            Sort.__mergeSort(a, mid+1, high)
            Sort.__merge_other(a, low, mid, high)
        pass

    def __merge(a, low, mid, high):
        """
        合并两个有序列表
        """
        b = a[:]
        i, j = low, mid+1
        k = low

        while i <= mid and j <= high:
            if b[i] <= b[j]:
                a[k] = b[i]
                i += 1
            else:
                a[k] = b[j]
                j += 1
            k += 1

        while i <= mid:
            a[k] = b[i]
            i += 1
            k += 1

        while j <= high:
            a[k] = b[j]
            j += 1
            k += 1
        pass

    def __merge_other(a, low, mid, high):
        """
        合并两个有序序列，另一种写法
        """
        help = []
        i, j = low, mid+1

        while i <= mid and j <= high:
            if a[i] <= a[j]:
                help.append(a[i])
                i += 1
            else:
                help.append(a[j])
                j += 1

        while i <= mid:
            help.append(a[i])
            i += 1
            
        while j <= high:
            help.append(a[j])
            j += 1

        for i in range(low, high+1):
            a[i] = help.pop(0)
            
        pass


# 交换排序

    def bubble_sort(a):
        """
        冒泡排序
        时间复杂度：O(n^2)
        空间复杂度：O(1)
        稳定
        """
        n = len(a)
        if n <= 1:
            return

        flag = False
        for i in range(n-1):
            flag = False
            for j in range(n-1, i, -1):
                if a[j] < a[j-1]:
                    Sort.__swap(a, j-1, j)
                    flag = True
            if flag == False: #如果一趟冒泡过程没有发生一次交换，则列表已经有序
                break
        pass

    def quick_sort(a):
        """
        快速排序
        时间复杂度：平均O(nlogn) 最坏O(n^2)
        空间复杂度：O(1)
        不稳定
        """
        n = len(a)
        if n <= 1:
            return

        Sort.__quickSort(a, 0, n-1, partition = Sort.__partitionRandom)
        pass

    def __quickSort(a, low, high, partition):
        if low < high:
            pos = partition(a, low, high)
            Sort.__quickSort(a, low, pos-1, partition)
            Sort.__quickSort(a, pos+1, high, partition)
        pass

    def __partition(a, low, high):
        """
        以列表第一个元素为基准划分
        """
        key = a[low]
        while low < high:
            while low < high and a[high] >= key:
                high -= 1
            a[low] = a[high]
            while low < high and a[low] <= key:
                low += 1
            a[high] = a[low]
        a[low] = key
        return low
        pass

    def __partitionRandom(a, low, high):
        """
        随机划分
        """
        k = random.randint(low, high)
        if k != low:
            Sort.__swap(a, k, low)
        return Sort.__partition(a, low, high)
        pass

    
    def __swap(a, i, j):
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp
            pass

sort_test.py

from sort import Sort
import random
import operator

class SortTest(object):
    """
    the test class of sorting algorithm
    """
    def __init__(self):
        pass

    def gen_random_list(n, min = 0, max = 100):
        """
        generate a random int list
        """
        if min > max or n < 1:
            return []

        random_lsit = []
        for i in range(n):
            random_lsit.append(random.randint(min, max))
        return random_lsit  
        pass

    def test(fun_sort):
        """
        测试排序函数
        成功：true
        失败：false，并打印出错序列
        """
        print(fun_sort.__doc__)
        for i in range(10):
            a = SortTest.gen_random_list(10)
            b = sorted(a)
            c = a[:]
            fun_sort(c) #排序
            # print(a)
            # print(b)
            # print(c)
            if not operator.eq(b, c):
                #打印出错序列
                print(a)
                print(b)
                print(c)
                print('false')
                break
            if i == 9:
                print('true')
        pass

if __name__ == '__main__':
    SortTest.test(fun_sort = Sort.insert_sort)
    SortTest.test(fun_sort = Sort.binary_insert_sort)

    SortTest.test(fun_sort = Sort.select_sort)
    SortTest.test(fun_sort = Sort.heap_sort)

    SortTest.test(fun_sort = Sort.bubble_sort)
    SortTest.test(fun_sort = Sort.quick_sort)

    SortTest.test(fun_sort = Sort.merge_sort)