排序演算法的實現和比較
摘 要：
排序是計算機程式設計中的1種重要操作，其功能是對1個數據元素集合或序列重新排列成1個按資料元素某個項值有序的序列。作為排序依據的資料項稱為“排序碼”，也即資料元素的關鍵碼。為了便於查詢，通常希望計算機中的資料表是按關鍵碼有序排列的。如有序表的折半查詢，查詢效率較高。還有，2叉排序樹、B-樹和B+樹的`構造過程就是1個排序過程。
排序世界這個程式分為4個模組.排序模組將多種不同的排序演算法整合在1個介面裡，對各種綜合排序演算法的複雜度進行研究，對比其時間及空間複雜度，發現它們各自的特點；複雜度模組將排序演算法的複雜度整合在1個介面，可以對理論上的複雜度進行研究；模型模組是用動態的方法把排序過程表現出來；綜合模組可以多次排序並比較時間空間複雜度。
關鍵詞：圖靈機；時間複雜度；空間複雜度；排序演算法。
The implementation and comparison of sorting arithmetic
Abstract：
The management, whose function is sorting a data element collection or sequence to another sequence according to some value of a data，is a kind of important operation in computer programming。Data items used as sorting according，which is called "the arrangement code", is also key code of data element. In order to be more convenient for searching, it is usually hoped that the data sheet in the computer is sorted as key code sequence。For example, the half-searching of sequence list is of higher efficiency. And the performing of two forks sequence tree, B- tree and B+ trees is such a process。
The program, sort world, is divided into four modules。Many kinds of different arrangement algorithm are integrated in a surface by sort module。It also does research on the complexity of every kind of synthesis sort algorithm。Respective characteristic can be found from the contrast between time and space complexity。 The model module displays the arrangement process through moving surfaces。Meanwhile, the whole module can be sorted and compared in complexity of time and space many times。
Keywords：Turing machine; Time complexity; Space complexity; Sorting arithmetic.
目錄
前 言 1
1 緒 論 2
1.1課題背景 2
1.2研究意義 2
1.3課題任務 2
1.4開發工具 3
2 排序演算法簡介 4
2.1演算法理論 4
2.2排序理論 5
2.3排序演算法與圖靈機 6
3 需求說明 7
3.1任務概述 7
3.1.1目標 7
3.1.2 約束 7
3.2對效能的規定 7
3.2.1精度 7
3.2.2時間特性要求 7
3.3輸人輸出要求 7
3.4裝置 7
4 概要設計 8
4.1設計思路 8
4.2程式流程圖 8
4.2.1 模組圖 8
4.2.2 Sort模組 9
4.2.3 Airth模組 11
4.2.4 Mode模組 11
4.3排序演算法的具體模型 13
4.3.1 交換排序 13
4.3.2選擇排序 13
4.3.3 直接插入排序 13
4.3.4 2分插入排序 17
4.3.5 Shell排序 17
4.3.6 氣泡排序 17
4.4程式模組主要函式 21
4.4.1 Sort模組函式 21
4.4.2 Airth模組函式 21
4.4.3 Mode模組函式 21
4.5 程式介面 22
4.5.1 主介面 22
4.5.2 複雜度介面 22
4.5.3 排序介面 23
4.5.4 模型介面 24
4.5.5統計介面 24
5 詳細設計 26
5.1 SORT函式模組 26
5.1.1 產生隨機數模組 26
5.1.2 排序模組 26
5.1.3 時間消耗模組 28
5.2 AIRTH模組 28
5.2.1 初始化模組 28
5.2.2 排序模組 28
5.2.3 綜合模組 29
5.3 排序模型模組 29
5.3.1 分配數模組 29
5.3.2 建立數模組 29
5.3.3 集合模組 29
5.3.4 排序模型 29
6 軟體測試及誤差分析 31
6.1 軟體測試專案 31
6.1.1 程式常規測試 31
6.1.2 程式穩定性測試 31
6.1.3 系統的相容性測試 31
6.2 測試結果 31
6.2.1 程式常規測試結果 31
6.2.2 程式穩定性測試結果 31
6.2.3 系統的相容性測試結果 31
6.3 排序演算法誤差分析 32
6.3.1 插入排序演算法誤差分析 32
6.3.2 希爾排序演算法誤差分析 33
6.3.3 氣泡排序演算法誤差分析 33
6.3.4 選擇排序演算法誤差分析 33
6.3.5 堆排序演算法誤差分析 34
6.3.6 快速排序演算法誤差分析 34
6.3.7 歸併排序演算法誤差分析 35
6.3.8 2分插入排序演算法誤差分析 35
6.3.9 交換排序演算法誤差分析 35
7 結束語 36
參考文獻 37
致謝 38
前言
排序是指輸入1個序列，而按1定規律輸出原序列的1個重排。對我們來說，用得最多的是升序排序，即對1個輸入序列<a1、a2、…、an>產生的輸出的序列<a1’、a2’、…、an’>保證a1’< a2’<…< an’。排序演算法有很廣泛的應用，在我們的計算機上幾乎無時無處不存在。因為無處不在，所以我們必須研究排序的演算法。比較它在不同情況下的優劣，對計算機科學的發展有重要作用。
我們要排序的元素可以是1個簡單的整數，1個字元或是1個字串，也可以是1個複雜的資料結構，擁有很多域，但它必須至少有1個key域，我們正是針對這個key域進行排序（本文中主要研究的是長整型的數的排序過程）。除了在隨機排序演算法中，我們都要求不管key域是什麼型別，至少它應該支援比較操作，即能判斷兩個元素key域之間的大小關係。
研究排序主要方法：計算排序演算法的時間空間複雜度(最壞, 平均和最佳)及演算法的穩定性。
本設計主要解決的問題是：比較排序演算法的時間空間複雜度以及排序演算法的動態實現。