Python 常见排序算法

在平常面试中，一般都会遇见让写排序算法的要求，那么基本也就这三种排序算法，大家可以掌握学会！

冒泡排序

原理： 相邻连个数进行比较，大的下沉，最后一个元素最大

复杂度： 时间复杂度O(n^2)

def dlist_sort(dlist):
    if dlist == []:
        return []
    else:
        dlist_lenght = len(dlist)
        for i  in range (0, dlist_lenght):
            for j in range (i+1, dlist_lenght):
                if dlist[i] > dlist[j]:
                    dlist[i],dlist[j] = dlist[j],dlist[i]
        return dlist


print(dlist_sort([1,5,6,3,2,4,7,8,53]))

快速排序

原理： 递归思想， 列表中取出第一个元素作为标准，比第一个小的放左侧，比第一个大的放右侧

复杂度： 时间复杂度O(nlog2n)

def quick_sort(quick_list):
    if quick_list == []:
        return []
    else:
        first = quick_list[0]
        less = quick_sort([l for l in quick_list[1:] if l < first])
        more = quick_sort([i for i in quick_list[1:] if i >= first])
    return less + [first] + more


print(quick_sort([3,4,2,5,7,9,6,1]))

插入排序

原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序，即只需用到O(1)的额外空间的排序，因而在从后向前扫描过程中，找到排序位置后，需要将已排序元素逐步向后挪位，为最新元素提供插入空间。

复杂度：O(n)

def insertionSort(arr): 
  
    for i in range(1, len(arr)): 
  
        key = arr[i] 
  
        j = i-1
        while j >=0 and key < arr[j] : 
                arr[j+1] = arr[j] 
                j -= 1
        arr[j+1] = key 
  
  
arr = [12, 11, 13, 5, 6] 
insertionSort(arr) 
print ("排序后的数组:") 
for i in range(len(arr)): 
    print ("%d" %arr[i])