朱瑩瑩

（河南師范大學(xué)，河南 新鄉(xiāng) 453007）

?

計(jì)算機(jī)程序設(shè)計(jì)排序方法研究

朱瑩瑩

（河南師范大學(xué)，河南 新鄉(xiāng) 453007）

摘 要：在計(jì)算機(jī)程序設(shè)計(jì)的算法中，存在多種排序方法。學(xué)習(xí)和研究各種排序方法是計(jì)算機(jī)工作者的重要課題之一。排序作為一種重要的算法，就是將一個(gè)數(shù)據(jù)記錄的隨意排序，重新排成一個(gè)按關(guān)鍵字排序的序列。文章將會介紹計(jì)算機(jī)程序設(shè)計(jì)中幾種常用的排序方法，并對其各種性能進(jìn)行分析。

關(guān)鍵詞：選擇排序；插入排序；合并排序；快速排序；時(shí)間復(fù)雜度

為了查找方便，通常計(jì)算機(jī)中的表是按關(guān)鍵字排列有序的，因?yàn)檫@樣有序的順序表可以采用查找效率較高的查找方法，提高查找的速度。因此，排序是計(jì)算機(jī)程序設(shè)計(jì)中重要的操作。因?yàn)榇判蛴涗浀臄?shù)量往往是不同的，排序時(shí)使用的存儲器不同，可將排序方法分為兩大類，內(nèi)部排序和外部排序。不同排序方法的性能往往存在著很大的差別，有的排序方法是穩(wěn)定的，而有的卻不穩(wěn)定，并且算法復(fù)雜性的高低有很大的差別。不言而喻，因此對任意給定的問題，設(shè)計(jì)出復(fù)雜性盡可能低的算法是設(shè)計(jì)算法時(shí)追求的一個(gè)重要目標(biāo)。另一方面，當(dāng)給定的問題已有多種算法時(shí)，選擇其中復(fù)雜性最低者，是選用算法時(shí)遵循的一個(gè)重要準(zhǔn)則。因此，算法的復(fù)雜性分析對算法設(shè)計(jì)或選用有著重要的指導(dǎo)意義和實(shí)用價(jià)值［1］。本文除了給出了每種排序算法在進(jìn)行排序時(shí)所依據(jù)的原則，還對其進(jìn)行了復(fù)雜度的分析以及優(yōu)缺點(diǎn)的評價(jià)。

1　各種排序方法的分析

1.1 選擇排序

選擇排序（Selection Sort）需要進(jìn)行多趟比較，每一趟在n-i+1（i=1，2，...，n-1）個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。其中，又分為簡單選擇排序，樹形選擇排序，堆排序。

簡單選擇排序，第i趟要通過n-i次關(guān)鍵字之間的比較，從n-i+1個(gè)記錄中選取關(guān)鍵字最小的記錄，并和第i個(gè)記錄進(jìn)行交換。對含有n個(gè)元素的數(shù)組，再進(jìn)行簡單選擇排序，需要進(jìn)行n-1次的選擇操作。通過分析，能夠得出，當(dāng)一個(gè)數(shù)組本來就從小到大有序排列時(shí)，記錄只需移動0次，而如果記錄是逆序排列的話，所需移動的次數(shù)最多為3（n-1）次。而進(jìn)行選擇排序時(shí)，記錄都需要進(jìn)行n（n-1）/2次比較，一般情況下，簡單選擇排序的時(shí)間復(fù)雜度為O（n2）。由上可知，選擇排序關(guān)鍵詞之間的比較操作較多，要想進(jìn)行改進(jìn)，可以減少關(guān)鍵詞之間的比較。

樹形選擇排序（Tree Selection Sort）是對簡單選擇排序一種改進(jìn)的方法。它的思想是n個(gè)關(guān)鍵字先兩兩比較。這樣會得出個(gè)較小的關(guān)鍵字，然后再進(jìn)行兩兩比較，這樣一直重復(fù)進(jìn)行能夠選出最小的關(guān)鍵字。這個(gè)過程通常會用含有n個(gè)節(jié)結(jié)點(diǎn)的完全二叉樹表示。含有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹的深度是，選擇次小關(guān)鍵字需要進(jìn)行次比較，由此可以得出樹形選擇排序的時(shí)間復(fù)雜度。這種方法的缺點(diǎn)是輔助存儲空間較多。另一種選擇排序的方法，堆排序（Heap Sort）可以彌補(bǔ)這種缺點(diǎn)，它只需一個(gè)記錄大小的存儲空間。排序的過程就是將一個(gè)無序的序列建成一個(gè)堆，也稱作“篩選”。堆有“大頂堆”和“小頂堆”，排序過程可以使記錄序列按非遞減或非遞增有序隊(duì)列。堆排序在最壞的情況下，時(shí)間復(fù)雜度為O（nlogn）。單堆排序?qū)較大的文件進(jìn)行排序有效，當(dāng)n較小時(shí)并不適合，并且堆排序是一種不穩(wěn)定的排序方法。

