一個(gè)推薦的博客，里面有詳細(xì)的動(dòng)圖介紹。

排序算法	平均時(shí)間復(fù)雜度	最壞時(shí)間復(fù)雜度	最好時(shí)間復(fù)雜度	空間復(fù)雜度	穩(wěn)定性
快速排序	$O(n\log _2n)$	$O(n^2)$	$O(n\log _2n)$	$O(\log _2n)$	不穩(wěn)定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	穩(wěn)定
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	穩(wěn)定
選擇排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不穩(wěn)定
歸并排序	$O(n\log _2n)$	$O(n\log _2n)$	$O(n\log _2n)$	$O(n)$	穩(wěn)定
希爾排序	$O(n^{1.3})$	$O(n^2)$	$O(n)$	$O(1)$	不穩(wěn)定
堆排序	$O(n\log _2n)$	$O(n\log _2n)$	$O(n\log _2n)$	$O(1)$	不穩(wěn)定

快速排序

思想：
通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分進(jìn)行排序，也就是分治法的思想。
步驟：

從數(shù)列中挑選出一個(gè)元素，作為基準(zhǔn)
重新遍歷數(shù)列，將比基準(zhǔn)小的放在前面，比基準(zhǔn)大的放在后面，相同的可以放在任意一邊
然后對(duì)剛才左邊的和右邊的，分別遞歸上面的操作

不穩(wěn)定，這個(gè)時(shí)候不是雙重循環(huán)，時(shí)間復(fù)雜度O(nlogn).

# ------ coding:utf-8 -----
'''
快速排序
從數(shù)組中選擇一個(gè)數(shù)作為基準(zhǔn)，然后將數(shù)組分成三部分，小于、等于、大于這個(gè)基準(zhǔn)的
然后對(duì)小于、大于基準(zhǔn)的數(shù)組重復(fù)上面的操作
O(nlogn),不穩(wěn)定
'''

def quickSort(nums):
    if len(nums) <= 1:
        return nums
    base = nums[0]
    left = []
    equal = []
    right = []
    for num in nums:
        if num < base:
            left.append(num)
        elif num > base:
            right.append(num)
        else:
            equal.append(num)
    left = quickSort(left)
    right = quickSort(right)
    return left + equal + right

print quickSort([2,3,1,9,0,4,7,8,5])

還有另外一種常見的原地排序的實(shí)現(xiàn)方法：

def quickSort2(nums, left, right):
    if left >= right:
        return
    low = left
    high = right
    base = nums[left]
    while left < right:
        while left < right and nums[right] > base:
            right -= 1
        nums[left] = nums[right]
        while left < right and nums[left] <= base:
            left += 1
        nums[right] = nums[left]
    nums[right] = base
    quickSort2(nums, low, left-1)
    quickSort2(nums, left+1, high)

冒泡排序

思想：
重復(fù)走訪待排的序列，一次比較兩個(gè)元素，比如它們之間的順序錯(cuò)誤了，就把它們進(jìn)行交換。冒泡排序就是把小的元素往前調(diào)，把大的元素往后調(diào)。經(jīng)過一次循環(huán)之后，最大的值將出現(xiàn)在最后。注意的是相鄰的兩個(gè)元素進(jìn)行比較，而且是否需要交換也發(fā)生在這兩個(gè)元素之間。
步驟：

比較相鄰元素，如果第一個(gè)比第二個(gè)大，則交換它們
重復(fù)，直到序列末尾，這個(gè)時(shí)候序列最后的元素就是最大的數(shù)
重復(fù)，直到排序完成

當(dāng)此次循環(huán)中，沒有元素交換的時(shí)候，就停止，代表排序完成

如果兩個(gè)元素相等，是不會(huì)去交換位置的。所以即使通過前面的兩輛交換把兩個(gè)元素放在的一起，也不會(huì)交換他們的位置，所以冒泡排序是穩(wěn)定的。雙重循環(huán)，時(shí)間復(fù)雜度O(n2).

# ------- coding:utf-8 ----
'''
冒泡排序
將大的元素向后調(diào)，則一次機(jī)就將最大的元素放在了最后
時(shí)間復(fù)雜度是O(n^2)，穩(wěn)定
'''

