資訊專欄INFORMATION COLUMN
摘要：一前言冒泡排序是一種交換排序。以升序冒泡排序?yàn)槔?，冒泡排序就是要每趟排序過程中通過兩兩比較相鄰元素，將小的數(shù)字放到前面，大的數(shù)字放在后面。所以，冒泡排序最好時(shí)間復(fù)雜度為。因此，冒泡排序的平均時(shí)間復(fù)雜度為。
一、前言
冒泡排序是一種交換排序。 什么是交換排序呢？ 解：兩兩比較待排序的關(guān)鍵字，并交換不滿足次序要求的那對數(shù)，直到整個(gè)表都滿足次序要求為止。
二、算法思想
它重復(fù)地走訪要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名冒泡排序。
假設(shè)有一個(gè)大小為 N 的無序序列。以升序冒泡排序?yàn)槔?，冒泡排序就是要每趟排序過程中通過兩兩比較相鄰元素，將小的數(shù)字放到前面，大的數(shù)字放在后面。
代碼
# -*- coding:utf-8 -*-
def bubbleSort(input_list):
"""
函數(shù)說明:冒泡排序（升序）
Author:
www.cuijiahua.com
Parameters:
input_list - 待排序列表
Returns:
sorted_list - 升序排序好的列表
"""
if len(input_list) == 0:
return []
sorted_list = input_list
for i in range(len(sorted_list) - 1):
print("第%d趟排序:" % (i + 1))
for j in range(len(sorted_list) - 1):
if sorted_list[j + 1] < sorted_list[j]:
sorted_list[j], sorted_list[j + 1] = sorted_list[j + 1], sorted_list[j]
print(sorted_list)
return sorted_list
if __name__ == "__main__":
input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]
print("排序前:", input_list)
sorted_list = bubbleSort(input_list)
print("排序后:", sorted_list)
三、算法分析
1、冒泡排序算法的性能
2、時(shí)間復(fù)雜度
若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)C和記錄移動(dòng)次數(shù)M均達(dá)到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好時(shí)間復(fù)雜度為O(N)。
但是上述代碼，不能掃描一趟就完成排序，它會(huì)進(jìn)行全掃描。所以一個(gè)改進(jìn)的方法就是，當(dāng)冒泡中途發(fā)現(xiàn)已經(jīng)為正序了，便無需繼續(xù)比對下去。改進(jìn)方法一會(huì)兒介紹。
若初始文件是反序的，需要進(jìn)行 N -1 趟排序。每趟排序要進(jìn)行 N - i 次關(guān)鍵字的比較(1 ≤ i ≤ N - 1)，且每次比較都必須移動(dòng)記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動(dòng)次數(shù)均達(dá)到最大值：
Cmax = N(N-1)/2 = O(N^2)
Mmax = 3N(N-1)/2 = O(N^2)
冒泡排序的最壞時(shí)間復(fù)雜度為O(N^2)。
因此，冒泡排序的平均時(shí)間復(fù)雜度為O(N^2)。
總結(jié)起來，其實(shí)就是一句話：當(dāng)數(shù)據(jù)越接近正序時(shí)，冒泡排序性能越好。
四、優(yōu)化
對冒泡排序常見的改進(jìn)方法是加入標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換。
如果進(jìn)行某一趟排序時(shí)并沒有進(jìn)行數(shù)據(jù)交換，則說明所有數(shù)據(jù)已經(jīng)有序，可立即結(jié)束排序，避免不必要的比較過程。
代碼
# -*- coding:utf-8 -*-
def bubbleSort(input_list):
"""
函數(shù)說明:冒泡排序（升序）
Author:
www.cuijiahua.com
Parameters:
input_list - 待排序列表
Returns:
sorted_list - 升序排序好的列表
"""
if len(input_list) == 0:
return []
sorted_list = input_list
for i in range(len(sorted_list) - 1):
bChanged = False
print("第%d趟排序:" % (i + 1))
for j in range(len(sorted_list) - 1):
if sorted_list[j + 1] < sorted_list[j]:
sorted_list[j], sorted_list[j + 1] = sorted_list[j + 1], sorted_list[j]
bChanged = True
print(sorted_list)
if not bChanged:
break
return sorted_list
if __name__ == "__main__":
input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]
print("排序前:", input_list)
sorted_list = bubbleSort(input_list)
print("排序后:", sorted_list)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/43315.html
摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，...
摘要：經(jīng)過一次冒泡排序，最終在無序表中找到一個(gè)最大值，第一次冒泡結(jié)束。也是我們后面要說的冒泡排序的優(yōu)化。冒泡排序只執(zhí)行第一層循環(huán)，而不會(huì)執(zhí)行第二層循環(huán)。因此冒泡排序的時(shí)間復(fù)雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...
摘要：本文對一些排序算法進(jìn)行了簡單分析，并給出了的代碼實(shí)現(xiàn)。平均時(shí)間復(fù)雜度不好分析，它是冒泡排序是穩(wěn)定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復(fù)雜度是的排序算法。歸并排序，會(huì)將數(shù)組從中間分成左右兩部分。 本文對一些排序算法進(jìn)行了簡單分析，并給出了 javascript 的代碼實(shí)現(xiàn)。因?yàn)楸疚陌舜罅康呐判蛩惴?，所以分析不?huì)非常詳細(xì)，適合有對排序算法有一定了解的同學(xué)。本文內(nèi)容其實(shí)不...
摘要：多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實(shí)現(xiàn)細(xì)節(jié)，更能夠鍛煉我們的思維，提升編程能力。排序算法的穩(wěn)定性一個(gè)穩(wěn)定的排序，指的是在排序之后，相同元素的前后順序不會(huì)被改變，反之就稱為不穩(wěn)定。 1. 導(dǎo)言 因?yàn)檫@是排序算法系列的第一篇文章，所以多啰嗦幾句。 排序是很常見的算法之一，現(xiàn)在很多編程語言都集成了一些排序算法，比如Java 的Arrays.sort()方法，這種方式讓我們可...
閱讀 3000·2023-04-25 19:45
閱讀 2726·2021-11-19 09:40
閱讀 725·2021-10-14 09:49
閱讀 2814·2021-09-30 09:47
閱讀 2295·2021-09-26 09:55
閱讀 1257·2021-09-22 16:01
閱讀 2834·2019-08-30 14:19
閱讀 730·2019-08-29 16:44
