冒泡排序

一匈仗、排序流程

• 1.比較相鄰的元素瓢剿。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)悠轩。
• 2.對每一對相鄰元素做同樣的工作间狂，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)火架，最后的元素應(yīng)該會(huì)是最大的數(shù)鉴象。
• 3.針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)何鸡。
• 4.持續(xù)每次對越來越少的元素重復(fù)上面的步驟纺弊，直到?jīng)]有任何一對數(shù)字需要比較。

def bubble_sort(nums):
    length = len(nums)
    for i in range(length):
        for j in range(1, length - i):
            if nums[j - 1] > nums[j]:
                nums[j], nums[j-1] = nums[j - 1], nums[j]
    return nums

二骡男、選擇排序

def find_smallest(nums):
    smallest = nums[0]
    smallest_index = 0
    for index, num in enumerate(nums):
        if num < smallest:
            smallest = num
            smallest_index = index
    return smallest_index

def select_sort(nums):
    sorted_nums = []
    while len(nums) > 0:
        smallest_index = find_smallest(nums)
        smallest_num = nums.pop(smallest_index)
        sorted_nums.append(smallest_selected)
    return sorted_nums

三淆游、插入排序

• 插入排序是指在待排序的元素中，假設(shè)前面n-1(其中n>=2)個(gè)數(shù)已經(jīng)是排好順序的隔盛，現(xiàn)將第n個(gè)數(shù)插到前面已經(jīng)排好的序列中犹菱，然后找到合適自己的位置，使得插入第n個(gè)數(shù)的這個(gè)序列也是排好順序的吮炕。按照此法對所有元素進(jìn)行插入腊脱，直到整個(gè)序列排為有序的過程，稱為插入排序

def insert_sort(nums):
    for index, num in enumerate(nums):
        pointer = index
        while pointer > 0 and nums[pointer] > num:
            nums[pointer] = nums[pointer - 1]
            pointer -= 1
        nums[pointer] = num
    return nums

四龙亲、希爾排序

• 1.算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組陕凹，每組中記錄的下標(biāo)相差d.對每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對它進(jìn)行鳄炉，在每組中再進(jìn)行排序捆姜。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組迎膜，排序完成。

• 2.一般的初次取序列的一半為增量浆兰，以后每次減半磕仅，直到增量為1。

def shell_sort(nums):
    length = len(nums)
    gap = length // 2
    while gap > 0:
        for i in range(gap, length):
            temp = nums[i]
            j = i
            while j >= gap and num[j - gap] > temp:
                j -= gap
            nums[j] = temp
        gap = gap // 2
    return nums

希爾排序

五簸呈、歸并排序

歸并排序（Merge Sort）是建立在歸并操作上的一種有效榕订，穩(wěn)定的排序算法，該算法是采用分治法的一個(gè)非常典型的應(yīng)用蜕便。將已有序的子序列合并劫恒，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序两嘴。若將兩個(gè)有序表合并成一個(gè)有序表丛楚，稱為二路歸并。

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result  += right
    return result
def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = nums[:mid]
    right = nums[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

六憔辫、快速排序

• 1.首先設(shè)定一個(gè)分界值趣些，通過該分界值將數(shù)組分成左右兩部分。

• 2.將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊贰您，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊坏平。此時(shí)，左邊部分中各元素都小于或等于分界值锦亦，而右邊部分中各元素都大于或等于分界值舶替。

• 3.然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序杠园。對于左側(cè)的數(shù)組數(shù)據(jù)顾瞪，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分返劲，同樣在左邊放置較小值玲昧，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理篮绿。

• 4.重復(fù)上述過程孵延，可以看出，這是一個(gè)遞歸定義亲配。通過遞歸將左側(cè)部分排好序后尘应，再遞歸排好右側(cè)部分的順序。當(dāng)左吼虎、右兩個(gè)部分各數(shù)據(jù)排序完成后犬钢，整個(gè)數(shù)組的排序也就完成了。

def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[0]
    less = [i for i in nums[1:] if i <= pivot]
    greater = [i for i in nums[i:] if i > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

class QuickSort:
    def quick_sort(self, nums):
        self.random_quicksort(nums, left, right)
        return nums
    def random_quicksort(self, nums, left, right):
        if left >= right:
            return
        pivot = self.random_paritition(nums, left, right)
        self.random_quicksort(nums, left, pivot - 1)
        self.random_quicksort(nums, pivot + 1, right)
    def random_partition(self, nums, left, right):
        pivot = random.randint(left, right)
        nums[right], nums[pivot] = nums[pivot], nums[right]
        i = left - 1
        for j in range(left, right):
            if nums[j] < nums[right]:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        i += 1
        nums[i], nums[right] = nums[right], nums[i]
        return i

七思灰、堆排序

heapSort.gif

def build_heap(nums, length, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 1
    
def heap_sort(nums):
    length = len(nums)
    for i in range(length, -1, -1):
        build_heap(nums, length, i)

八玷犹、計(jì)數(shù)排序

def counting_sort(nums, max):  # maxnumber為數(shù)組中的最大值
    length = len(nums)
    if length <= 1:
        return nums
    count_array= [0] * (max + 1)
    for num in nums:
        count_array[num] += 1
    result = []
    for i in range(max + 1):
        for j in range(count_array[i]):
            result.append(i)
    return result

若O(k) > O(nlogn)時(shí)其效率反而不如基于比較的排序