自然排序演算法

① 用「自然排序」演算法對數組排序

natsort
(PHP 4, PHP 5, PHP 7)
natsort — 用「自然排序」演算法對數組排序
說明
natsort ( array &$array ) : bool
本函數實現了一個和人們通常對字母數字字元串進行排序的方法一樣的排序演算法並保持原有鍵／值的關聯，這被稱為「自然排序」。本演算法和通常的計算機字元串排序演算法（用於 sort()）的區別見下面示例。
注意:
如果兩個成員完全相同，那麼它們在排序數組中的相對順序是未定義的。
參數
array
輸入的 array。
返回值
成功時返回 true， 或者在失敗時返回 false。
更新日誌
版本 說明
5.2.10 用零填充的數字字元串 (例如 '00005')現在本質上會忽略掉填充的前道零。
範例
示例 #1 natsort() 基本用法的操作示例

② [求助] 自然合並排序的演算法

#include "stdio.h" //輸入輸出的庫函數
#include "stdlib.h" //自然生成數據的庫函數
int n; //全局變數，數組的長度
//函數的定義
void zgb(int *p); //自然分組的規劃
void zgb1(int x,int y,int *q,int *p,int m); //遞歸實現的分治策略
void zgb2(int x,int y,int z,int *p); //排序函數
int main() //主函數
{
int i,m;
char ch=13; //變數的定義
while(1) //主菜單選擇的循環
{
if(ch==13); //判斷控制換行
system("cls"); //清屏
printf("------------請選擇：--------------\n1、運行程序。\n0、退出程序。\n"); //主菜單
scanf("%d",&m); //接受菜單選擇值
system("cls"); //清屏
if(!m) //判斷程序是否執行。
exit(0); //如果m的值非1，則執行退出
printf("請輸入數列的長度n。\n"); //提示語句
scanf("%d",&n); //從鍵盤輸入一個值給n，規定數組的長度
int *a=new int[n]; //定義原數據數組
printf("隨機數列如下：\n");
for(i=0; i<n; i++)
printf("%4d",a[i]=rand()%100); //動態生成數組的數據
printf("\n");
zgb(a); //調用自然分組的函數
printf("自然歸並排序的結果如下：\n");
for(i=0; i<n; i++)
printf("%4d",a[i]); //輸入最終排序號的結果數組
printf("\n");
scanf("%c%c",&ch,&ch); //接受最終的回車符，進入主菜單的下次循環
}
return 0;
}
void zgb(int *p) //自然分組函數
{
int i,m;
int *b=new int[n];//定義保存自然分組的起始下標值的數組
m=0;
b[0]=0;
for(i=1; i<n-1; i++)
if(p[i]>p[i+1]) //判斷取得起始下標的值
b[m+=1]=i+1;
printf("每次排序前的分段下標如下：\n");
while(1) //進入分治策略的循環
{
for(i=0; i<=m; i++)
printf("%d\t",b[i]); //輸出每次進入排序前的自然分組的起始下標值
printf("\n");
int k=0;
zgb1(0,m,b,p,m); //調用遞歸分治策略的函數
for(i=0; i<=m; i++)
{
if(b[i]!=-1&&b[k]==-1)
{
b[k]=b[i];
b[i]=-1; //合並後的起始下標的位子去除
}
if(b[k]!=-1)
k++;
}
m=k-1;
if(m<=0) //控制循環的退出
{
printf("0\n");
break;
}
}
}
void zgb1(int x,int y,int *q,int *p,int m) //分治策略函數
{
if(y-x==1) //判斷下標的值域
{
if(y==m) //判斷臨界值，選擇排序值的調用
zgb2(q[x],q[y],n,p);
else
zgb2(q[x],q[y],q[y+1],p); //調用排序函數
q[y]=-1;
}
int h=(x+y)/2; //計算規劃值
if(y-x>=2)
{
zgb1(x,h,q,p,m); //遞歸調用函數本身
zgb1(h+1,y,q,p,m);
}

}
/*
排序函數
*/
void zgb2(int x,int y,int z,int *p)
{
int i,j,k,s;
for(i=y; i<z; i++)
for(j=x; j<z; j++)
if(p[i]<p[j])
{
k=p[i];
p[i]=p[j];
p[j]=k;
}
}

