sort

sort.md

一、冒泡排序

def bububle_sort(alist):
    """冒泡排序(稳定|n^2m)"""
    n = len(alist)
    for j in range(n-1):
        count = 0
        for i in range(0,n-1-j):
            if alist[i]>alist[i+1]:
                count +=1
                alist[i], alist[i+1] = alist[i+1], alist[i]
        if count==0:
            return

二、选择排序

def select_sort(alist):
    """选择排序(不稳定|n^2)"""
    n = len(alist)
    for j in range(n-1):
        min_index = j
        for i in range(j+1,n):
            if alist[min_index] > alist[i]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]
    

三、插入排序

def insert_sort(alist):
    """插入排序(稳定|n^2)"""
    n = len(alist)
    for j in range(1,n):
        i = j
        while i>0:
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break 

四、希尔排序

def shell_sort(alist):
    """希尔排序(不稳定|n^2)"""
    n = len(alist)
    gap = n//2
    
    while gap>=1:
        for j in range(gap,n):
            i=j
            while i>0:
                if alist[i]<alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i -= gap
                else:
                    break
        gap //=2

五、快速排序

def quick_sort(alist, first, last):
    """快速排序(不稳定|n^2)"""
    if first >= last:
        return
    mid_value = alist[first]
    low = first
    high = last
    while low < high:
        #high左移
        while low <high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]
        #low右移
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] =alist[low]  
    #从循环退出时，low=high
    alist[low] = mid_value
    
    #对low左边的列表执行快速排序
    quick_sort(alist, first, low-1)
    #对low右边的列表执行快速排序
    quick_sort(alist, low+1, last)

六、归并排序

def merge_sort(alist):
    """归并排序(稳定|nlgn)"""
    n = len(alist)
    if n <= 1:
        return alist
    mid = n//2
    
    #left 采用归并排序后形成新的有序列表
    left_li = merge_sort(alist[:mid])
    #right 采用归并排序后形成新的有序列表
    right_li = merge_sort(alist[mid:])
    
    #merge(left, right) 将两个有序的子序列合并为一个新的整体
    left_pointer, right_pointer = 0, 0
    result = []
    
    while left_pointer < len(left_li) and right_pointer<len(right_li):
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
            
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result

sort.py

def bububle_sort(alist):
    n = len(alist)
    for j in range(n-1):
        count = 0
        for i in range(n-1-j):
            if alist[i] > alist[i+1]:
                alist[i+1], alist[i] = alist[i], alist[i+1]
                count += 1
        if count == 0:
            return alist
    return alist

def bububle_sort2(alist):
    n = len(alist)
    for i in range(n-1):
        for j in range(i+1, n):
            if alist[i] > alist[j]:
                alist[i], alist[j] = alist[j], alist[i]
    return alist


def select_sort(alist):
    n = len(alist)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        if min_index != i:
            alist[i], alist[min_index] = alist[min_index], alist[i]
    return alist


def insert_sort(alist):
    n = len(alist)
    for i in range(1, n):
        if alist[i] < alist[i-1]:
            temp = alist[i]
            j = i-1
            while alist[j]>temp and j >=0:
                alist[j+1] = alist[j]
                j -= 1
            alist[j+1] = temp
    return alist


def shell_sort(alist):
    n = len(alist)
    gap = n
    while gap > 1:
        gap = gap // 3 + 1
        for i in range(gap, n):
            if alist[i] < alist[i-gap]:
                temp = alist[i]
                j = i - gap
                while alist[j] > temp and j >= 0:
                    alist[j+gap] = alist[j]
                    j -= gap
                alist[j+gap] = temp
    return alist