def bubbleSort(nums):
    # 外層循環(huán)控制從頭到尾的次數(shù)
    for i in range(len(nums)-1):
        count = 0   # 記錄一次循環(huán)中，交換元素的次數(shù)，如果為0的話，就停止了
        # 內(nèi)層循環(huán)控制走一次的過程
        for j in range(len(nums)-1-i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                count += 1
        if count == 0:
            break
    return nums

print bubbleSort([1,2,7,8,3,1,9,0,5])

插入排序

思想：
通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中，從后向錢掃描，找到相應(yīng)的位置進(jìn)行并插入。
步驟：

從第一個(gè)元素開始，這個(gè)時(shí)候是一個(gè)有序序列
取出下一個(gè)元素，在已經(jīng)排序的序列中，從后向前掃描，如果有序序列中的當(dāng)前元素大于待排元素，則該元素后移一個(gè)位置，直到找到有序序列中的元素小于等于待排元素，就在該位置進(jìn)行插入（可能找不到這樣的元素，則就在最前的位置插入）
重復(fù)上面的步驟，直到?jīng)]有待排元素

相等元素的前后順序沒有改變，所以插入排序是穩(wěn)定的。雙重循環(huán)，時(shí)間復(fù)雜度O(n2).

# ------ coding:utf-8 -----
'''
插入排序
在已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。最初狀態(tài)只有1個(gè)元素
O(n^2)，穩(wěn)定
'''

def insertSort(nums):
    n = len(nums)
    for i in range(1, n):
        # 將當(dāng)前元素放到前面有序序列的正確位置
        for j in range(i, 0, -1):
            # 如果當(dāng)前當(dāng)前元素比前面的元素小，則往前移動(dòng)，與前面的元素交換
            if nums[j] < nums[j-1]:
                nums[j], nums[j-1] = nums[j-1], nums[j]
            else:
                break
    return nums

print insertSort([1,2,8,9,0,3,6,7,4])

選擇排序

思想：
首先在未排序的序列中找到最小的元素，存放在已排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，然后放到已排序序列末尾。

選擇排序即是給每個(gè)位置選擇待排序元素中當(dāng)前最小的元素。比如給第一個(gè)位置選擇最小的，在剩余元素里面給第二個(gè)位置選擇次小的。以此類推，直到第n-1個(gè)元素，第n個(gè)元素就不用選擇了。
舉例：5 8 5 2 9，首先會(huì)將5與2進(jìn)行交換，那么兩個(gè)5的順序就交換了，所以，選擇排序不穩(wěn)定。
雙重循環(huán)，時(shí)間復(fù)雜度O(n2).

# ------ coding:utf-8 -------
'''
選擇排序
給每個(gè)位置選擇待排序中當(dāng)前最小的元素（交換）
O(n^2)，不穩(wěn)定
'''

def selectSort(nums):
    n = len(nums)
    for i in range(n-1):
        min_dix = i
        for j in range(i+1, n):
            # 尋找最小元素的下標(biāo)
            if nums[min_dix] > nums[j]:
                min_dix = j
        if i != min_dix:
            # 交換當(dāng)前元素和最小元素
            nums[i], nums[min_dix] = nums[min_dix], nums[i]
    return nums

print selectSort([1,2,0,4,9,8,5,4,7])

歸并排序

思想：
采用分治法，將兩個(gè)已經(jīng)有序的序列合并成一個(gè)有序序列，得到完全有序的序列。即先使每個(gè)子序列有序，再使自序列之間有序。若將兩個(gè)有序表合并成一個(gè)有序表，成為2-路歸并。
步驟：

將長(zhǎng)度為 n 的序列分成兩個(gè)長(zhǎng)度為 n/2 的子序列
將這兩個(gè)自序列分別采用歸并排序
將兩個(gè)排序好的自序列合并成一個(gè)最終的排序序列

歸并排序最初的狀態(tài)，可以看成是 n 個(gè)長(zhǎng)度為 1 的有序自序列。
在1個(gè)或2個(gè)元素時(shí)，1個(gè)元素不會(huì)交換，2個(gè)元素如果大小相等的話也不會(huì)交換，所以是穩(wěn)定的
這個(gè)時(shí)候不是雙重循環(huán)，時(shí)間復(fù)雜度O(nlogn)