1.2 快速排序

快速排序（Quick Sort）是對起泡排序方法的一種改進(jìn)。它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字少，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序［2］。快速排序是一種不穩(wěn)定的排序方法。

首先介紹一下起泡排序（Bubble Sort），它是一類基于“交換”進(jìn)行排序的方法。以將數(shù)據(jù)從小到大排序?yàn)槔?，其基本思路就是每次將相鄰的兩個(gè)數(shù)進(jìn)行比較，每一次排序可將最大的數(shù)“沉底”。例如，若有6個(gè)數(shù)，8，7，5，2，1，4。經(jīng)過第一趟交換為7，5，2，1，4，8，最大的數(shù)8已經(jīng)“沉底”。每一趟的比較都是使該趟最大的數(shù)“沉底”。如果有n個(gè)數(shù)需要進(jìn)行n-1趟比較，在第j趟中需要進(jìn)行n-j次比較。通過對冒泡排序法的排序過程進(jìn)行分析，冒泡排序在排序過程中只需要一個(gè)輔助單元，其空間復(fù)雜度為O（1）。它的時(shí)間效率與數(shù)據(jù)的n有關(guān)，若數(shù)據(jù)元素的狀態(tài)保持不變，正序冒泡法的比較次數(shù)為n-1，移動次數(shù)為0，逆序冒泡法的比較次數(shù)為n（n-1）/2，移動次數(shù)為3n（n-1）/2［3］。通過分析可知冒泡排序法的平均時(shí)間復(fù)雜度為O（n2）。

快速排序在排序前需要任意選取一個(gè)記錄作為“樞紐”。通常情況下選取第一個(gè)記錄，然后將使所有關(guān)鍵字比它小的記錄都放在它的位置之前，所有關(guān)鍵字比它大的記錄都放在它之后。這樣可以將序列分為兩個(gè)子序列，分界線是“樞紐”所在的位置i。整個(gè)快速排序的過程可以用遞歸算法來實(shí)現(xiàn)，當(dāng)待排序列中只含有一個(gè)記錄時(shí)，則該隊(duì)列一定是有序的。否則，需要再次進(jìn)行快速排序，即對分割的兩個(gè)子序列進(jìn)行排序。例如初始序列為49，38，65，97，76，13，27，49。選擇第一個(gè)關(guān)鍵字為49，經(jīng)過一次快速排序后變?yōu)椋?7，38，13｝49｛76，97，65，49｝，然后再分別對分割的兩個(gè)子序列進(jìn)行排序，直至排序完成。就平均時(shí)間而言，快速排序是目前最好的一種排序方法。當(dāng)初始記錄序列按關(guān)鍵字有序或基本有序時(shí)，快速排序?qū)⑼懟癁槊芭菖判颉?/p>

1.3 插入排序的分析

直接插入排序（Straight Insertion Sort）的基本操作是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的，記錄數(shù)增1的有序表。由于需要查找插入位置，為了避免出界，通常要在首址設(shè)置監(jiān)視哨。插入排序也是分趟操作，在第i趟排序時(shí)，則從i-1往前搜索來查找合適的插入位置，對n個(gè)記錄進(jìn)行排序，整個(gè)排序過程需要進(jìn)行n-1趟插入。直接插入排序是一種最簡單的排序方法。當(dāng)被排列的n個(gè)記錄序列為正序時(shí)，需要的比較次數(shù)最少，僅需n-1次，并且不需要移動記錄。最差的情況下需要移動記錄（n+2）（n-1）/2次，移動次數(shù)為（n+4）（n-1）/2。通常情況下，記錄是雜亂無章地排列著，可以取上述分析的最差和最好情況下的平均值，易得時(shí)間復(fù)雜度為O（n2）。

