[科普中國(guó)]-排序

排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。分內(nèi)部排序和外部排序，若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序。反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序。內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過程。1

概念將雜亂無章的數(shù)據(jù)元素，通過一定的方法按關(guān)鍵字順序排列的過程叫做排序。2

常見排序算法快速排序、希爾排序、堆排序、直接選擇排序不是穩(wěn)定的排序算法，而基數(shù)排序、冒泡排序、直接插入排序、折半插入排序、歸并排序是穩(wěn)定的排序算法。1

分類◆穩(wěn)定排序：假設(shè)在待排序的文件中，存在兩個(gè)或兩個(gè)以上的記錄具有相同的關(guān)鍵字，在

用某種排序法排序后，若這些相同關(guān)鍵字的元素的相對(duì)次序仍然不變，則這種排序方法

是穩(wěn)定的。其中冒泡，插入，基數(shù)，歸并屬于穩(wěn)定排序，選擇，快速，希爾，堆屬于不穩(wěn)定排序。3

◆就地排序：若排序算法所需的輔助空間并不依賴于問題的規(guī)模n，即輔助空間為O（1），

則稱為就地排序。

冒泡排序原理已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大于a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大于a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最后比較a[n-1]與a[n]的值。這樣處理一輪后，a[n]的值一定是這組數(shù)據(jù)中最大的。再對(duì)a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對(duì)a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪后a[1]、a[2]、……a[n]就以升序排列了。降序排列與升序排列相類似，若a[1]小于a[2]則交換兩者的值，否則不變，后面以此類推。 總的來講，每一輪排序后最大（或最小）的數(shù)將移動(dòng)到數(shù)據(jù)序列的最后，理論上總共要進(jìn)行n(n-1）/2次交換。2

優(yōu)劣優(yōu)點(diǎn)：穩(wěn)定。

缺點(diǎn)：慢，每次只能移動(dòng)相鄰兩個(gè)數(shù)據(jù)。

Pascal程序program name;

var

a:array[1..N] of 1..MAX;

temp,i,j:integer;

begin

randomize;

for i:=1 to N do a:=1+random(MAX);

writeln('Array before sorted:');

for i:=1 to N do write(a,' ');

writeln;

for i:=N-1 downto 1 do

for j:=1 to i do

if a[j]