程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C/C++完成八年夜排序算法匯總

C/C++完成八年夜排序算法匯總

編輯：關於C++

C/C++完成八年夜排序算法匯總。本站提示廣大學習愛好者：（C/C++完成八年夜排序算法匯總）文章只能為提供參考，不一定能成為您想要的結果。以下是C/C++完成八年夜排序算法匯總正文

概述排序有外部排序和內部排序，外部排序是數據記載在內存中停止排序，而內部排序是因排序的數據很年夜，一次不克不及包容全體的排序記載，在排序進程中須要拜訪外存。

我們這裡說說八年夜排序就是外部排序。

當n較年夜，則應采取時光龐雜度為O(nlog2n)的排序辦法：疾速排序、堆排序或合並排序。

疾速排序：是今朝基於比擬的外部排序中被以為是最好的辦法，當待排序的症結字是隨機散布時，疾速排序的均勻時光最短；

1. 拔出排序—直接拔出排序(Straight Insertion Sort)

根本思惟:

將一個記載拔出到已排序好的有序表中，從而獲得一個新，記載數增1的有序表。即：先將序列的第1個記載算作是一個有序的子序列，然後從第2個記載逐一停止拔出，直至全部序列有序為止。

要點：設立尖兵，作為暫時存儲和斷定數組界限之用。

直接拔出排序示例：

假如碰見一個和拔出元素相等的，那末拔出元素把想拔出的元素放在相等元素的前面。所以，相等元素的前後次序沒有轉變，從原無序序列出去的次序就是排好序後的次序，所以拔出排序是穩固的。

算法的完成：

//拔出排序
void Insert_Sort(int *list,int count)
{
 int temp;/*此處充任尖兵，不在list數組外面零丁占一個單元*/
 int i,j;
 for(i=1;i<count;i++)
 {
 if(list[i]<list[i-1])
 {
  temp = list[i];
  for(j=i-1;list[j]>temp&&j>=0;j--)
  {
  list[j+1] = list[j];
  }
  list[j+1] = temp;
 }
 }
}

效力：

時光龐雜度：O（n^2）.

其他的拔出排序有二分拔出排序，2-路拔出排序。

