反饋

排序

排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。分內部排序和外部排序，若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題為外部排序。內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。^[1]

中文名: 排序
外文名: sequence
性質: 計算機內經常進行的一種操作

排序算法: 快速排序、希爾排序、堆排序等
分類: 穩定排序等
應用學科: 數學計算機

排序概念

將雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程叫做排序。^[2]

排序常見排序算法

快速排序、希爾排序、堆排序、直接選擇排序不是穩定的排序算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸併排序是穩定的排序算法。^[1]

排序分類

◆穩定排序：假設在待排序的文件中，存在兩個或兩個以上的記錄具有相同的關鍵字，在

用某種排序法排序後，若這些相同關鍵字的元素的相對次序仍然不變，則這種排序方法

是穩定的。其中冒泡，插入，基數，歸併屬於穩定排序，選擇，快速，希爾，歸屬於不穩定排序。^[3]

◆就地排序：若排序算法所需的輔助空間並不依賴於問題的規模n，即輔助空間為O（1），

則稱為就地排序。

排序冒泡排序

排序原理

已知一組無序數據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]的值一定是這組數據中最大的。再對a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪後a[1]、a[2]、……a[n]就以升序排列了。降序排列與升序排列相類似，若a[1]小於a[2]則交換兩者的值，否則不變，後面以此類推。總的來講，每一輪排序後最大（或最小）的數將移動到數據序列的最後，理論上總共要進行n(n-1）/2次交換。^[2]

排序優劣

優點：穩定。

缺點：慢，每次只能移動相鄰兩個數據。

排序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]<a[j+1] then

begin

temp:=a[j];

a[j]:=a[j+1];

a[j+1]:=temp

end;

writeln('Array sorted:');

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

writeln;

writeln('End sorted.');

readln;

end.

排序c++程序

對N個數進行從小到大排序：

#include <bits/stdc++.h>
using namespace std;
int a[101];
int main()
{
 int n;
 cin>>n;
 for(int i=1;i<=n;i++)//輸入數據
  cin>>a[i];
 for(int i=1;i<n;i++)
 {
  bool flag=true;
  for(int j=1;j<=n-i;j++)
  {
   if(a[j+1]<a[j])//如果後面的數比前面的數小，則需要交換
   {
    swap(a[j+1],a[j]);//交換相鄰的兩個數
    flag=false;
   }
  }
  if(flag)//如果在這一輪都沒有進行交換，則説明該序列已經有序，不需要進行下一輪
   break;
 }
 for(int i=1;i<=n;i++)//輸出排列後的數據
  cout<<a[i]<<" ";
 cout<<endl;
 return 0;
}

排序c#程序

指定個數排序：

static void Main(string[] args)