def merge_sort(alist):
    n = len(alist)
    if n <= 1:
        return alist
    left = merge_sort(alist[:n//2])
    right = merge_sort(alist[n//2:])
    if left[-1] > right[0]:
        return mergeing(left, right)
    return alist


def mergeing(list1, list2):
    list1_size = len(list1)
    list2_size = len(list2)
    i = j = 0
    li = []
    while i < list1_size and j < list2_size:
        if list1[i] < list2[j]:
            li.append(list1[i])
            i += 1
        else:
            li.append(list2[j])
            j += 1
    if i < list1_size:
        li.extend(list1[i:])
    if j < list2_size:
        li.extend(list2[j:])
    return li


def quick_sort(alist):
    if len(alist) < 2:
        return alist
    pivot_index = 0
    pivot = alist[pivot_index]
    less_part = [i for i in alist[pivot_index+1:] if i <= pivot]
    great_part = [i for i in alist[pivot_index+1:] if i > pivot]
    return quick_sort(less_part) + [pivot] + quick_sort(great_part)


def partition(alist, beg, end):
    pivot_index = beg  # 第一个元素作为主元的位置
    pivot = alist[pivot_index]
    left = pivot_index + 1
    right = end - 1

    while True:
        while left <= right and alist[left] < pivot:
            left += 1
        while right >= left and alist[right] > pivot:
            right -= 1
        if right < left:
            break
        else:
            alist[left], alist[right] = alist[right], alist[left]
    alist[right], alist[pivot_index] = alist[pivot_index], alist[right]
    return right


def quick_sort_inplace(alist, beg, end):
    if beg < end:
        pivot = partition(alist, beg, end)
        quick_sort_inplace(alist, beg, pivot)
        quick_sort_inplace(alist, pivot+1, end)
        
        
def partition2(alist, beg, end):
    pivot_index = beg
    pivot = alist[pivot_index]

    for i in range(beg + 1, end + 1):
        if alist[i] < pivot:
            alist[pivot_index + 1], alist[i] = alist[i], alist[pivot_index + 1]
            pivot_index += 1
    alist[beg], alist[pivot_index] = alist[pivot_index], alist[beg]
    return pivot_index


def quick_sort2(alist: list, beg: int, end: int):
    if beg >= end:
        return
    pivot_index = partition2(alist, beg, end)
    quick_sort2(alist, beg, pivot_index - 1)
    quick_sort2(alist, pivot_index + 1, end)

def test_quick_sort_inplace():
    import random
    seq = list(range(10))
    random.shuffle(seq)
    quick_sort_inplace(seq, 0, len(seq))
    key = lambda x, y : x <= y
    assert all(key(seq[i], elem) for i, elem in enumerate(seq[1:])) is True

sort1.py

#!/usr/bin/env python3


def is_sorted(alist):
    n = len(alist)
    if n == 1 or n == 0:
        return True

    for i in range(1, n):
        if alist[i] < alist[i - 1]:
            return False
    return True


def bubble_sort(alist):
    """冒泡排序"""
    n = len(alist)
    if n == 1 or n == 0:
        return alist

    for i in range(n - 1):
        sorted = True
        for j in range(1, n - i):
            if alist[j] < alist[j - 1]:
                alist[j], alist[j - 1] = alist[j - 1], alist[j]
                sorted = False
        if sorted:
            return alist
    return alist


print("=*" * 9, "冒泡排序", "=*" * 9)
import random

alist = list(range(10))
random.shuffle(alist)
print("排序前", alist)
bubble_sort(alist)
print("排序后", alist, ", is sorted {}".format(is_sorted(alist)))
print("\n" * 3)


def select_sort(alist):
    """选择排序"""
    n = len(alist)
    if n == 1 or n == 0:
        return alist

    for i in range(n - 1):
        min = i
        for j in range(i + 1, n):
            if alist[j] < alist[min]:
                min = j
        if min != i:
            alist[i], alist[min] = alist[min], alist[i]
    return alist


print("=*" * 9, "选择排序", "=*" * 9)
import random

alist = list(range(10))
random.shuffle(alist)
print("排序前", alist)
select_sort(alist)
print("排序后", alist, ", is sorted {}".format(is_sorted(alist)))
print("\n" * 3)


def insert_sort(alist):
    """插入排序"""
    n = len(alist)
    if n == 1 or n == 0:
        return alist

    for i in range(1, n):
        j = i
        while j > 0:
            if alist[j] < alist[j - 1]:
                alist[j], alist[j - 1] = alist[j - 1], alist[j]
                j -= 1
            else:
                break
    return alist


print("=*" * 9, "插入排序", "=*" * 9)
import random

alist = list(range(10))
random.shuffle(alist)
print("排序前", alist)
insert_sort(alist)
print("排序后", alist, ", is sorted {}".format(is_sorted(alist)))
print("\n" * 3)


def shell_sort(alist):
    """希尔排序"""
    n = len(alist)
    if n == 1 or n == 0:
        return alist

    gap = n // 2
    while gap >= 1:
        for i in range(gap, n):
            j = i
            while j > 0:
                if alist[j] < alist[j - gap]:
                    alist[j], alist[j - gap] = alist[j - gap], alist[j]
                    j -= gap
                else:
                    break
        gap //= 2
    return alist


print("=*" * 9, "希尔排序", "=*" * 9)
import random

alist = list(range(10))
random.shuffle(alist)
print("排序前", alist)
shell_sort(alist)
print("排序后", alist, ", is sorted {}".format(is_sorted(alist)))
print("\n" * 3)


def merge_sort1(alist):
    """归并排序, 无辅助函数"""
    n = len(alist)
    if n == 1 or n == 0:
        return alist

    mid = n // 2

    # left 采用归并排序后形成的新的有序列表
    left_li = merge_sort1(alist[:mid])
    # right 采用归并排序后形成的新的有序列表
    right_li = merge_sort1(alist[mid:])

    # merge(left, right)将两个有序子序列合并为一个新的整体
    left_pointer = right_pointer = 0
    result = []

    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
    result.extend(left_li[left_pointer:])
    result.extend(right_li[right_pointer:])
    return result


print("=*" * 9, "归并排序, 无辅助函数", "=*" * 9)
import random

alist = list(range(10))
random.shuffle(alist)
print("排序前", alist)
alist = merge_sort1(alist)
print("排序后", alist, ", is sorted {}".format(is_sorted(alist)))
print("\n" * 3)


def merge_sort2(alist):
    """归并排序，有辅助函数"""
    n = len(alist)
    if n == 1 or n == 0:
        return alist

    mid = n // 2
    left = merge_sort2(alist[:mid])
    right = merge_sort2(alist[mid:])

    return merge(left, right)


def merge(left, right):
    left_pointer = right_pointer = 0
    result = []
    while left_pointer < len(left) and right_pointer < len(right):
        if left[left_pointer] < right[right_pointer]:
            result.append(left[left_pointer])
            left_pointer += 1
        else:
            result.append(right[right_pointer])
            right_pointer += 1
    result.extend(left[left_pointer:])
    result.extend(right[right_pointer:])
    return result


print("=*" * 9, "归并排序, 有辅助函数", "=*" * 9)
import random

alist = list(range(10))
random.shuffle(alist)
print("排序前", alist)
alist = merge_sort2(alist)
print("排序后", alist, ", is sorted {}".format(is_sorted(alist)))
print("\n" * 3)


def quick_sort(alist):
    """快速排序"""
    n = len(alist)
    if n == 1 or n == 0:
        return alist
    perform_quick_sort(alist, 0, n-1)
    return alist


def perform_quick_sort(alist, beg, end):
    if beg >= end:
        return

    pivot = alist[beg]
    low = beg
    high = end

    while high > low:
        while high > low and alist[high] >= pivot:
            high -= 1
        alist[low] = alist[high]
        while high > low and alist[low] < pivot:
            low += 1
        alist[high] = alist[low]
    alist[low] = pivot  # 当循环退出时，low=high
    perform_quick_sort(alist, beg, low-1)
    perform_quick_sort(alist, low+1, end)


print("=*" * 9, "快速排序", "=*" * 9)
import random
alist = list(range(10))
random.shuffle(alist)
print("排序前", alist)
quick_sort(alist)
print("排序后", alist, ", is sorted {}".format(is_sorted(alist)))
print("\n" * 3)