# -------- coding:utf-8 ------
'''
歸并排序
將兩個(gè)有序序列合并成一個(gè)有序序列，初始狀態(tài)是n個(gè)長(zhǎng)度為1的有序序列
O(nlong), 穩(wěn)定
'''

def mergeSort(nums):
    # 先分解成n個(gè)長(zhǎng)度為1的有序序列
    if len(nums) <= 1:
        return nums
    mid_idx = len(nums) / 2 
    left_nums = mergeSort(nums[:mid_idx])   # 將左邊的部分?jǐn)?shù)據(jù)進(jìn)行排序
    right_nums = mergeSort(nums[mid_idx:])  # 右邊的部分?jǐn)?shù)據(jù)進(jìn)行排序
    return merge(left_nums, right_nums) # 將兩個(gè)有序數(shù)組合并為一個(gè)有序書序

def merge(left_nums, right_nums):
    result = []
    left_idx, right_idx = 0, 0
    # 逐個(gè)比較兩個(gè)數(shù)組最前面的元素
    while left_idx < len(left_nums) and right_idx < len(right_nums):
        if left_nums[left_idx] < right_nums[right_idx]:
            result.append(left_nums[left_idx])
            left_idx += 1
        else:
            result.append(right_nums[right_idx])
            right_idx += 1
    # 將數(shù)組剩下部分加入
    result += left_nums[left_idx:]
    result += right_nums[right_idx:]
    return result

print mergeSort([1,2,0,9,4,5,8,7,3])

希爾排序

思想：
希爾排序又叫做縮小增量排序。是簡(jiǎn)單插入排序的改進(jìn)版，不同之處在于，它會(huì)優(yōu)選比較距離較遠(yuǎn)的元素。
步驟：

選擇增量序列：如 5 3 2 1
按增量序列個(gè)數(shù) k，進(jìn)行 k 趟排序，上面這個(gè)例子就是 4 趟排序
每趟排序，根據(jù)對(duì)應(yīng)的增量，將器分成若干個(gè)長(zhǎng)度為 m 的子序列，然后對(duì)各個(gè)子表進(jìn)行直接插入排序

通常在實(shí)現(xiàn)的過程中，可以不用指定增量序列，初始增量 step = len(nums)/2，后面每一次 step/= 2.

def shellSort(nums):
   n = len(nums)
   step = n / 2
   while step >= 1:
       for i in range(step, n):
           for j in range(i, 0, -step):
               if nums[j] < nums[j - step]:
                   nums[j], nums[j - step] = nums[j - step], nums[j]
               else:
                   break
       step /= 2
   return nums

因?yàn)橄嗤臄?shù)在一次 step 中，可能不在同一個(gè)自序列，因此可能在這個(gè)過程中位置發(fā)生改變，所以希爾排序是不穩(wěn)定的。

堆排序

思想：
堆排序是基于完全二叉樹，以大頂堆為例，大頂堆表示每個(gè)節(jié)點(diǎn)都大于或等于自己的孩子節(jié)點(diǎn)。
步驟：

將長(zhǎng)度為 n 的待排數(shù)組進(jìn)行堆有序化構(gòu)造成一個(gè)大頂堆
- 構(gòu)造的過程是，假如有 n 個(gè)節(jié)點(diǎn)，則逐個(gè)檢查 n/2-1 ~ 0 這些節(jié)點(diǎn)，因?yàn)橹挥羞@些節(jié)點(diǎn)有孩子節(jié)點(diǎn)，如果他們比孩子節(jié)點(diǎn)小，則跟孩子節(jié)點(diǎn)進(jìn)行交換
將大頂堆的根節(jié)點(diǎn)與尾節(jié)點(diǎn)進(jìn)行交換
檢查剩下的 n-1 個(gè)節(jié)點(diǎn)
重復(fù)上面的步驟，直到大頂堆中只有一個(gè)節(jié)點(diǎn)

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

python版本排序算法

python版本排序算法

快速排序

冒泡排序

插入排序

選擇排序

歸并排序

希爾排序

堆排序

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

python版本排序算法

快速排序

冒泡排序

插入排序

選擇排序

歸并排序

希爾排序

堆排序

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av