自然排序算法

① 用“自然排序”算法对数组排序

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。