2. 拔出排序—希爾排序（Shell`s Sort）

希爾排序是1959 年由D.L.Shell 提出來的，絕對直接排序有較年夜的改良。希爾排序又叫減少增量排序。希爾排序長短穩固排序算法。

根本思惟：

希爾排序是把記載按下標的必定增量分組，對每組應用直接拔出排序算法排序；跟著增量逐步削減，每組包括的症結詞愈來愈多，當增量減至1時，全部文件恰被分紅一組，算法便終止。

操作辦法：

排序進程：先取一個正整數d1<n，把一切序號相隔d1的數組元素放一組，組內停止直接拔出排序；然後取d2<d1，反復上述分組和排序操作；直至di=1，即一切記載放進一個組中排序為止。

算法完成：

我們簡略處置增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n為要排序數的個數

即：先將要排序的一組記載按某個增量d（n/2,n為要排序數的個數）分紅若干組子序列，每組中記載的下標相差d.對每組中全體元素停止直接拔出排序，然後再用一個較小的增量（d/2）對它停止分組，在每組中再停止直接拔出排序。持續赓續減少增量直至為1，最初應用直接拔出排序完成排序。

//shell排序
void Shell_Sort(int *list,int count)
{
 int i,j;
 int temp;
 int increment = count;
 do
 {
 increment = increment/2;
 for(i = increment;i<count;i++)
 {
  if(list[i]<list[i-increment])
  {
  temp = list[i];
  for(j=i-increment;j>=0&&list[j]>temp;j-=increment)
  {
   list[j+increment] = list[j];
  }
  list[j+increment] = temp;
  }
  
 }

 }while(increment>1);
}

希爾排序時效剖析很難，症結碼的比擬次數與記載挪動次數依附於增量因子序列d的拔取，特定情形下可以精確預算出症結碼的比擬次數和記載的挪動次數。今朝還沒有人給出拔取最好的增量因子序列的辦法。增量因子序列可以有各類取法，有取奇數的，也有取質數的，但須要留意：增量因子中除1 外沒有公因子，且最初一個增量因子必需為1。希爾排序辦法是一個不穩固的排序辦法。希爾排序時光龐雜度的下界是n*log2n，是以中等年夜小范圍表示優越。
3. 選擇排序—簡略選擇排序（Simple Selection Sort）

根本思惟：

在要排序的一組數中，選出最小（或許最年夜）的一個數與第1個地位的數交流；然後在剩下的數傍邊再找最小（或許最年夜）的與第2個地位的數交流，順次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最初一個數）比擬為止。

簡略選擇排序的示例：

停止比擬操作的時光龐雜度為O(n^2)，停止挪動操作的時光龐雜度為O(n)。簡略選擇排序是不穩固排序。

操作辦法：

第一趟，從n 個記載中找出症結碼最小的記載與第一個記載交流；

第二趟，從第二個記載開端的n-1 個記載中再選出症結碼最小的記載與第二個記載交流；

以此類推.....

第i 趟，則從第i 個記載開端的n-i+1 個記載當選出症結碼最小的記載與第i 個記載交流，

直到全部序列按症結碼有序。

算法完成：

//選擇排序
void Select_Sort(int *list,int count)
{
 int min,i,j;
 for(i=0;i<count;i++)
 {
 min = i;
 for(j=i+1;j<count;j++)
 {
  if(list[min]>list[j])
  {
  min = j;
  }
 }
 if(min!=i)
 {
  swap(list[i],list[min]);
 }
 }
}

簡略選擇排序的改良——二元選擇排序

簡略選擇排序，每趟輪回只能肯定一個元素排序後的定位。我們可以斟酌改良為每趟輪回肯定兩個元素（以後趟最年夜和最小記載）的地位,從而削減排序所需的輪回次數。改良後對n個數據停止排序，最多只需停止[n/2]趟輪回便可。

4. 選擇排序—堆排序（Heap Sort）

堆排序是一種樹形選擇排序，是對直接選擇排序的有用改良。

根本思惟：

堆的界說以下：具有n個元素的序列（k1,k2,...,kn),當且僅當知足

時稱之為堆。由堆的界說可以看出，堆頂元素（即第一個元素）必為最小項（小頂堆）。
若以一維數組存儲一個堆，則堆對應一棵完整二叉樹，且一切非葉結點的值均不年夜於(或不小於)其後代的值，根結點（堆頂元素）的值是最小(或最年夜)的。如：

（a）年夜頂堆序列：（96，83，27，38，11，09)

(b) 小頂堆序列：（12，36，24，85，47，30，53，91）

初始時把要排序的n個數的序列看做是一棵次序存儲的二叉樹（一維數組存儲二叉樹），調劑它們的存儲序，使之成為一個堆，將堆頂元素輸入，獲得n 個元素中最小(或最年夜)的元素，這時候堆的根節點的數最小（或許最年夜）。然後對後面(n-1)個元素從新調劑使之成為堆，輸入堆頂元素，獲得n 個元素中次小(或次年夜)的元素。依此類推，直到只要兩個節點的堆，並對它們作交流，最初獲得有n個節點的有序序列。稱這個進程為堆排序。

是以，完成堆排序需處理兩個成績：
1. 若何將n 個待排序的數建成堆；
2. 輸入堆頂元素後，如何調劑殘剩n-1 個元素，使其成為一個新堆。

起首評論辯論第二個成績：輸入堆頂元素後，對殘剩n-1元素從新建成堆的調劑進程。
調劑小頂堆的辦法：

1）設有m 個元素的堆，輸入堆頂元素後，剩下m-1 個元素。將堆底元素送入堆頂（（最初一個元素與堆頂停止交流），堆被損壞，其緣由僅是根結點不知足堆的性質。

2）將根結點與左、右子樹中較小元素的停止交流。

3）若與左子樹交流：假如左子樹堆被損壞，即左子樹的根結點不知足堆的性質，則反復辦法（2）.

4）若與右子樹交流，假如右子樹堆被損壞，即右子樹的根結點不知足堆的性質。則反復辦法（2）.

5）持續對不知足堆性質的子樹停止上述交流操作，直到葉子結點，堆被建成。

稱這個自根結點到葉子結點的調劑進程為挑選。如圖：

再評論辯論對n 個元素初始建堆的進程。
建堆辦法：對初始序列建堆的進程，就是一個重復停止挑選的進程。

1）n 個結點的完整二叉樹，則最初一個結點是第個結點的子樹。

2）挑選從第個結點為根的子樹開端，該子樹成為堆。

3）以後向前順次對各結點為根的子樹停止挑選，使之成為堆，直到根結點。

如圖建堆初始進程：無序序列：（49，38，65，97，76，13，27，49）

算法的完成：

從算法描寫來看，堆排序須要兩個進程，一是樹立堆，二是堆頂與堆的最初一個元故舊換地位。所以堆排序有兩個函數構成。一是建堆的滲入滲出函數，二是重復挪用滲入滲出函數完成排序的函數。

//調劑為一個堆
void Heap_Adjust(int *list,int s,int m)
{
 int temp = list[s];
 for(int j=2*s+1;j<=m;j = 2*j+1)
 {
 if(list[j]<list[j+1]&&j<m)
 {
  j++;
 }
 if(temp>list[j])
  break;
 list[s] = list[j];
 s = j;
 }
 list[s] = temp;
}

//堆排序
void Heap_Sort(int *list,int len)
{
 //創立一個年夜頂堆
 for(int s = len/2-1;s>=0;s--)
 {
 Heap_Adjust(list,s,len-1);
 }

 //排序
 for(int i = len-1;i >= 1;i--)
 {
 swap(list[0],list[i]);
 Heap_Adjust(list,0,i-1);
 }
}

剖析:

設樹深度為k，。從根到葉的挑選，元素比擬次數至少2(k-1)次，交流記載至少k 次。所以，在建好堆後，排序進程中的挑選次數不跨越下式：

而建堆時的比擬次數不跨越4n 次，是以堆排序最壞情形下，時光龐雜度也為：O(nlogn )。

因為建初始堆所需的比擬次數較多，所以堆排序不合適於記載數較少的文件。堆排序是當場排序，幫助空間為O(1），它是不穩固的排序辦法。

5. 交流排序—冒泡排序（Bubble Sort）

根本思惟：

在要排序的一組數中，對以後還未排好序的規模內的全體數，自上而下對相鄰的兩個數順次停止比擬和調劑，讓較年夜的數往下沉，較小的往上冒。即：每當兩相鄰的數比擬後發明它們的排序與排序請求相反時，就將它們交換。

冒泡排序的示例：

算法的完成：

//冒泡排序
void Bubble_Sort(int *list,int count)
{
 int flag = true;
 int i = 0,j = 0;
 for(i=0;i<=count&&flag;i++)
 {
  flag = false;
  for(j=count -1;j>=i;j--)
  {
   if(list[j]<list[j-1])
   {
    swap(list[j],list[j-1]);
    flag = true;
   }
  }
 }
}

冒泡排序算法的改良

對冒泡排序罕見的改良辦法是參加一標記性變量exchange，用於標記某一趟排序進程中能否稀有據交流，假如停止某一趟排序時並沒有停止數據交流，則解釋數據曾經按請求分列好，可立刻停止排序，防止不用要的比擬進程。本文再供給以下兩種改良算法：

1．設置一標記性變量pos,用於記載每趟排序中最初一次停止交流的地位。因為pos地位以後的記載均已交流到位,故在停止下一趟排序時只需掃描到pos地位便可。

2．傳統冒泡排序中每趟排序操作只能找到一個最年夜值或最小值,我們斟酌應用在每趟排序中停止正向和反向兩遍冒泡的辦法一次可以獲得兩個終究值(最年夜者和最小者) , 從而使排序趟數簡直削減了一半。

6. 交流排序—疾速排序（Quick Sort）

根本思惟：

一趟疾速排序的算法是：1）設置兩個變量i、j，排序開端的時刻：i=0，j=N-1；2）以第一個數組元素作為症結數據，賦值給key，即key=A[0]；3）從j開端向前搜刮，即由後開端向前搜刮(j--)，找到第一個小於key的值A[j]，將A[j]和A[i]交換；4）從i開端向後搜刮，即由前開端向後搜刮(i++)，找到第一個年夜於key的A[i]，將A[i]和A[j]交換；5）反復第3、4步，直到i=j； (3,4步中，沒找到相符前提的值，即3中A[j]不小於key,4中A[i]不年夜於key的時刻轉變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到相符前提的值，停止交流的時刻i， j指針地位不變。別的，i==j這一進程必定正好是i+或j-完成的時刻，此時令輪回停止）。

（a）一趟排序的進程：

算法的完成：

//疾速排序
int Partition(int *list,int low,int high)
{
 int pivotKey;
 pivotKey = list[low];
 while(low<high)
 {
  while(low<high&&list[high]>=pivotKey)
  {
   high--;
  }
  swap(list[low],list[high]);
  while(low<high&&list[low]<=pivotKey)
  {
   low++;
  }
  swap(list[low],list[high]);
 }
 return low;
}

void Qsort(int *list,int low,int high)
{
 int pivot;
 if(low<high)
 {
  pivot =Partition(list,low,high);
  Qsort(list,low,pivot-1);
  Qsort(list,pivot+1,high);
 }
}

void Quick_Sort(int *list,int count)
{
 Qsort(list,0,count-1);
}

剖析：

疾速排序是平日被以為在同數目級（O(nlog2n)）的排序辦法中均勻機能最好的。但如果初始序列按症結碼有序或根本有序時，快排序反而墮落為冒泡排序。為改良之，平日以“三者取中法”來拔取基准記載，行將排序區間的兩個端點與中點三個記載症結碼居中的調劑為支點記載。疾速排序是一個不穩固的排序辦法。

疾速排序的改良

在本改良算法中,只對長度年夜於k的子序列遞歸挪用疾速排序,讓原序列根本有序，然後再對全部根本有序序列用拔出排序算法排序。理論證實，改良後的算法時光龐雜度有所下降，且當k取值為 8 閣下時,改良算法的機能最好。

7. 合並排序（Merge Sort）

根本思惟：

合並（Merge）排序法是將兩個（或兩個以上）有序表歸並成一個新的有序表，即把待排序序列分為若干個子序列，每一個子序列是有序的。然後再把有序子序列歸並為全體有序序列。

合並排序示例：

歸並辦法：

設r[i…n]由兩個有序子表r[i…m]和r[m+1…n]構成，兩個子表長度分離為n-i +1、n-m。

1.j=m+1；k=i；i=i; //置兩個子表的肇端下標及幫助數組的肇端下標

2.若i>m 或j>n，轉⑷ //個中一個子表已歸並完，比擬拔取停止

3.//拔取r[i]和r[j]較小的存入幫助數組rf
假如r[i]<r[j]，rf[k]=r[i]； i++； k++；轉⑵
不然，rf[k]=r[j]； j++； k++；轉⑵

4.//將還沒有處置完的子表中元素存入rf
假如i<=m，將r[i…m]存入rf[k…n] //前一子表非空
假如j<=n , 將r[j…n] 存入rf[k…n] //後一子表非空

5.歸並停止。

//合並排序
//將兩個有序數組排序
void Merge(int *list,int start,int mid,int end)
{
 const int len1 = mid -start +1;
 const int len2 = end -mid;
 const int len = end - start +1;
 int i,j,k;

 int * front = (int *)malloc(sizeof(int)*len1);
 int * back = (int *)malloc(sizeof(int)*len2);

 for(i=0;i<len1;i++)
  front[i] = list[start+i];
 for(j=0;j<len2;j++)
  back[j] = list[mid+j+1];

 for(i=0,j=0,k=start;i<len1&&j<len2&&k<end;k++)
 {
  if(front[i]<back[j])
  {
   list[k] = front[i];
   i++;
  }else
  {
   list[k] = back[j];
   j++;
  }
 }
 while(i<len1)
 {
  list[k++] = front[i++];
 }
 while(j<len2)
 {
  list[k++] = back[j++];
 }
}  

void MSort(int *list,int start,int end)
{
 if(start<end)
 {
  int mid = (start+end)/2;
  MSort(list,0,mid);
  MSort(list,mid+1,end);
  Merge(list,start,mid,end);
 }

} 

void Merge_Sort(int *list,int count)
{
 MSort(list,0,count-1);
}

8. 桶排序/基數排序(Radix Sort)

說基數排序之前，我們先說桶排序：

根本思惟：是將陣列分到無限數目的桶子裡。每一個桶子再個體排序（有能夠再應用其余排序算法或是以遞回方法持續應用桶排序停止排序）。桶排序是鴿巢排序的一種歸結成果。當要被排序的陣列內的數值是平均分派的時刻，桶排序應用線性時光（Θ（n））。但桶排序其實不是比擬排序，他不遭到 O(n log n) 上限的影響。

簡略來講，就是把數據分組，放在一個個的桶中，然後對每一個桶外面的在停止排序。

例如要對年夜小為[1..1000]規模內的n個整數A[1..n]排序

起首，可以把桶設為年夜小為10的規模，詳細而言，設聚集B[1]存儲[1..10]的整數，聚集B[2]存儲 (10..20]的整數，……聚集B[i]存儲( (i-1)*10, i*10]的整數，i = 1,2,..100。總共有 100個桶。

然後，對A[1..n]從頭至尾掃描一遍，把每一個A[i]放入對應的桶B[j]中。再對這100個桶中每一個桶裡的數字排序，這時候可用冒泡，選擇，甚至快排，普通來講任何排序法都可以。

最初，順次輸入每一個桶外面的數字，且每一個桶中的數字從小到年夜輸入，這樣就獲得一切數字排好序的一個序列了。

假定有n個數字，有m個桶，假如數字是均勻散布的，則每一個桶外面均勻有n/m個數字。假如對每一個桶中的數字采取疾速排序，那末全部算法的龐雜度是 O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

從上式看出，當m接近n的時刻，桶排序龐雜度接近O(n)

固然，以上龐雜度的盤算是基於輸出的n個數字是均勻散布這個假定的。這個假定是很強的，現實運用中後果並沒有這麼好。假如一切的數字都落在統一個桶中，那就退步成普通的排序了。

後面說的幾年夜排序算法，年夜部門時光龐雜度都是O（n2），也有部門排序算法時光龐雜度是O(nlogn)。而桶式排序卻能完成O（n）的時光龐雜度。但桶排序的缺陷是：

1）起首是空間龐雜度比擬高，須要的額定開支年夜。排序有兩個數組的空間開支，一個寄存待排序數組，一個就是所謂的桶，好比待排序值是從0到m-1，那就須要m個桶，這個桶數組就要至多m個空間。

2）其次待排序的元素都要在必定的規模內等等。

桶式排序是一種分派排序。分派排序的特定是不須要停止症結碼的比擬，但條件是要曉得待排序列的一些詳細情形。

分派排序的根本思惟：說白了就是停止屢次的桶式排序。

基數排序進程不必比擬症結字，而是經由過程“分派”和“搜集”進程來完成排序。它們的時光龐雜度可到達線性階：O(n)。

實例:

撲克牌中52 張牌，可按花樣和面值分紅兩個字段，其年夜小關系為：
花樣：梅花< 方塊< 紅心< 黑心
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若對撲克牌按花樣、面值停止升序排序，獲得以下序列：

即兩張牌，若花樣分歧，豈論面值如何，花樣低的那張牌小於花樣高的，只要在同花樣情形下，年夜小關系才由面值的年夜小肯定。這就是多症結碼排序。

為獲得排序成果，我們評論辯論兩種排序辦法。
辦法1：先對花樣排序，將其分為4 個組，即梅花組、方塊組、紅心組、黑心組。再對每一個組分離按面值停止排序，最初，將4 個組銜接起來便可。
辦法2：先按13 個面值給出13 個編號組(2 號，3 號，...，A 號)，將牌按面值順次放入對應的編號組，分紅13 堆。再按花樣給出4 個編號組(梅花、方塊、紅心、黑心)，將2號組中牌掏出分離放入對應花樣組，再將3 號組中牌掏出分離放入對應花樣組，……，如許，4 個花樣組中均按面值有序，然後，將4 個花樣組順次銜接起來便可。

設n 個元素的待排序列包括d 個症結碼{k1，k2，…，kd}，則稱序列對症結碼{k1，k2，…，kd}有序是指：關於序列中任兩個記載r[i]和r[j](1≤i≤j≤n)都知足以下有序關系：

個中k1 稱為最主位症結碼，kd 稱為最次位症結碼。

兩種多症結碼排序辦法：

多症結碼排序依照從最主位症結碼到最次位症結碼或從最次位到最主位症結碼的次序逐次排序，分兩種辦法：

最高位優先(Most Significant Digit first)法，簡稱MSD 法：

1）先按k1 排序分組，將序列分紅若干子序列，統一組序列的記載中，症結碼k1 相等。

2）再對各組按k2 排序分紅子組，以後，對前面的症結碼持續如許的排序分組，直到按最次位症結碼kd 對各子組排序後。

3）再將各組銜接起來，便獲得一個有序序列。撲克牌按花樣、面值排序中引見的辦法一等於MSD 法。

最低位優先(Least Significant Digit first)法，簡稱LSD 法：

1) 先從kd 開端排序，再對kd-1停止排序，順次反復，直到按k1排序分組分紅最小的子序列後。

2) 最初將各個子序列銜接起來，即可獲得一個有序的序列, 撲克牌按花樣、面值排序中引見的辦法二等於LSD 法。

基於LSD辦法的鏈式基數排序的根本思惟

　　“多症結字排序”的思惟完成“單症結字排序”。對數字型或字符型的單症結字，可以看做由多個數位或多個字符組成的多症結字，此時可以采取“分派-搜集”的辦法停止排序，這一進程稱作基數排序法，個中每一個數字或字符能夠的取值個數稱為基數。好比，撲克牌的花樣基數為4，面值基數為13。在整頓撲克牌時，既可以先按花樣整頓，也能夠先按面值整頓。按花樣整頓時，先按紅、黑、方、花的次序分紅4摞（分派），再按此次序再疊放在一路（搜集），然後按面值的次序分紅13摞（分派），再按此次序疊放在一路（搜集），如斯停止二次分派和搜集便可將撲克牌分列有序。

基數排序:

是依照低位先排序，然後搜集；再依照高位排序，然後再搜集；順次類推，直到最高位。有時刻有些屬性是有優先級次序的，先按低優先級排序，再按高優先級排序。最初的順序就是高優先級高的在前，高優先級雷同的低優先級高的在前。基數排序基於分離排序，分離搜集，所所以穩固的。

算法完成：

#define MAX 20
#define BASE 10

void Radix_Sort(int *a, int n) {
 int i, b[MAX], m = a[0], exp = 1;

 for (i = 1; i < n; i++) {
 if (a[i] > m) {
  m = a[i];
 }
 }

 while (m / exp > 0) {
 int bucket[BASE] = { 0 };

 for (i = 0; i < n; i++) {
  bucket[(a[i] / exp) % BASE]++;
 }

 for (i = 1; i < BASE; i++) {
  bucket[i] += bucket[i - 1];
 }

 for (i = n - 1; i >= 0; i--) {
  b[--bucket[(a[i] / exp) % BASE]] = a[i];
 }

 for (i = 0; i < n; i++) {
  a[i] = b[i];
 }

 exp *= BASE;
 }
}

總結

我們比擬時光龐雜度函數的情形：

時光龐雜度函數O(n)的增加情形

所以對n較年夜的排序記載。普通的選擇都是時光龐雜度為O(nlog2n)的排序辦法。

時光龐雜度來講：

(1)平方階(O(n2))排序
各類簡略排序:直接拔出、直接選擇和冒泡排序；
(2)線性對數階(O(nlog2n))排序
疾速排序、堆排序和合並排序；
(3)O(n1+§))排序,§是介於0和1之間的常數。

希爾排序
(4)線性階(O(n))排序
基數排序，另外還有桶、箱排序。

解釋：

當原表有序或根本有序時，直接拔出排序和冒泡排序將年夜年夜削減比擬次數和挪動記載的次數，時光龐雜度可降至O（n）；

而疾速排序則相反，當原表根本有序時，將墮落為冒泡排序，時光龐雜度進步為O（n2）；

原表能否有序，對簡略選擇排序、堆排序、合並排序和基數排序的時光龐雜度影響不年夜。

穩固性：

排序算法的穩固性:若待排序的序列中，存在多個具有雷同症結字的記載，經由排序，這些記載的絕對順序堅持不變，則稱該算法是穩固的；若經排序後，記載的絕對順序產生了轉變，則稱該算法是不穩固的。
穩固性的利益：排序算法假如是穩固的，那末從一個鍵上排序，然後再從另外一個鍵上排序，第一個鍵排序的成果可認為第二個鍵排序所用。基數排序就是如許，先按低位排序，逐次按高位排序，低位雷同的元素其次序再高位也雷同時是不會轉變的。別的，假如排序算法穩固，可以免過剩的比擬；

穩固的排序算法：冒泡排序、拔出排序、合並排序和基數排序

不是穩固的排序算法：選擇排序、疾速排序、希爾排序、堆排序

選擇排序算法原則：

每種排序算法都各有優缺陷。是以，在適用時需依據分歧情形恰當選用，乃至可以將多種辦法聯合起來應用。

選擇排序算法的根據

影響排序的身分有許多，均勻時光龐雜度低的算法其實不必定就是最優的。相反，有時均勻時光龐雜度高的算法能夠更合適某些特別情形。同時，選擇算法時還得斟酌它的可讀性，以利於軟件的保護。普通而言，須要斟酌的身分有以下四點：

1．待排序的記載數量n的年夜小；

2．記載自己數據量的年夜小，也就是記載中除症結字外的其他信息量的年夜小；

3．症結字的構造及其散布情形；

4．對排序穩固性的請求。

設待排序元素的個數為n.

1）當n較年夜，則應采取時光龐雜度為O(nlog2n)的排序辦法：疾速排序、堆排序或合並排序序。