資訊專欄INFORMATION COLUMN
摘要：一前言冒泡排序是一種交換排序。以升序冒泡排序為例，冒泡排序就是要每趟排序過程中通過兩兩比較相鄰元素，將小的數字放到前面，大的數字放在后面。所以，冒泡排序最好時間復雜度為。因此，冒泡排序的平均時間復雜度為。
一、前言
冒泡排序是一種交換排序。 什么是交換排序呢？ 解：兩兩比較待排序的關鍵字，并交換不滿足次序要求的那對數，直到整個表都滿足次序要求為止。
二、算法思想
它重復地走訪要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，故名冒泡排序。
假設有一個大小為 N 的無序序列。以升序冒泡排序為例，冒泡排序就是要每趟排序過程中通過兩兩比較相鄰元素，將小的數字放到前面，大的數字放在后面。
代碼
# -*- coding:utf-8 -*-
def bubbleSort(input_list):
"""
函數說明:冒泡排序（升序）
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、時間復雜度
若文件的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數C和記錄移動次數M均達到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好時間復雜度為O(N)。
但是上述代碼，不能掃描一趟就完成排序，它會進行全掃描。所以一個改進的方法就是，當冒泡中途發現已經為正序了，便無需繼續比對下去。改進方法一會兒介紹。
若初始文件是反序的，需要進行 N -1 趟排序。每趟排序要進行 N - i 次關鍵字的比較(1 ≤ i ≤ N - 1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：
Cmax = N(N-1)/2 = O(N^2)
Mmax = 3N(N-1)/2 = O(N^2)
冒泡排序的最壞時間復雜度為O(N^2)。
因此，冒泡排序的平均時間復雜度為O(N^2)。
總結起來，其實就是一句話：當數據越接近正序時，冒泡排序性能越好。
四、優化
對冒泡排序常見的改進方法是加入標志性變量exchange，用于標志某一趟排序過程中是否有數據交換。
如果進行某一趟排序時并沒有進行數據交換，則說明所有數據已經有序，可立即結束排序，避免不必要的比較過程。
代碼
# -*- coding:utf-8 -*-
def bubbleSort(input_list):
"""
函數說明:冒泡排序（升序）
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)
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43315.html
摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學好前端，先練好內功，...
摘要：經過一次冒泡排序，最終在無序表中找到一個最大值，第一次冒泡結束。也是我們后面要說的冒泡排序的優化。冒泡排序只執行第一層循環，而不會執行第二層循環。因此冒泡排序的時間復雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...
摘要：本文對一些排序算法進行了簡單分析，并給出了的代碼實現。平均時間復雜度不好分析，它是冒泡排序是穩定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復雜度是的排序算法。歸并排序，會將數組從中間分成左右兩部分。 本文對一些排序算法進行了簡單分析，并給出了 javascript 的代碼實現。因為本文包含了大量的排序算法，所以分析不會非常詳細，適合有對排序算法有一定了解的同學。本文內容其實不...
摘要：多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實現細節，更能夠鍛煉我們的思維，提升編程能力。排序算法的穩定性一個穩定的排序，指的是在排序之后，相同元素的前后順序不會被改變，反之就稱為不穩定。 1. 導言 因為這是排序算法系列的第一篇文章，所以多啰嗦幾句。 排序是很常見的算法之一，現在很多編程語言都集成了一些排序算法，比如Java 的Arrays.sort()方法，這種方式讓我們可...
閱讀 2976·2023-04-25 19:45
閱讀 2694·2021-11-19 09:40
閱讀 698·2021-10-14 09:49
閱讀 2694·2021-09-30 09:47
閱讀 2222·2021-09-26 09:55
閱讀 1230·2021-09-22 16:01
閱讀 2814·2019-08-30 14:19
閱讀 710·2019-08-29 16:44
