之前面試的時(shí)候經(jīng)常被問(wèn)到排序算法巩那，每次都回答不上來(lái)，排序算法算是對(duì)算法的入門，對(duì)于排序算法想要掌握應(yīng)該先掌握排序算法的思想瞳步，代碼是對(duì)思想的展示闷哆，只有真正理解思想后才能真正掌握排序算法，對(duì)于其他的算法肯定也是先掌握思想
下面主要記錄一下簡(jiǎn)單的排序算法单起，冒泡排序抱怔，選擇排序，插入排序嘀倒，希爾排序屈留，歸并排序，快速排序括儒，都按照升序排列

冒泡排序

冒泡排序是對(duì)相鄰的兩個(gè)進(jìn)行比較绕沈，如果后者比前者小則替換位置，然后繼續(xù)向后比較帮寻，這樣每次都能將最大的數(shù)字排到最后乍狐，每次循環(huán)都能將最大的數(shù)字排到最后,排序過(guò)程嵌套兩個(gè)for循環(huán)，時(shí)間復(fù)雜度最好時(shí)為O(n)最壞時(shí)為O(n2),平均時(shí)間復(fù)雜度為O(n2)

def bubbleSort(arr):
    for i in range(len(arr)):
        for j in range(1,len(arr) - i):
            if arr[j - 1] > arr[j]:
                arr[j],arr[j - 1] = arr[j - 1],arr[j]
    return arr1

選擇排序

選擇排序相當(dāng)于從數(shù)組中選中一個(gè)最小的數(shù)值放在首位,每次循環(huán)的時(shí)候嵌套的循環(huán)默認(rèn)從未排序的位置開(kāi)始,時(shí)間復(fù)雜度最好時(shí)為O(n2)最壞時(shí)為O(n2),平均時(shí)間復(fù)雜度為O(n2)

def slectSort(arr):
    for i in range(len(arr)):
        for j in range(i,len(arr)):
            if arr[i] > arr[j]:
                arr[j],arr[i] = arr[i],arr[j]
    return arr

插入排序

插入排序類似于打撲克牌時(shí)起牌,新起的牌會(huì)插入到前者小于自己后者大于自己的位置,手中已有重復(fù)的話可以插入同等牌的左邊或者右邊(根據(jù)比較時(shí)從左邊比較還是右邊比較),排序時(shí)先看前面是否有已排好的,如果有的話且滿足最后一個(gè)數(shù)字大于新數(shù)字的話則進(jìn)行位置后移,最后將新數(shù)字插入到preIndex的后一位,時(shí)間復(fù)雜度最好時(shí)為O(n)最壞時(shí)為O(n2),平均時(shí)間復(fù)雜度為O(n2)

def insertSort(arr):
    for i in range(len(arr)):
        preIndex = i - 1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex + 1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex + 1] = current
    return arr

希爾排序

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)固逗，效率高浅蚪，即可以達(dá)到線性排序的效率。
但插入排序一般來(lái)說(shuō)是低效的烫罩，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位惜傲。
希爾排序是通過(guò)一個(gè)增量將需要排序的數(shù)分成多組然后對(duì)每一組進(jìn)行插入排序,這個(gè)增量一般開(kāi)始的時(shí)候?yàn)閿?shù)組數(shù)量的一半,最后為1,代碼中3可以替換為其他的值,會(huì)影響到分組的次數(shù),時(shí)間復(fù)雜度最好時(shí)為O(nlogn)最壞時(shí)為O(nlog2n),平均時(shí)間復(fù)雜度為O(nlog2n)

import math
def shellSort(arr)
    gap = 1
    while gap < math.floor(len(arr) / 3):
        gap = gap * 3 + 1
    while gap > 0:
        for g in range(gap):
            for i in range(g, len(arr), gap):
                preIndex = i - gap
                current = arr[i]
                while preIndex >= 0 and arr[preIndex] > current:
                    arr[preIndex + gap] = arr[preIndex]
                    preIndex -= gap
                arr[preIndex + gap] = current
        gap = math.floor(gap / 3)
    return arr

歸并排序

歸并排序相當(dāng)于將數(shù)組先分為兩組,然后將子數(shù)組再分別分為兩組一直到子子...子數(shù)組里面只有一個(gè)或者0個(gè)元素為止,然后合并這些子數(shù)組一直到將數(shù)組最后合并成一個(gè)有序的數(shù)組,時(shí)間復(fù)雜度最好時(shí)為O(nlogn)最壞時(shí)為O(nlogn),平均時(shí)間復(fù)雜度為O(nlogn)

def mergeSort(arr):
    if len(arr) < 2:
        return arr
    midIndex = math.floor(len(arr) / 2)
    left,right = arr[:midIndex],arr[midIndex:]
    return merge(mergeSort(left),mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left > right:
            result.append(right.pop(0))
        else:
            result.append(left.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

快速排序

快速排序命名很粗暴,快速排序是對(duì)冒泡排序的一個(gè)優(yōu)化,首先選擇數(shù)組中的一個(gè)元素,將后面的元素?cái)?shù)值小于這個(gè)數(shù)的放在左邊,大于或者等于的放在右邊,遞歸的對(duì)拆分出的數(shù)組進(jìn)行同樣的排序最后得到一個(gè)有序的數(shù)組,時(shí)間復(fù)雜度最好時(shí)為O(nlogn)最壞時(shí)為O(n2),平均時(shí)間復(fù)雜度為O(nlogn)

def quickSort(arr,left,right):
    if left < right:
        partitionIndex = partition(arr,left,right)
        quickSort(arr,left,partitionIndex - 1)
        quickSort(arr,partitionIndex + 1,right)
    return arr

def partition(arr,left,right):
    provt = left
    index = left + 1
    i = index
    while i <= right:
        if arr[i] < arr[provt]:
            arr[i],arr[index] = arr[index],arr[i]
            index += 1
        i += 1
    arr[index - 1],arr[provt] = arr[provt],arr[index - 1]
    return index - 1