③ 排序演算法有多少種

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般來說有升序排列和降序排列2種排序，在演算法中有8中基本排序：
(1)冒泡排序；
(2)選擇排序；
(3)插入排序；
(4)希爾排序；
(5)歸並排序；
(6)快速排序；
(7)基數排序；
(8)堆排序；
(9)計數排序；
(10)桶排序。
插入排序
插入排序演算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的後面，因此插入該元素後並未改變原序列的前後順序。我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。
冒泡排序
冒泡排序演算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和演算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重復進行上述計算，直至完成第(n一1)個和第n個記錄的關鍵字之間的比較，此後，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴格的穩定排序演算法，它不改變序列中相同元素之間的相對位置關系。
選擇排序
選擇排序演算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置即可；以此類推，重復進行「最小元素」的選擇，直至完成第(n-1)個位置的元素選擇，則第n個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同於冒泡法的細節。舉例說明：序列58539．我們知道第一遍選擇第1個元素「5」會和元素「3」交換，那麼原序列中的兩個相同元素「5」之間的前後相對順序就發生了改變。因此，我們說選擇排序不是穩定的排序演算法，它在計算過程中會破壞穩定性。
快速排序
快速排序的基本思想是:通過一趟排序演算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分後的這兩塊序列的元素分別再次實行快速排序演算法，排序實現的整個過程可以是遞歸的來進行調用，最終能夠實現將所需排序的無序序列元素變為一個有序的序列。
歸並排序
歸並排序演算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規則進行排序為長序列。歸並排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合並得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列；將上述步驟重復操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該演算法不會破壞序列的穩定性，即歸並排序也是穩定的排序演算法。

④ 4321是自然排序嗎

不是。
自然排列是接自然順序排列，就是沒有任何條件（默認）所組成的排列：如1234就是自然排列。如果順序被打亂，就要考察逆序數。
函數實現了一個和人們通常對字母數字字元串進行排序的方法一樣的排序演算法並保持原有鍵／值的關聯，這被稱為「自然排序」。

⑤ 關於c語言排序問題

排 序：
程序員可以使用的基本排序演算法有5種：
·插入排序(insertionsort．)
·交換排序(exchangesOrt)
·選擇排序(selectionsort)
·歸並排序(mergesort)
·分布排序(distributionsort)

