菜单

精良算法种类–排序算法(一)

2019年8月29日 - 金沙编程资讯

 排序算法是我们常用算法之一,也是Computer程序设计中的一种重大操作,它的效用是将三个数量成分(或记录)的即兴系列,重新排列成多少个生死攸关字有序的队列。排序进程中提到的存款和储蓄器分歧,可将排序方法分为两大类:一类是内排序,指的是待排序记录寄放在微型计算机随机存款和储蓄器中开展的排序进度,内排序有:插入排序、Hill排序、沟通排序、快捷排序、选取排序等;另一类是向外排水序,指的是待排序记录的数目比非常大,以至内部存款和储蓄器二回不可能包容全数记下,在排序进程中尚需对外部存款和储蓄器进行拜候的排序进度。

   
下边说一下置换排序,调换排序主要有:冒泡排序和飞跃排序,飞速排序(Quicksort)其实是对冒泡排序的一种创新。

     为了便利描述,使用种种表类型定义如下:

#define MAXSIZE 1000
typedef int KeyType;
typedef struct {
         KeyType key;
         InfoType otherinfo;
}RecType;

typedef struct {
         RecType r[MAXSIZE+1];
         int length;
}SqList;
  

冒泡排序
基本概念是:依次比较相邻的五个数,将小数放在前面,大数放在前面。整个排序进程最多实践n-1趟,它是一种和煦的算法。

  C Code:

void BubbleSort(SqList &q)
{
int j,h,p=q.length-1,temp;
for(h=1;h<=p;)
  for(j=0;j<p-1;j++)
    if(q.r[j].Key>q.r[j+1].key)
     {
      temp=q.r[j];
      q.r[j]=q.r[j+1];
      q.r[j+1]=temp;
      p=j
     }
}
  冒泡排序法存在那相差,当排序的数据非常多时排序的日子会刚强延长。具体做法:自便选取某一记录(日常取第二个记录),比较其着重字与全数记录的要紧字,并将重大字比它小的记录整个位居它的先头,将比它大的笔录均寄放在它的末尾,那样,经过三回排序之后,可将兼具记录以该记录所在的分界点分为两有个别,然后分别对这两有的开展高效排序,直至排序完
,那就是立异的办法:急迅排序。

快速排序
     设要排序的数组是a[0]……a[n-1],

      一趟高速排序的算法是:

  1)设置七个变量low、high,排序开端的时候:low=0,low=n-1;

  2)以第二个数组成分作为第一数据,赋值给key,即 key=a[0];

  3)从J开端向前搜索,即由后开始向前找寻(high=high-1),找到第二个低于key的值a[high],并与a[low]交换;

  4)从I初叶向后查找,即由前开始向后查找(low=low+1),找到第一个抢先key的a[low],与a[high]交换;

  5)重复第3、4、5步,直到 low=high;

      示意图:

 图片 1

C Code:

void QuickSort(SqList &R ,int s,int t)
{
   int low, high,Key;
   low=s;
   high=t;
   Key=R.r[s].key;
   R.r[0]=R.r[s];
   while(low<high)
    {
        while(high>low&&R.r[high].key>Key)
          high–;
        if(low<high)
        {
         R.r[low]=R.r[high];
         low++;
         }
        while(low<high&&R.r[high].key<=Key)
         ++low;
        if(low<high)
        {
         R.r[high]=R.r[low];
         high–;
         }
    }
    R.r[low]=R.r[0];
    QuickSort(R,s,low-1);
    QuickSort(R,low+1,t);
}
  好了,就先提起这边了。

 作者“flute的专栏”
 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图