最近面試中經(jīng)常考察排序算法，所以這里用python實現(xiàn)一下常用的排序算法。

1、直接插入排序

"""插入排序"""

def insertion_sort(a_list):
    for index in range(1,len(a_list)):
        current_value = a_list[index]
        #這里不能減1
        position = index
        # 這里比較的是前一個位置的值
        while position > 0 and a_list[position - 1]> current_value:
            a_list[position] = a_list[position - 1]
            position -= 1
        a_list[position] = current_value


def insertion_sort_binarysearch(a_list):
    for index in range(1,len(a_list)):
        low = 0
        high = index - 1
        current_value = a_list[index]
        position = index
        while low<=high:
            middle = (low+high)//2
            if a_list[middle] > current_value:
                high = middle -1
            else:
                low = middle + 1
        while position > low:
            a_list[position] = a_list[position - 1]
            position -= 1
        a_list[low] = current_value

a_list = [54, 26, 93, 15, 77, 31, 44, 55, 20]
insertion_sort(a_list)
print(a_list)
insertion_sort_binarysearch(a_list)
print(a_list)

2、冒泡排序

def short_bubble_sort(a_list):
    pass_num = len(a_list)-1
    exchanges = True
    while pass_num > 0 and exchanges:
        exchanges = False
        for i in range(pass_num):
            if a_list[i] > a_list[i+1]:
                a_list[i],a_list[i+1] = a_list[i+1],a_list[i]
                exchanges = True

        pass_num -= 1

3、選擇排序

"""選擇排序"""

def selection_sort(a_list):
    for fill_slot in range(len(a_list)-1,0,-1):
        max_index = 0
        for i in range(1,fill_slot+1):
            if a_list[i] > a_list[max_index]:
                max_index=i

        a_list[max_index],a_list[fill_slot] = a_list[fill_slot],a_list[max_index]

if __name__ == '__main__':
    a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    selection_sort(a_list)
    print(a_list)

4、歸并排序

def merge_sort(a_list):
    print("Splitting ", a_list)
    if len(a_list) > 1:
        mid = len(a_list)//2
        left_half = a_list[:mid]
        right_half = a_list[mid:]
        merge_sort(left_half)
        merge_sort(right_half)
        i=0
        j=0
        k=0
        while i<len(left_half) and j<len(right_half):
            if left_half[i] < right_half[j]:
                a_list[k]=left_half[i]
                i+=1
                k+=1
            else:
                a_list[k] = right_half[j]
                j+=1
                k+=1
        while i<len(left_half):
            a_list[k]=left_half[i]
            i+=1
            k+=1
        while j<len(right_half):
            a_list[k] = right_half[j]
            j+=1
            k+=1
    print ('Mergeing',a_list)

5、希爾排序

def shell_sort(a_list):
    #how many sublists, also how many elements in a sublist
    sublist_count = len(a_list) // 2
    while sublist_count > 0:
        for start_position in range(sublist_count):
            gap_insertion_sort(a_list, start_position, sublist_count)
        print("After increments of size", sublist_count, "The list is", a_list)
        sublist_count = sublist_count // 2

def gap_insertion_sort(a_list, start, gap):
    #start+gap is the second element in this sublist
    for i in range(start + gap, len(a_list), gap):
        current_value = a_list[i]
        position = i
        while position >= gap and a_list[position - gap] > current_value:
            a_list[position] = a_list[position - gap] #move backward
            position = position - gap
            a_list[position] = current_value


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20, 88]
shell_sort(a_list)
print(a_list)

6、快速排序

def quick_sort(a_list):
    quick_sort_helper(a_list,0,len(a_list)-1)

def quick_sort_helper(a_list,first,last):
    if first<last:
        split_point = partition(a_list,first,last)
        quick_sort_helper(a_list,0,split_point-1)
        quick_sort_helper(a_list,split_point+1,last)

def partition(a_list,first,last):
    pivot_value = a_list[first]
    left_mark=first+1
    right_mark=last
    done = False
    while not done:
        while left_mark <= right_mark and a_list[left_mark] <= pivot_value:
            left_mark+=1
        while a_list[right_mark] >= pivot_value and right_mark >= left_mark:
            right_mark -= 1
        if right_mark < left_mark:
            done = True
        else:
            a_list[right_mark],a_list[left_mark] = a_list[left_mark],a_list[right_mark]

    a_list[first],a_list[right_mark] = a_list[right_mark],a_list[first]

    return left_mark

a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
my_quick_sort(a_list)
print(a_list)

7、堆排序

def perceDown(a_list,i,N):
    temp = a_list[i]
    while (2*i + 1) < N:
        child = 2 * i + 1
        if child < N - 1 and a_list[child+1] > a_list[child]:
            child = child + 1
        if temp < a_list[child]:
            a_list[i] = a_list[child]
            i = child
        else:
            break
    a_list[i] = temp


def heap_sort(a_list,N):
    for i in range(N//2,-1,-1):
        perceDown(a_list,i,N)
    for i in range(N-1,-1,-1):
        a_list[0],a_list[i] = a_list[i],a_list[0]
        perceDown(a_list,0,i)


if __name__ == '__main__':
    a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    heap_sort(a_list,9)
    print(a_list)