為了形象地解釋每種排序演算法是怎樣工作的，讓我們來看一看怎樣用這些方法對桌上一付亂序的牌進行排序。牌既要按花色排序(依次為梅花、方塊、紅桃和黑心)，還要按點數排序(從2到A)。
插入排序的過程為：從一堆牌的上面開始拿牌，每次拿一張牌，按排序原則把牌放到手中正確的位置。桌上的牌拿完後，手中的牌也就排好序了。
交換排序的過程為：
(1)先拿兩張牌放到手中。如果左邊的牌要排在右邊的牌的後面，就交換這兩張牌的位置。
(2)然後拿下一張牌，並比較最右邊兩張牌，如果有必要就交換這兩張牌的位置。
(3)重復第(2)步，直到把所有的牌都拿到手中。
(4)如果不再需要交換手中任何兩張牌的位置，就說明牌已經排好序了；否則，把手中的牌放到桌上，重復(1)至(4)步，直到手中的牌排好序。
選擇排序的過程為：在桌上的牌中找出最小的一張牌，拿在手中；重復這種操作，直到把所有牌都拿在手中。
歸並排序的過程為：把桌上的牌分為52堆，每堆為一張牌。因為每堆牌都是有序的(記住，此時每堆中只有一張牌)，所以如果把相鄰的兩堆牌合並為一堆，並對每堆牌進行排序，就可以得到26堆已排好序的牌，此時每一堆中有兩張牌。重復這種合並操作，就可以依次得到13堆牌(每一堆中有4張牌)，7堆牌(有6堆是8張牌，還有一堆是4張牌)，最後將得到52張的一堆牌。
分布排序(也被稱作radix sort，即基數排序)的過程為：先將牌按點數分成13堆，然後將這13堆牌按點數順序疊在一起；再將牌按花色分成4堆，然後將這4堆牌按花色順序疊在一起，牌就排好序了。
在選用排序演算法時，你還需要了解以下幾個術語：
(1)自然的(natural)
如果某種排序演算法對有序的數據排序速度較快(工作量變小)，對無序的數據排序速度卻較慢(工作變數大)，我們就稱這種排序演算法是自然的。如果數據已接近有序，就需要考慮選用自然的排序演算法。
(2)穩定的(stable)
如果某種排序演算法能保持它認為相等的數據的前後順序，我們就稱這種排序演算法是穩定的。
例如，現有以下名單：
Mary Jones
Mary Smith
Tom Jones
Susie Queue
如果用穩定的排序演算法按姓對上述名單進行排序，那麼在排好序後"Mary Jones」和"Tom Jones」將保持原來的Jr順序，因為它們的姓是相同的。
穩定的排序演算法可按主、次關鍵字對數據進行排序，例如按姓和名排序(換句話說，主要按姓排序，但對姓相同的數據還要按名排序)。在具體實現時，就是先按次關鍵字排序，再按主關鍵字排序。
(3)內部排序(internal sort)和外部排序(external sort)
待排數據全部在內存中的排序方法被稱為內部排序，待排數據在磁碟、磁帶和其它外存中的排序方法被稱為外部排序。

查 找：
和排序演算法一樣，查找(searching)演算法也是計算機科學中研究得最多的問題之一。查找演算法和排序演算法是有聯系的，因為許多查找演算法依賴於要查找的數據集的有序程度。基本的查找演算法有以下4種：
·順序查找(sequential searching)。
·比較查找(comparison searching)
·基數查找(radix searching)
·哈希查找(hashing)
下面仍然以一付亂序的牌為例來描述這些演算法的工作過程。
順序查找的過程為：從第一張開始查看每一張牌，直到找到要找的牌。
比較查找(也被稱作binarysearching，即折半查找)要求牌已經排好序，其過程為：任意抽一張牌，如果這張牌正是要找的牌，則查找過程結束。如果抽出的這張牌比要找的牌大，則在它前面的牌中重復查找操作；反之，則在它後面的牌中重復查找操作，直到找到要找的牌。
基數查找的過程為：先將牌按點數分成13堆，或者按花色分成4堆。然後找出與要找的牌的點數或花色相同的那一堆牌，再在這堆牌中用任意一種查找演算法找到要找的牌。
哈希查找的過程為：
(1)在桌面上留出可以放若干堆牌的空間，並構造一個函數，使其能根據點數和花色將牌映射到特定的堆中(這個函數被稱為hashfunction，即哈希函數)。
(2)根據哈希函數將牌分成若干堆。
(3)根據哈希函數找到要找的牌所在的堆，然後在這一堆牌中找到要找的牌。
例如，可以構造這樣一個哈希函數：
pile=rank+suit
其中，rank是表示牌的點數的一個數值；suit是表示牌的花色的一個數值；pile表示堆值，它將決定一張牌歸入到哪一堆中。如果用1，2，……，13分別表示A，2，……．K，用0，1，2和3分別表示梅花、方塊、紅桃和黑桃，則pile的值將為1，2，……，16，這樣就可以把一付牌分成16堆。
哈希查找雖然看上去有些離譜，但它確實是一種非常實用的查找演算法。各種各樣的程序，從壓縮程序(如Stacker)到磁碟高速緩存程序(如SmartDrive)，幾乎都通過這種方法來提高查找速度，

