冒泡排序（短冒泡排序）

import numpy as np
import time


def bubble_sort(alist):
    for passnum in range(len(alist) - 1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]


# 短冒泡排序，当一次遍历时，已经出现排好序的情况下，不需要再进行下面的遍历
def short_bubble_sort(alist):
    need_exchange = True
    passnum = len(alist) - 1
    while passnum > 0 and need_exchange:
        need_exchange = False
        for i in range(passnum):
            if alist[i] > alist[i + 1]:
                need_exchange = True
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
        passnum -= 1


if __name__ == '__main__':
    alist = np.random.randint(10, size=10)
    print(alist)
    bubble_sort(alist)
    print(alist)

    blist = np.random.randint(10, size=10)
    print(blist)
    short_bubble_sort(blist)
    print(blist)

    start_time = time.time()
    for i in range(10):
        clist = np.random.randint(int(1e4), size=int(1e4))
        bubble_sort(clist)
    print(time.time() - start_time)

    start_time = time.time()
    for i in range(10):
        dlist = np.random.randint(int(1e4), size=int(1e4))
        short_bubble_sort(dlist)
    print(time.time() - start_time)

# [4 8 7 5 9 9 1 1 8 9]
# [1 1 4 5 7 8 8 9 9 9]
# [1 4 0 3 7 7 8 7 2 1]
# [0 1 1 2 3 4 7 7 7 8]
# 166.6802577972412
# 168.61909222602844

选择排序

import numpy as np
import time

def selection_sort(alist,list_size):
    for i in range(list_size-1):
        tmp_min=i
        for j in range(i+1,list_size):
            if alist[j]<alist[tmp_min]:
                tmp_min=j

        alist[i],alist[tmp_min]=alist[tmp_min],alist[i]


if __name__=='__main__':
    alist=np.random.randint(0,10,size=10)
    print('before sort: ',alist)
    list_length=len(alist)
    selection_sort(alist, list_length)
    print('after sort: ',alist)

    blist=np.random.randint(0,10000,size=10000)
    list_length=len(blist)
    start_time=time.time()
    selection_sort(blist, list_length)
    print('elapsed time= ',time.time()-start_time)

# before sort:  [2 8 8 8 1 4 0 4 0 3]
# after sort:  [0 0 1 2 3 4 4 8 8 8]
# elapsed time=  9.69593620300293

插入排序

import numpy as np
import time


def insertion_sort(alist,list_length):
    for i in range(1,list_length):
        for j in range(0,i):
            if alist[j]>alist[i]:
                tmp=alist[i]
                for k in range(i,j,-1):
                    alist[k]=alist[k-1]
                alist[j]=tmp
                break


if __name__ == '__main__':
    alist = np.random.randint(10, size=10)
    print(alist)
    insertion_sort(alist)
    print(alist)

    start_time = time.time()
    for i in range(10):
        clist = np.random.randint(int(1e4), size=int(1e4))
        insertion_sort(clist)
    print(time.time() - start_time)

# [9 8 9 6 7 6 8 7 1 4]
# [1 4 6 6 7 7 8 8 9 9]
# 68.87531685829163

希尔排序

import numpy as np
import time

# This implementation is a copy version of the Java implementation in the Algorithm (4th edition)
# But its performance is very bad. 

# * before sort:  [7 6 6 4 9 8 4 2 0 1]
# * after sort:  [0 1 2 4 4 6 6 7 8 9]
# * elapsed time=  14.546229839324951

def shell_sort_from_java(alist):
    length=len(alist)
    h=1
    while h<length//3:
        h=3*h+1
    while h>=1:
        for i in range(h,length):
            for j in range(i,h-1,-h):
                if alist[j]<alist[j-h]:
                    alist[j],alist[j-h]=alist[j-h],alist[j]
        h=h//3

