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)的排序方法:快速排序、堆排序或归并排序序。

快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
堆排序 : 如果内存空间允许且要求稳定性的,

归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

2)当n较大,内存空间允许,且要求稳定性 =》归并排序

3)当n较小,可采用直接插入或直接选择排序。

直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

5)一般不使用或不直接使用传统的冒泡排序。

6)基数排序
它是一种稳定的排序算法,但有一定的局限性:
1、关键字可分解。
2、记录的关键字位数较少,如果密集更好
3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C/C++实现快速排序的方法

    快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边.(你可以想象一下i和j是两个机器人,数据就是大小不一的石头,先取走i前面的石头留出回旋的空间,然后他们轮流分别挑选比k大和比k小的石头扔给对面,最后在他们中间把取走的那块石头放回去,于是比这块石头大的全扔给了j那一边,小的全扔给了i那一边.只是这次运气好,扔完一次刚好排整齐.)为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果. -- 取自百度百科

  • 逐步讲解快速排序算法及C#版的实现示例

    算法思想 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序.它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod). 该方法的基本思想是: 1.先从数列中取出一个数作为基准数. 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边. 3.再对左右区间重复第二步,直到各区间只有一个数. 虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤.因此我的对快速排序作了进一步的说明:挖坑填数+分治法:

  • C++快速排序的分析与优化详解

    相信学过数据结构与算法的朋友对于快速排序应该并不陌生,本文就以实例讲述了C++快速排序的分析与优化,对于C++算法的设计有很好的借鉴价值.具体分析如下: 一.快速排序的介绍 快速排序是一种排序算法,对包含n个数的输入数组,最坏的情况运行时间为Θ(n2)[Θ 读作theta].虽然这个最坏情况的运行时间比较差,但快速排序通常是用于排序的最佳的实用选择.这是因为其平均情况下的性能相当好:期望的运行时间为 Θ(nlgn),且Θ(nlgn)记号中隐含的常数因子很小.另外,它还能够进行就地排序,在虚拟内存

  • c语言快速排序算法示例代码分享

    步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat

  • c++ 快速排序算法【过程图解】

    第一.算法描述 快速排序由C. A. R. Hoare在1962年提出,该算法是目前实践中使用最频繁,实用高效的最好排序算法, 快速排序算法是采用分治思想的算法,算法分三个步骤 1.从数组中抽出一个元素作为基数v(我们称之为划界元素),一般是取第一个.最后一个元素或中间的元素 2.将剩余的元素中小于v的移动到v的左边,将大于v元素移动到v的右边 3.对左右两个分区重复以上步骤直到所有元素都是有排序好. 第二.算法实现 /*序列划分函数*/ int partition(int a[], int p

  • C/C++实现八大排序算法汇总

    概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1. 插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已

  • 必须知道的C语言八大排序算法(收藏)

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到

  • python实现八大排序算法(2)

    本文接上一篇博客python实现的八大排序算法part1,将继续使用python实现八大排序算法中的剩余四个:快速排序.堆排序.归并排序.基数排序 5.快速排序 快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的. 算法思想: 已知一组无序数据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]中的每一个数

  • python实现八大排序算法(1)

    排序 排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列.分内部排序和外部排序.若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序.反之,若参加排序的记录数量很大,整个序列的排序过程不可能完全在内存中完成,需要访问外存,则称此类排序问题为外部排序.内部排序的过程是一个逐步扩大记录的有序序列长度的过程. 看图使理解更清晰深刻: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序

  • 八大排序算法的Python实现

    Python实现八大排序算法,具体内容如下 1.插入排序 描述 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法.插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 代码实现 def inser

  • Python实现八大排序算法

    如何用Python实现八大排序算法 1.插入排序 描述 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为 O(n^2).是稳定的排序方法.插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插 入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 代码实现 def insert_

  • python八大排序算法速度实例对比

    这篇文章并不是介绍排序算法原理的,纯粹是想比较一下各种排序算法在真实场景下的运行速度. 算法由 Python 实现,可能会和其他语言有些区别,仅当参考就好. 测试的数据是自动生成的,以数组形式保存到文件中,保证数据源的一致性. 排序算法 直接插入排序 时间复杂度:O(n²) 空间复杂度:O(1) 稳定性:稳定 def insert_sort(array): for i in range(len(array)): for j in range(i): if array[i] < array[j]:

  • Java基础之八大排序算法

    前言 关系 复杂度 一.直接插入排序 基本思想: 将新的数据插入已经排好的数据列中. 将第一个和第二个数排序,构成有序数列 然后将第三个数插进去,构成新的有序数列,后面的数重复这个步骤 算法描述 1.设定插入的次数,即是循环次数,for(int i=1;i<length;i++),1个数的那次不用插入. 2.设定插入的数和得到的已经排好的序列的最后一个数,insertNum和j=i-1. 3.从最后一个数向前开始循环,如果插入数小于当前数就将当前数向前移动一位 4.将当前位置放置到空的位置,即j

  • C/C++语言八大排序算法之桶排序全过程示例详解

    基本思路是将所有数的个位十位百位一直到最大数的最高位一步步装桶,先个位装桶然后出桶,直到最高位入桶出桶完毕. 首先我们要求出一个数组的最大数然后求出他的最大位数 //求最大位数的函数 int getmaxweisu(int* a,int len)// { int max = a[0]; for (int i = 0; i < len; i++) { if (max < a[i]) { max = a[i]; } } int count = 1; while (max/10) { count++

  • C语言 八大排序算法的过程图解及实现代码

    目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关

随机推荐