排序或查找的性能：
有關排序和查找的一個主要問題就是速度。這個問題經常被人們忽視，因為與程序的其餘部分相比，排序或查找所花費的時間幾乎可以被忽略。然而，對大多數排序或查找應用來說，你不必一開始就花很多精力去編制一段演算法程序，而應該先在現成的演算法中選用一種最簡單的(見3．1和3．4)，當你發現所用的演算法使程序運行很慢時，再換用一種更好的演算法(請參見下文中的介紹)。
下面介紹一種判斷排序或查找演算法的速度的方法。
首先，引入一個演算法的復雜度的概念，它指的是在各種情況(最好的、最差的和平均的)下排序或查找需要完成的操作次數，通過它可以比較不同演算法的性能。
演算法的復雜度與排序或查找所針對的數據集的數據量有關，因此，引入一個基於數據集數據量的表達式來表示演算法的復雜度。
最快的演算法的復雜度O(1)，它表示演算法的操作次數與數據量無關。復雜度O(N)(N表示數據集的數據量)表示演算法的操作次數與數據量直接相關。復雜度O(logN)介於上述兩者之間，它表示演算法的操作次數與數據量的對數有關。復雜度為O(NlogN)(N乘以logN)的演算法比復雜度為O(N)的演算法要慢，而復雜度為O(N2)的演算法更慢。
注意：如果兩種演算法的復雜度都是O(logN)，那麼logN的基數較大的演算法的速度要快些，在本章的例子中，logN的基數均為10

⑥ C語言排序

排序：基本排序演算法
程序員可以使用5種：

路插入排序（insertionsort.）

路交換排序（exchangesOrt）

路選擇排序（selectionsort）路排序（歸並）合並

路分配排序（distributionsort）

為了生動地解釋每個排序演算法的工作原理，讓我們來看看如何在桌子上，隨機使用這些方法該卡支付排序。排序根據色卡只（順序梅花，方塊，紅心和黑色心臟），而且還排序由點（從2到A）。

插入排序過程：從一堆卡片的頂部開始拿牌，每人持有一張卡，根據卡的原則納入排序正確的位置的手中。在桌子上拿著卡後，遞給排序的卡。

交換排序過程為：

（1）獲得兩張牌到手上。如果卡到左邊在卡的背面右側，以換取這兩張牌的位置。

（2）然後把一張卡，如果有必要比較一下最右邊的兩張牌，以換取這兩張牌的位置。

（3）重復步驟（2），直到所有的牌都拿到手。

（4）如果位置不再有任何需要交換的兩張牌的手，就說明這個品牌已經被排序，否則，出牌桌上的雙手，重復（1）至（4）步驟，直到他們的手來分類的。

選擇排序過程：找到最小的卡牌在桌子上，並拿在手中，重復這個過程，直到所有的牌都在你手中。

歸並排序過程：上表中的卡片被劃分為52的反應器，每個反應器到卡上。因為每堆牌是有序的（記住，這個時候每個堆疊只有一個卡），所以如果卡分成兩堆相鄰樁，每樣的堆卡，你可以得到26堆已排序的卡，然後每堆有兩張卡。重復此合並操作，你可以把堆有13張牌（有四張牌中每根樁），7堆疊卡（有六個反應堆八張牌，有一堆的四張牌），最後將獲得52樁卡。

分配排序（也稱為基數排序，即基數排序）過程是：首先由卡13點到堆中，並根據卡疊在一起的順序堆疊這13點，然後通過許可西裝4分堆，那麼這四張牌由花色順序疊堆在它排序的卡。

在選擇排序演算法，你還需要了解以下條款：

（1）自然（自然）

如果某種有序的數據排序演算法的比較快（工作變小），排序為無序的速度數據較慢（工作變大），我們稱這種排序演算法是很自然的。如果數據已接近有序，就需要考慮使用自然排序演算法。

（2）穩定（穩定）

如果一個排序演算法可以保持審議之前和之後的序列數據相等，我們稱這種排序演算法是穩定的。

例如，下面的現有列表：

瑪麗·瓊斯

瑪麗·史密斯

湯姆·瓊斯

蘇西隊列

如果上面的列表中一個穩定的排序演算法由姓氏排序，那麼「瑪麗·瓊斯」和「湯姆·瓊斯」JR將維持原有的秩序，因為他們的姓是一樣的後整理。