直接插入排序在記錄n的值不大時(shí)，易于操作，并且很容易實(shí)現(xiàn)，但當(dāng)n很大時(shí)，并不適合使用，由此出現(xiàn)了其他改進(jìn)的排序方法。從減少比較次數(shù)方面考慮，出現(xiàn)了折半查找。2-路插入排序，可以減少排序過程中的記錄的移動次數(shù)，但不能避免移動，且所需的輔助存儲空間增多。表插入排序可以通過改變存儲結(jié)構(gòu)，避免移動。希爾排序（Shell’s Sort）與上面所述的幾種改進(jìn)的插入排序方法相比，在時(shí)間效率上又有較大改進(jìn)。它不是直接對全體記錄進(jìn)行排序，而是將待排記錄分割為若干個(gè)子序列進(jìn)行排序。子序列的構(gòu)成也不是簡單的“逐段分割”，其中的記錄都是相隔一定的“增量”。因此在進(jìn)行一趟插入排序時(shí)，關(guān)鍵字的記錄可以跳躍式的移動。當(dāng)序列已經(jīng)基本有序時(shí)，直至最后才進(jìn)行一次增量為1的插入排序。由于增量序列并且影響著希爾排序的時(shí)間復(fù)雜度，增量序列的選擇是一個(gè)復(fù)雜的問題。但是希爾排序從使待排序列按關(guān)鍵字“基本有序”和使每次排序時(shí)n的取值盡量小兩個(gè)方面，對直接插入排序進(jìn)行了改進(jìn)。

1.4 合并排序

合并排序（Merging Sort）是一種運(yùn)用分治策略的思想的算法，它將n個(gè)待排序的記錄分成大小大致相同的兩個(gè)集合，分別對兩個(gè)子集合進(jìn)行排序，最后將各個(gè)排好序的子集合合并成按要求排序的集合，整個(gè)算法要通過遞歸調(diào)用實(shí)現(xiàn)。具體實(shí)現(xiàn)過程是：將待排元素一分為二，每個(gè)子集繼續(xù)遞歸拆分直到分解到僅一個(gè)元素為止，然后兩合并為一個(gè)有續(xù)集即完成了排序。因此通過合并排序算法進(jìn)行排序，在最壞的情況下時(shí)間復(fù)雜度的計(jì)算：

通過解這個(gè)方程可以得出T（n）=O（nlogn）。與快速排序相比，合并排序最大的特點(diǎn)就是一種穩(wěn)定的排序算法。

2　排序方法的比較與總結(jié)

簡單排序的平均時(shí)間為O（n2），最壞情況下也是O （n2），需要輔助的存儲空間是O（1）?？焖倥判虻钠骄鶗r(shí)間是O（nlogn）。最壞情況是O（n2），輔助存儲空間是O （logn）。合并排序的平均時(shí)間是O（nlogn），最壞情況下是O（nlogn），需要的輔助存儲空間是O（n）。通過分析不難得出，當(dāng)待排序的n的值較大時(shí)，宜采用合并排序的排序算法，所需時(shí)間較省，但是需要的輔助存儲空間較多?？焖倥判蛟谄骄阅苌闲枰臅r(shí)間最少，但是在最壞的情況下需要的時(shí)間較多。當(dāng)待排序的記錄“基本有序”或者n的值不大時(shí)，直接插入排序較簡單，可以認(rèn)為是最佳的排序方法。它經(jīng)常和快速排序，合并排序等其他的排序方法一起配合使用。

3　結(jié)語

通過對幾種排序方法的分析和比較，不難得出每一種排序方法就其全面性能而言，很難判斷出哪一種方法最好。不同的排序方法有不同的適應(yīng)場合，應(yīng)根據(jù)具體地實(shí)際情況選擇合適的排序方法。在一個(gè)程序設(shè)計(jì)中，方法的選擇可以不局限于一種，為了達(dá)到最好的效果，可以多種排序方法配合著使用。在學(xué)習(xí)每一種排序方法的思想與原理時(shí)，深入了解每種算法的精髓，有助于創(chuàng)造出新的合適的算法。

［參考文獻(xiàn)］

［1］王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析［M］.4版北京：電子工業(yè)出版社，2012（2）：15-17.

［2］嚴(yán)蔚敏.吳偉民.數(shù)據(jù)結(jié)構(gòu)，C語言版［M］.北京：清華大學(xué)出版社，2007.

［3］張健.計(jì)算機(jī)程序設(shè)計(jì)中的排序問題探討［J］.計(jì)算機(jī)光盤軟件與應(yīng)用，2014（14）:169-170.

Research of Computer Programming Sorting Methods

Zhu Yingying
（Henan Normal University，Xinxiang 453007，China）

Abstract:In computer programming，algorithms，there are various sorting methods. Learning and research various sorting methods is an important issue for computer workers. As an important sorting algorithm is a data record of arbitrary sorting，re-arranged in a sequence ordered by keywords. In this paper，a computer program will introduce the design of several commonly used sorting method，and to analyze the various properties.

Key words:choose sort；insertion sort；merge sort；quick sort；the time complexity

作者簡介：朱瑩瑩（1995-），女，河南周口；研究方向：計(jì)算機(jī)算法。