Python实现排序算法

一、冒泡排序


#1.第一层循环，从后往前遍历
#2.第二层循环，在第一层的基础上，从前往后遍历
#3.相近的元素进行比较，若前面的比后面的数据大，则交换位置
def bubbleSort(tmp_list):
    for i in range(len(tmp_list)-1,0,-1):
        flag = 0
        for j in range(i):
            if tmp_list[j] > tmp_list[j+1]:
                tmp_list[j],tmp_list[j+1] = tmp_list[j+1],tmp_list[j]
                flag = 1
        if 0 == flag:
             break

冒泡排序动图演示

冒泡排序动态图

二、选择排序

#1.第一层循环，从后往前遍历
#2.第二层循环，在一层的基础上，选择当前范围的最大值，放在第一层循环的最大索引处
def selectionSort(tmp_list):
    for i in range(len(tmp_list) - 1, 0, -1):
        index = i
        for j in range(i):
            if tmp_list[j] > tmp_list[index]:
                index = j

        tmp_list[index], tmp_list[i] = tmp_list[i], tmp_list[index]

动态图

三、插入排序

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5

def insertSort(a):
    for i in range(1,len(a,1):
        j = i-1
　　　　 current = a[i]
        while j >=0 and a[j] > current:
　　　　　　a[j+1] = a[j]
　　　　　　j -= 1
　　　　a[j+1] = current

动态图

四、希尔排序

原理:https://zhuanlan.zhihu.com/p/34914588

def shellSort(a):
    step = len(a)/2
    while step > 0:
        for i in range(step,len(a)):
            j = i
            temp = a[j]
            while j-step>= 0 and a[j-step] > temp:
                a[j]=a[j-step]
                j -= step
            a[j] = temp
    step /= 2

参考:https://www.cnblogs.com/wuxinyan/p/8615127.html