穩定的排序演算法可以是一級，二級關鍵字的數據，如名字和姓氏（排序排序換句話說，按姓氏的主要排序，但在相同的姓氏，而且按名稱排序的數據）。在具體實施時，按下第二個鍵進行排序，然後鍵排序。

（3）內部排序（內部排序）和外部排序的所有排序方法被稱為內部排序，將排在磁碟，磁帶的數據在內存中的數據（外部排序）

鱗次櫛比，及其他事情存款排序方法被稱為外部排序。

查找：

和排序演算法，找到一個（搜索）演算法也是研究最多的計算機科學問題。查找演算法和排序演算法是鏈接的，因為許多搜索演算法依賴於數據集找到有序度。基本的搜索演算法有以下四種：

路順序查找（順序檢索）。

路查找比較（比較搜索）

路查找底數（基數搜索）

路哈希查找（哈希）

下面是照樣出，以支付卡為例，描述這些演算法的工作過程。

順序查找過程如下：從第一個開始，看看每個卡，直到你找到找卡。

比較搜索（也稱為binarysearching，即二進制搜索）的發牌條件已排序，其過程是：任意抽一張牌，如果卡找卡，然後找到該進程的結束。如果繪制的不是尋找更大的卡此卡，該卡在它前面反復查找操作，相反，品牌的背後是反復的查找操作，直到你找到找卡。 13分第一個卡插入堆，或按顏色分為四個樁：

基地查找過程。然後找到並找到點或卡那一堆相同花色的牌，然後在這堆使用的搜索演算法中的任何一個尋找尋找卡牌。

哈希查找過程是：

（1）留在桌上可以放幾堆卡空間，構造一個函數，根據花色和等級，以便它可以被映射到一個特定的品牌樁（該函數被調用散列函數，即哈希函數）。

（2）根據散列功能卡片分成若干堆。

（3）尋找到樁尋找基於散列函數在卡片上，然後找到望著這堆牌中的卡。

例如，您可以構建這樣一個散列函數：

一堆=等級+西裝

其中，職級是一個數字表示卡點;西裝是一個數字表示牌的花色;說一堆一堆的價值，它決定了一堆卡片掉落。如果1,2，......，13表示一個，2，...... K，1，2，和3，分別與梅花，方塊，紅心和黑桃，然後堆放值將是1，2，...，16，這樣就可以把一副牌分成16堆。

哈希查找，雖然看起來有點可笑，但它確實是一個非常有用的搜索演算法。各種程序，從壓縮程序（如堆高機）的磁碟緩存程序（如的SmartDrive），幾乎所有的這種方式來提高搜索速度，或發現性能

排序：
>其中一個主要問題是排序和搜索的速度。這個問題往往被忽視，與程序的其他部分相比，還是覺得它需要排序的時間幾乎可以忽略不計。然而，對於大多數應用程序，排序或查找，你不必花費大量的精力開始准備一些演算法，但應可在選擇最簡單的演算法之一（見3.1和3.4），當你發現演算法當程序有更好的演算法運行速度非常慢，而且回來（見下面的說明）使用。

這里有一個排序或搜索演算法，以確定方法的速度。

一，引進的一種演算法，它是指在所有情況下（最好和最差的平均值）查找需要進行排序或完成作業的數量，從而可以比較不同性能的復雜性的概念的演算法。復雜性和數據進行排序或查找數據集針對

演算法的量，因此，表達數據集的量引入基於所述演算法的復雜度的表示。 最快的演算法復雜度，它代表操作的數量無關，與演算法的數據量。 O（N）的復雜度（N表示數據集的數量）指示操作的數目直接相關的數據的量的演算法。為O（logN）的復雜性兩者之間，其指示操作的數量和相關的演算法的對數的數據量。復雜度為O（nlogn）的（N乘以logN）的演算法比復雜度為O（N）的演算法是緩慢的，而且復雜度為O（N2）演算法慢。
注意：如果兩種演算法的復雜度為O（logN）的，則演算法的logN的基數較大的速度要快於本章中的例子，logN的基數是10