{

int[] arr = { 4, 2, 5, 7, 4, 9, 6, 21 };

for (int i = 0; i < arr.Length; i++)

{

for (int j = i + 1; j < arr.Length; j++)

{

int temp = 0;

if (arr[i] > arr[j])

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

foreach (int num in arr)

{

Console.Write(" {0}", num);

}

Console.ReadKey();

}

排序選擇排序

排序原理

每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。^[1]

選擇排序是不穩定的排序方法(很多教科書都説選擇排序是不穩定的，但是，完全可以將其實現成穩定的排序方法)。

n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：

①初始狀態：無序區為R[1..n]，有序區為空。

②第1趟排序

在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

……

③第i趟排序

第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。

排序優劣

優點：移動數據的次數已知（n-1次）。

缺點：比較次數多，不穩定。

排序C++程序

#include<iostream>
#include<time.h>
#include<iomanip>
using namespace std;
const int N=10;
int main()
{
    int a[N],i,j,temp,b;
    srand(time(NULL));
    for(i=0;i<N;i++)
        a[i]=rand()%100;
    for(i=0;i<N;i++)
        cout<<setw(3)<<a[i];
    cout<<endl;
    for(i=0;i<N-1;i++)
    {
        temp=i;
        for(j=i+1;j<N;j++)
        {
            if(a[temp]>a[j])
                temp=j;
        }
        if(i!=temp)
        {
            b=a[temp];
            a[temp]=a[i];
            a[i]=b;}
    }
    for(i=0;i<N;i++)
        cout<<setw(3)<<a[i];
    cout<<endl;
}

排序Java程序

public static void selectSort(int[]a)
{
    int minIndex=0;
    int temp=0;
    if((a==null)||(a.length==0))
        return;
    for(int i=0;i<a.length-1;i++)
    {
        minIndex=i;//無序區的最小數據數組下標
        for(intj=i+1;j<a.length;j++)
        {
            //在無序區中找到最小數據並保存其數組下標
            if(a[j]<a[minIndex])
            {
                minIndex=j;
            }
        }
        if(minIndex!=i)
        {
            //如果不是無序區的最小值位置不是默認的第一個數據，則交換之。
            temp=a[i];
            a[i]=a[minIndex];
            a[minIndex]=temp;
        }
    }
}

排序插入排序

排序原理

插入排序：已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、b[2]、……b[m]，需將二者合併成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大於a[2]，則繼續跳過，直到b[1]小於a數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。^[1] （若無數組a，可將b[1]當作n=1的數組a）

排序優劣

優點：穩定，快。

缺點：比較次數不一定，比較次數越多，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決這個問題。

排序算法複雜度

如果目標是把n個元素的序列升序排列，那麼採用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1）次。平均來説插入排序算法的時間複雜度為O（n^2）。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小為量級小於千，那麼插入排序還是一個不錯的選擇。

排序Java程序

/**
*插入排序
*@paramarr
*@return
*/
private static int[] insertSort(int[]arr){
if(arr == null || arr.length < 2){
    return arr;
}
for(inti=1;i<arr.length;i++){
for(intj=i;j>0;j--){
if(arr[j]<arr[j-1]){
//TODO:
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}else{
break;
}
}
}
return arr;
}

排序C++程序

#include<iterator>
template<typenamebiIter>
voidinsertion_sort(biIterbegin,biIterend)
{
typedeftypenamestd::iterator_traits<biIter>::value_typevalue_type;
biIterbond=begin;
std::advance(bond,1);
for(;bond!=end;std::advance(bond,1)){
value_typekey=*bond;
biIterins=bond;
biIterpre=ins;
std::advance(pre,-1);
while(ins!=begin&&*pre>key){
*ins=*pre;
std::advance(ins,-1);
std::advance(pre,-1);
}
*ins=key;
}
}

排序希爾排序

由希爾在1959年提出，是對直接插入排序的優化，又稱希爾排序(Shell Sort)。^[1]

排序原理

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重複上述操作，直到d=1。

排序Pascal程序

program Shell;

type

arr=array[1..100] of integer;

var

a:arr;

i,j,t,d,n:integer;

bool:boolean;

begin

readln(n);

for i:=1 to n do

read(a[i]);

d:=n;

while d>1 do

begin

d:=d div 2;

for j:=d+1 to n do

begin

t:=a[j];

i:=j-d;

while (i>0) and (a[i]>t) do

begin

a[i+d]:=a[i];

i:=i-d;

end;

a[i+d]:=t;

end;

for i:=1 to n do write(a[i],' ');

end.

排序C程序

int[] a = new int[] { 2, 0, 5, 9, 3, 1, 7 };
            int n = a.Length;
            int k = n / 2;
            while (k > 0)
            {
                for (int i = k; i < n; i++)
                {
                    int t = a[i];
                    int j = i - k;
                    while (j >= 0 && t < a[j])
                    {
                        a[j + k] = a[j];
                        j = j - k;
                    }
                    a[j + k] = t;
                }
                k /= 2;
            }

排序優劣

優點：快，數據移動少。

缺點：不穩定，d的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。

不需要大量的輔助空間，和歸併排序一樣容易實現。希爾排序是基於插入排序的一種算法，在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間複雜度為 O(N*(logN)2)，沒有快速排序算法快 O(N*(logN))，因此中等大小規模表現良好，對規模非常大的數據排序不是最優選擇。但是比O（N2）複雜度的算法快得多。並且希爾排序非常容易實現，算法代碼短而簡單。此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞的情況下執行的效率會非常差。專家門提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快，再改成快速排序這樣更高級的排序算法. 本質上講，希爾排序算法的一種改進，減少了其複製的次數，速度要快很多。原因是，當N值很大時數據項每一趟排序需要的個數很少，但數據項的距離很長。當N值減小時每一趟需要和動的數據增多，此時已經接近於它們排序後的最終位置。正是這兩種情況的結合才使希爾排序效率比插入排序高很多。^[1]

排序快速排序

快速排序是大家已知的常用排序算法中最快的排序方法。^[4]

排序原理

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據a[x]作為基準。比較a[x]與其它數據並排序，使a[x]排在數據的第k位，並且使a[1]~a[k-1]中的每一個數據<a[x]，a[k+1]~a[n]中的每一個數據>a[x]，然後採用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n]兩組數據進行快速排序。

排序優劣

優點：極快，數據移動少。

缺點：不穩定。

排序Pascal程序

program kuaipai;

var

a:array[1..100]of integer;

k,l,n,i:integer;

procedure kp(z,y:integer);

var

i,j,t:integer;

begin

i:=z;

j:=y;

t:=a[i];

repeat

while (a[j]>t)and(j>i) do

begin

inc(k);

dec(j);

end;

if i<j then

begin

a[i]:=a[j];

inc(i);

inc(l);

while (a[i]<t)and(i<j) do

begin

inc(k);

inc(i);

end;

if i<j then begin

a[j]:=a[i];

dec(j);

inc(l);

end;

until i=j;

a[i]:=t;

inc(i);

dec(j);

inc(l);

if z<j then kp(z,j);

if i<y then kp(i,y);

end;

begin

readln(n);

for i:=1 to n do

read(a[i]);

k:=0;

l:=0;

kp(1,n);

for i:=1 to n do

write(a[i],' ');

end.^[5]

排序JAVA程序

//化分區間,找到最後元素的排序位置。並返回分隔的點（即最後一數據排序的位置）。

//劃分的區間是[nBegin, nEnd). pData是保存數據的指針

static int Partition(int[] pData, int nBeging, int nEnd)

{

int i = nBeging - 1; //分隔符號，最後nD保存在這裏

--nEnd;

int nD = pData[nEnd]; //比較的數據。

int nTemp; // 交換用的臨時數據

//遍歷數據比較，找到nD的位置，這裏注意，比較結果是,

//如果i的左邊是小於等於nD的，i的右邊是大於nD的

for (int j = nBeging; j < nEnd; ++j)

{

if (pData[j] <= nD) //如果數據比要比較的小，則在該數據的左邊，與i+1交換

{

++i; //小於nD的數據多一個，所以要加1，i的左邊數據都比nD小

nTemp = pData[i]; //交換數據

pData[i] = pData[j];

pData[j] = nTemp;

}

//最後不要忘了吧nD和i+1交換，因為這裏就是nD的位置咯。

++i;

pData[nEnd] = pData[i];

pData[i] = nD;

return i; //返回nD的位置，就是分割的位置。

}

//排序的遞歸調用。

static int QuickSortRecursion(int[] pData, int nBeging, int nEnd)

{

if (nBeging >= nEnd -1) //如果區域不存在或只有一個數據則不遞歸排序

{

return 1;

}

//這裏因為分割的時候，分割點處的數據就是排序中他的位置。

//也就是説他的左邊的數據都小於等於他，他右邊的數據都大於他。

//所以他不在遞歸調用的數據中。

int i = Partition(pData, nBeging, nEnd); //找到分割點

QuickSortRecursion(pData, nBeging, i); //遞歸左邊的排序

QuickSortRecursion(pData, i + 1, nEnd); //遞歸右邊的排序

return 1;

}

//快速排序

public static int QuickSort(int[] pData, int nLen)

{

//遞歸調用，快速排序。

QuickSortRecursion(pData, 0, nLen);

return 1;

}

排序箱排序

已知一組無序正整數數據a[1]、a[2]、……a[n]，需將其按升序排列。首先定義一個數組x[m],且m>=a[1]、a[2]、……a[n]，接着循環n次，每次x[a]++。^[1]

排序原理

1、箱排序的基本思想

箱排序也稱桶排序(Bucket Sort)，其基本思想是：設置若干個箱子，依次掃描待排序的記錄R[0]，R[1]，…，R[n-1]，把關鍵字等於k的記錄全都裝入到第k個箱子裏(分配)，然後按序號依次將各非空的箱子首尾連接起來(收集)。

【例】要將一副混洗的52張撲克牌按點數A<2<…<J<Q<K排序，需設置13個"箱子"，排序時依次將每張牌按點數放入相應的箱子裏，然後依次將這些箱子首尾相接，就得到了按點數遞增序排列的一副牌。

2、箱排序中，箱子的個數取決於關鍵字的取值範圍。

若R[0..n-1]中關鍵字的取值範圍是0到m-1的整數，則必須設置m個箱子。因此箱排序要求關鍵字的類型是有限類型，否則可能要無限個箱子。

3、箱子的類型應設計成鏈表為宜

一般情況下每個箱子中存放多少個關鍵字相同的記錄是無法預料的，故箱子的類型應設計成鏈表為宜。

4、為保證排序是穩定的，分配過程中裝箱及收集過程中的連接必須按先進先出原則進行。

（1）實現方法一

每個箱子設為一個鏈隊列。當一記錄裝入某箱子時，應做人隊操作將其插入該箱子尾部；而收集過程則是對箱子做出隊操作，依次將出隊的記錄放到輸出序列中。

（2）實現方法二

若輸入的待排序記錄是以鏈表形式給出時，出隊操作可簡化為是將整個箱子鏈表鏈接到輸出鏈表的尾部。這隻需要修改輸出鏈表的尾結點中的指針域，令其指向箱子鏈表的頭，然後修改輸出鏈表的尾指針，令其指向箱子鏈表的尾即可。

5、算法簡析

分配過程的時間是O(n)；收集過程的時間為O(m) （採用鏈表來存儲輸入的待排序記錄）或O(m+n)。因此，箱排序的時間為O(m+n)。若箱子個數m的數量級為O(n)，則箱排序的時間是線性的，即O(n)。箱排序實用價值不大，僅適用於作為基數排序的一箇中間步驟。

排序優劣

優點：快，效率達到O(1)。

缺點：數據範圍必須為正整數並且比較小。

排序歸併排序

排序原理

歸併排序是多次將兩個或兩個以上的有序表合併成一個新的有序表。最簡單的歸併是直接將兩個有序的子表合併成一個有序的表。^[1]

歸併排序是穩定的排序.即相等的元素的順序不會改變。如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括號中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序，這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息儘量按輸入的順序排列時很重要，這也是它比快速排序優勢的地方。

排序Pascal程序

program guibing;

type

arr=array[1..100] of integer;

var

a,b,c:arr;

i:integer;

procedure gb(r:arr;l,m,n:integer;var r2:arr);

var

i,j,k,p:integer;

begin

i:=l;

j:=m+1;

k:=l-1;

while (i<=m)and (j<=n) do

begin

k:=k+1;

if r[i]<=r[j] then

begin

r2[k]:=r[i];

i:=i+1

end

else

begin

r2[k]:=r[j];

j:=j+1

end

end;

if i<=m then

for p:=i to m do

begin

k:=k+1;

r2[k]:=r[p]

end;

if j<=n then

for p:=j to n do

begin

k:=k+1;

r2[k]:=r[p]

end;

procedure gp( var r,r1:arr;s,t:integer);

var

k:integer;

c:arr;

begin

if s=t then r1[s]:=r[s]

else

begin

k:=(s+t) div 2;

gp(r,c,s,k);

gp(r,c,k+1,t);

gb(c,s,k,t,r1)

end;

begin

readln(n);

for i:= 1 to n do

read(a[i]);

gp(a,b,1,n);

for i:=1 to n do

write(b[i],' ');

writeln;

end.

排序樹型排序

排序原理

樹形選擇排序又稱錦標賽排序（Tournament Sort），是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的關鍵字進行兩兩比較，然後在n/2個較小者之間再進行兩兩比較，如此重複，直至選出最小的記錄為止。樹形排序的要素就是讓所有的左子樹都比根及右子樹大。^[1]

排序優劣

優點：效率高。

缺點：不穩定。

排序Pascal程序

program shupai;

type

point=^nod;

nod=record

w:integer;

right,left:point ;

end;

var

a:array[1..100]of integer;

root,first:point;

k:boolean;

i:integer;

procedure hyt(d:integer;var p:point);

begin

if p=nil then

begin

new(p);

with p^ do begin

w:=d;

right:=nil;

left:=nil

end;

if k then

begin

root:=p;

k:=false

end;

end

else

with p^ do

if d>=w then

hyt(d,right)

else

hyt(d,left);

end;

procedure hyt1(p:point);

begin

with p^ do

begin

if left<>nil then

hyt1(left);

write(w,' ');

if right<>nil then hyt1(right);

end;

begin

first:=nil;

k:=true;

readln(n);

for i:=1 to n do

read(a[i]);

for i:=1 to n do

hyt(a[i],first);

hyt1(root);

end.

參考資料

1. 嚴蔚敏，吳偉民．數據結構（C語言版）：清華大學出版社，2011
2. 周純傑，劉正林，何頂新等．標準C語言程序設計及應用：華中科技大學出版社，2005
3. 基於PAR的排序算法自動生成研究．軟件學報[引用日期2017-11-27]
4. Thomas H.Cormen等．算法導論：機械工業出版社，2013
5. 基於快速排序的改進算法．2009國際信息技與應用論壇論文集[引用日期2017-11-27]

排序的概述圖（1張）

詞條統計

瀏覽次數：次
編輯次數：83次歷史版本
最近更新：不会说的段子手（2024-01-26）

排序

目錄

排序概念

排序常見排序算法

排序分類

排序冒泡排序

排序原理

排序優劣

排序Pascal程序

排序c++程序

排序c#程序

排序選擇排序

排序原理

排序優劣

排序C++程序

排序Java程序

排序插入排序

排序原理

排序優劣

排序算法複雜度

排序Java程序

排序C++程序

排序希爾排序

排序原理

排序Pascal程序

排序C程序

排序優劣

排序快速排序

排序原理

排序優劣

排序Pascal程序

排序JAVA程序

排序箱排序

排序原理

排序優劣

排序歸併排序

排序原理

排序Pascal程序

排序樹型排序

排序原理

排序優劣

排序Pascal程序