排序算法的實現(xiàn)和比較VC++
畢業(yè)論文
排序算法的實現(xiàn)和比較
摘 要：
排序是計算機程序設(shè)計中的1種重要操作，其功能是對1個數(shù)據(jù)元素集合或序列重新排列成1個按數(shù)據(jù)元素某個項值有序的序列。作為排序依據(jù)的數(shù)據(jù)項稱為“排序碼”，也即數(shù)據(jù)元素的關(guān)鍵碼。為了便于查找，通常希望計算機中的數(shù)據(jù)表是按關(guān)鍵碼有序排列的。如有序表的折半查找，查找效率較高。還有，2叉排序樹、B-樹和B+樹的`構(gòu)造過程就是1個排序過程。
排序世界這個程序分為4個模塊.排序模塊將多種不同的排序算法集成在1個界面里，對各種綜合排序算法的復(fù)雜度進行研究，對比其時間及空間復(fù)雜度，發(fā)現(xiàn)它們各自的特點；復(fù)雜度模塊將排序算法的復(fù)雜度集成在1個界面，可以對理論上的復(fù)雜度進行研究；模型模塊是用動態(tài)的方法把排序過程表現(xiàn)出來；綜合模塊可以多次排序并比較時間空間復(fù)雜度。
關(guān)鍵詞：圖靈機；時間復(fù)雜度；空間復(fù)雜度；排序算法。
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課題任務(wù) 2
1.4開發(fā)工具 3
2 排序算法簡介 4
2.1算法理論 4
2.2排序理論 5
2.3排序算法與圖靈機 6
3 需求說明 7
3.1任務(wù)概述 7
3.1.1目標 7
3.1.2 約束 7
3.2對性能的規(guī)定 7
3.2.1精度 7
3.2.2時間特性要求 7
3.3輸人輸出要求 7
3.4設(shè)備 7
4 概要設(shè)計 8
4.1設(shè)計思路 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程序模塊主要函數(shù) 21
4.4.1 Sort模塊函數(shù) 21
4.4.2 Airth模塊函數(shù) 21
4.4.3 Mode模塊函數(shù) 21
4.5 程序界面 22
4.5.1 主界面 22
4.5.2 復(fù)雜度界面 22
4.5.3 排序界面 23
4.5.4 模型界面 24
4.5.5統(tǒng)計界面 24
5 詳細設(shè)計 26
5.1 SORT函數(shù)模塊 26
5.1.1 產(chǎn)生隨機數(shù)模塊 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 分配數(shù)模塊 29
5.3.2 創(chuàng)建數(shù)模塊 29
5.3.3 集合模塊 29
5.3.4 排序模型 29
6 軟件測試及誤差分析 31
6.1 軟件測試項目 31
6.1.1 程序常規(guī)測試 31
6.1.2 程序穩(wěn)定性測試 31
6.1.3 系統(tǒng)的兼容性測試 31
6.2 測試結(jié)果 31
6.2.1 程序常規(guī)測試結(jié)果 31
6.2.2 程序穩(wěn)定性測試結(jié)果 31
6.2.3 系統(tǒng)的兼容性測試結(jié)果 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 結(jié)束語 36
參考文獻 37
致謝 38
前言
排序是指輸入1個序列，而按1定規(guī)律輸出原序列的1個重排。對我們來說，用得最多的是升序排序，即對1個輸入序列<a1、a2、…、an>產(chǎn)生的輸出的序列<a1’、a2’、…、an’>保證a1’< a2’<…< an’。排序算法有很廣泛的應(yīng)用，在我們的計算機上幾乎無時無處不存在。因為無處不在，所以我們必須研究排序的算法。比較它在不同情況下的優(yōu)劣，對計算機科學(xué)的發(fā)展有重要作用。
我們要排序的元素可以是1個簡單的整數(shù)，1個字符或是1個字符串，也可以是1個復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，擁有很多域，但它必須至少有1個key域，我們正是針對這個key域進行排序（本文中主要研究的是長整型的數(shù)的排序過程）。除了在隨機排序算法中，我們都要求不管key域是什么類型，至少它應(yīng)該支持比較操作，即能判斷兩個元素key域之間的大小關(guān)系。
研究排序主要方法：計算排序算法的時間空間復(fù)雜度(最壞, 平均和最佳)及算法的穩(wěn)定性。
本設(shè)計主要解決的問題是：比較排序算法的時間空間復(fù)雜度以及排序算法的動態(tài)實現(xiàn)。
【排序算法的實現(xiàn)和比較VC++】相關(guān)文章：
2.常用排序算法之JavaScript實現(xiàn)代碼段