⑦ 排序演算法是怎樣的

一、背景介紹

在計算機科學與數學中，排序演算法（Sorting algorithm）是一種能將一串資料依照特定排序方式進行排列的一種演算法。

最常用到的排序方式是數字順序以及字典順序。

有效的排序演算法在一些演算法（例如搜尋演算法與合並演算法）中是重要的， 如此這些演算法才能得到正確解答。

排序演算法也用在處理文字資料以及產生人類可讀的輸出結果。

基本上，排序演算法的輸出必須遵守下列兩個原則：

1、輸出結果為遞增序列（遞增是針對所需的排序順序而言）；

2、輸出結果是原輸入的一種排列、或是重組；

雖然排序演算法是一個簡單的問題，但是從計算機科學發展以來，在此問題上已經有大量的研究。 更多的新演算法仍在不斷的被發明。

二、知識剖析

查找和排序演算法是演算法的入門知識，其經典思想可以用於很多演算法當中。因為其實現代碼較短，應用較常見。 所以在面試中經常會問到排序演算法及其相關的問題。但萬變不離其宗，只要熟悉了思想，靈活運用也不是難事。

一般在面試中最常考的是快速排序和冒泡排序，並且經常有面試官要求現場寫出這兩種排序的代碼。對這兩種排序的代碼一定要信手拈來才行。除此之外，還有插入排序、冒泡排序、堆排序、基數排序、桶排序等。

三、常見的幾種演算法：

冒泡演算法、選擇排序、插入排序、希爾排序、歸並排序、快速排序

演算法的特點：

1、有限性：一個演算法必須保證執行有限步之後結束。

2、確切性： 一個演算法的每一步驟必須有確切的定義。

3、輸入：一個演算法有零個或多個輸入，以刻畫運算對象的初始情況，所謂零個輸入是指演算法本身給定了初始條件。

4、輸出：一個演算法有一個或多個輸出。沒有輸出的演算法毫無意義。

5、可行性：演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）。

⑧ 排序演算法有哪些，簡述快速排序的核心

簡單的: 冒泡,選擇排序,插入排序,桶排序,

復雜點的: 堆排序,歸並排序,快速排序,

還有基數排序,計數排序(這兩個我還沒接觸到,不懂)

快速排序核心:

每次排序的時候設置一個基準點，將小於等於基準點的數全部放到基準點的左邊，將大於等於基準點的數全部放到基準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣只能在相鄰的數之間進行交換，交換的距離就大得多了。因此總的比較和交換次數就少了，速度自然就提高了。

圖片及快速排序簡述來源於<啊哈演算法>

⑨ 常用的排序演算法都有哪些

排序演算法 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。
一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。
當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重復2號步驟，直至原數列為空。
插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重復2號步驟，直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設數組內存放了n個待排數字，數組下標從1開始，到n結束。
i=1
從數組的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同，它是這樣的：
首先新建一個空列表，作用與插入排序中的"有序列表"相同。
找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重復2號步驟，直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。
看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
冒泡排序
654
比如說這個，我想讓它從小到大排序，怎麼做呢？
第一步：6跟5比，發現比它大，則交換。564
第二步：5跟4比，發現比它大，則交換。465
第三步：6跟5比，發現比它大，則交換。456

⑩ strnatcmp — 使用自然排序演算法比較字元串

這函數經常用到，這是總結後的知識點，如下：
strnatcmp
(PHP 4, PHP 5, PHP 7, PHP 8)
strnatcmp — 使用自然排序演算法比較字元串
說明
strnatcmp ( string $str1 , string $str2 ) : int
該函數實現了以人類習慣對數字型字元串進行排序的比較演算法，這就是「自然順序」。注意該比較區分大小寫。
參數
str1
第一個字元串。
str2
第二個字元串。
返回值
與其他字元串比較函數類似，如果 str1 小於 str2 返回 < 0； 如果 str1 大於 str2 返回 > 0；如果兩者相等，返回 0。