# before sort:  [0 5 3 6 2 9 4 5 6 7]
# after sort:  [0 2 3 4 5 5 6 6 7 9]
# elapsed time=  0.07308650016784668
def shell_sort(arr):

    # Start with a big gap, then reduce the gap
    n = len(arr)
    gap = n//2

    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped 
    # order keep adding one more element until the entire array
    # is gap sorted
    while gap > 0:

        for i in range(gap,n):

            # add a[i] to the elements that have been gap sorted
            # save a[i] in temp and make a hole at position i
            temp = arr[i]

            # shift earlier gap-sorted elements up until the correct
            # location for a[i] is found
            j = i
            while  j >= gap and arr[j-gap] >temp:
                arr[j] = arr[j-gap]
                j -= gap

            # put temp (the original a[i]) in its correct location
            arr[j] = temp
        gap =gap//2

if __name__ == '__main__':
    alist = np.random.randint(0, 10, size=10)
    print('before sort: ', alist)
    list_length = len(alist)
    shell_sort(alist)
    print('after sort: ', alist)

    blist=np.random.randint(0,10000,size=10000)
    list_length=len(blist)
    start_time=time.time()
    shell_sort(blist)
    print('elapsed time= ',time.time()-start_time)

归并排序

import numpy as np
import time
from copy import deepcopy

def merge_sort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        left_half = deepcopy(alist[:mid])
        right_half = deepcopy(alist[mid:])

        merge_sort(left_half)
        merge_sort(right_half)

        _merge(alist, left_half, right_half)


def _merge(alist, left_half, right_half):
    i, j, k = 0, 0, 0
    #print('merge alist: ', alist)
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            alist[k] = left_half[i]
            i += 1

        else:
            alist[k] = right_half[j]
            j += 1

        k += 1

    while i < len(left_half):
        alist[k] = left_half[i]
        i += 1
        k += 1

    while j < len(right_half):
        alist[k] = right_half[j]
        j += 1
        k += 1


if __name__ == '__main__':
    alist = np.random.randint(0, 10, size=10)
    print('before sort: ', alist)
    list_length = len(alist)
    merge_sort(alist)
    print('after sort: ', alist)

    blist=np.random.randint(0,10000,size=10000)
    list_length=len(blist)
    start_time=time.time()
    merge_sort(blist)
    print('elapsed time= ',time.time()-start_time)

# before sort:  [9 1 7 1 6 6 4 0 6 8]
# after sort:  [0 1 1 4 6 6 6 7 8 9]
# elapsed time=  0.08119559288024902

快速排序

import numpy as np
import time
from copy import deepcopy

def quick_sort(arr,l,r):
    if l >= r: return
    i,j = l,r
    while i < j:
        while i < j and arr[j] >= arr[l]:
            j -= 1
        while i < j and arr[i] <= arr[l]:
            i += 1
        arr[i], arr[j] = arr[j], arr[i]
    arr[l], arr[i] = arr[i], arr[l]

    quick_sort(arr, l, i-1)
    quick_sort(arr, i+1, r)

def quick_sort_implementation_two(array_):
    if len(array_)<2:
        return array_
    else:
        pivot=array_[0]
        less=[i for i in array_[1:] if i<=pivot]
        greater=[i for i in array_[1:] if i>pivot]
        return quicksort(less)+[pivot]+quicksort(greater)

print(quicksort([5,8,2,1,4,2,7]))

if __name__ == '__main__':
    alist = np.random.randint(0, 10, size=10)
    print('before sort: ', alist)
    list_length = len(alist)
    quick_sort(alist)
    print('after sort: ', alist)

    blist=np.random.randint(0,10000,size=10000)
    list_length=len(blist)
    start_time=time.time()
    quick_sort(blist)
    print('elapsed time= ',time.time()-start_time)

# before sort:  [8 0 7 2 6 4 1 2 0 2]
# after sort:  [0 0 1 2 2 2 4 6 7 8]
# elapsed time=  0.08011627197265625