一種冒泡排序的改進算法

廖志文

摘要：傳統的冒泡排序幾乎都是基于基本數據類型，通過比較相鄰的兩個元素的大小，如果發生逆序，則交換兩個元素的值。當待排序元素是構造類型時，通過交換兩個元素的值，時間復雜度必然會增加；另一方面，基本數據類型變量與構造類型變量的賦值方式有很大的區別，因此傳統的冒泡排序算法復用性低。針對傳統冒泡排序的不足，該文提出了一種冒泡排序的改進算法。改進后的冒泡排序對于元素是結構體等構造類型時時間復雜度明顯降低，且函數復用性提高。

關鍵詞：冒泡排序；改進算法；時間復雜度；函數復用性

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2014）18-4258-04

An Improved Algorithm of Bubble Sort

LIAO Zhi-wen

（Computer Science and Technology Department， Zhuhai College of Jilin University， Zhuhai 519041，China）

Abstract： The traditional bubble sort is almost based on basic data types. By comparing the size of two adjacent elements， if the reverse occurs， the values of the two elements are exchanged. When the elements to be sorted are of constructed type， through the exchange value of the two elements， the time complexity surely bounds to increase； On the other hand， because the assigned way of basic data type is different from that of constructed types， therefore， it will lower reusability of the traditional bubble sort algorithm. For the Shortcoming of the traditional bubble sort， this paper presents an improved bubble sort algorithm. The improved bubble sort algorithm significantly reduces the time complexity and improved reusability when the elements are of constructed data types.

Key words： bubble sort；improved algorithm；time complexity；function reusability

一個算法的復雜性的高低體現在運行該算法所需要的時間和空間資源。設計出復雜性盡可能低的算法是在設計算法時追求的一個重要目標[1]。算法是解決問題的一種方法或一個過程。在C語言中，算法都是通過函數實現的。函數是C語言源程序的基本構成模塊，是一段可以重復調用的、功能相對獨立完整的程序段[2]。函數的復用性是判斷一個函數設計優良的重要特征。

冒泡排序（Bubble Sort），是一種計算機科學領域的常用的較簡單的排序算法。如何設計出復雜度盡可能低且函數復用性高的算法是算法效率和通用性的關鍵內容。

1 傳統的冒泡排序

1.1 排序思想

假設數組有n個數組元素，將這n個元素按升序進行排序。從下標為0的元素開始，比較相鄰的兩個元素的大小，如果前面的元素大于后面的元素，在交換這兩個元素的值。……