探析數(shù)據(jù)結(jié)構(gòu)中內(nèi)部排序算法
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
摘要：排序是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意系列，重新排列成一個按關(guān)鍵字有序的序列。然而，在現(xiàn)實的過程中，由于受到排序算法本身的程序設(shè)計思想、時間復(fù)雜度及穩(wěn)定性等因素的影響，使初學(xué)者在理解上存在很大的問題，本文將具體針對這些問題，提供一些行之有效的解決方法。
論文關(guān)鍵詞：排序,算法,穩(wěn)定性,時間復(fù)雜度
排序依據(jù)所涉及的存儲器不同，分為兩大類：一類是內(nèi)部排序，指的是待排序記錄存放在計算機存儲器中進(jìn)行的排序過程；另一類則是外部排序，指的是待排序記錄數(shù)量很大，以至內(nèi)存不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。本文將主要討論內(nèi)部排序中的直接插入排序、冒泡排序和簡單選擇排序三種排序，并簡要的分析一下快速排序的穩(wěn)定性。
與其它算法相比，排序也是數(shù)據(jù)結(jié)構(gòu)中的一種算法，只不過它所實現(xiàn)的功能比較具體，即實現(xiàn)無序系列的排序。同樣，它也涉及到一種算法的設(shè)計思想、參數(shù)的引用及時間復(fù)雜度等相關(guān)因素；與其它算法有所不同，排序算法涉及到了穩(wěn)定性與不穩(wěn)定性的概念，即關(guān)鍵字相同，排序后它們的順序不變的排序方法稱為穩(wěn)定排序，順序有可能發(fā)生改變的排序方法稱為不穩(wěn)定排序。例如，
，序列中有兩個2，標(biāo)記為
。用一種排序方法進(jìn)行排序，排序后，若
始終在
的前面，則稱穩(wěn)定的排序，若有可能在的后面，則稱不穩(wěn)定的排序。
排序按排序過程中依據(jù)的不同原則對內(nèi)部排序進(jìn)行分類，大致可分為插入排序、交換排序、選擇排序、歸并排序和計數(shù)排序等五類。其實現(xiàn)過程主要進(jìn)行比較和移位兩種操作，即比較關(guān)鍵字的大小，將記錄從一個位置移動到另一個位置，最后得到一個有序序列。學(xué)習(xí)排序的過程，其關(guān)鍵在于理解排序的思想，分析各種排序的特點，從分類到實現(xiàn)，利用流程來實現(xiàn)過程。
1 幾種排序算法的實現(xiàn)過程
內(nèi)部排序按其算法設(shè)計思想的不同，可分為直接插入排序、折半插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序和基數(shù)排序，其中插入的排序有直接插入排序、折半插入排序和希爾排序三種，交換的排序有冒泡排序和快速排序，選擇的排序有簡單選擇排序和堆排序。
從排序的穩(wěn)定性來看，穩(wěn)定的排序有：直接插入排序、折半插入排序、冒泡排序和歸并排序，不穩(wěn)定的排序有：希爾排序、快速排序、簡單選擇排序和堆排序；從排序算法的時間復(fù)雜度來看，直接插入排序、折半插入排序、冒泡排序、簡單選擇排序的時間復(fù)雜度為
，希爾排序的時間復(fù)雜度為
，快速排序、堆排序和歸并排序的時間復(fù)雜度為
。
本文將從排序算法的設(shè)計思想、流程圖、程序設(shè)計、穩(wěn)定性和時間復(fù)雜度等五個方面具體分析，主要介紹直接插入排序、冒泡排序、快速排序、簡單選擇排序和堆排序。此外，在程序的設(shè)計過程中，將引用一個數(shù)組啊a[n]來保存排序序列，排序序列中的所有元素均為整型元素，且均按把序列排成升序的過程來實現(xiàn)。
1.1 直接插入排序
1.1.1 程序設(shè)計思想
直接插入排序可把序列分成已排序列和未排序列兩個部分，最開始時，第一個元素為已排序列，后面的所有元素均為未排序列，在排序的過程中，是把前面的序列看成一個已經(jīng)排好的序列，把后面的元素逐個插入到前面已排好的序列中。例如序列：25，17，8，49，23，15，20。
一次排序，25是一個已排好的序列，17，8，49，23，15，20是未排序列，選擇未排序列中第一個數(shù)17插入到前面的已排序列中，形成序列：17，25，8，49，23，15，20。此時17，25是已排序列，8，49，23，15，20是未排序列。
二次排序，選擇未排序列中第一個數(shù)8插入到前面的已排序列，形成已排序列8，17，25，未排序列49，23，15，20，此時整個序列為8，17，25，49，23，15，20。依次類推，直至整個序列有序。
1.1.2 程序流程圖
圖1 直接插入排序流程圖
1.1.3 程序設(shè)計
InsertSort( int a[n] ) //a[i-1]是已排序列的最后一個元素，a[i]是未
{ int i ,j ,b ; //排序列的第一個元素，實質(zhì)是把a[i]插入到
for( i=1; j
