当前位置:首页 » 数据结构精品文章 » 正文

各种排序方法的介绍与比较

1720 人参与  2018年09月03日 23:14  分类 : 数据结构精品文章  评论

前记:这一章中主要对数据排序相关的概念和方法进行了讲解,今天的拓展资源就对排序的基本概念、几种常见排序方法的算法及优缺点、插入排序的算法和C语言实现等,同学们多了解一下。

排序:是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

内部排序:若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序;内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

外部排序:若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。

  内排序的方法有许多种,按所用策略不同,可归纳为五类:插入排序、选择排序、交换排序、归并排序和分配排序。

  其中,插入排序主要包括直接插入排序和希尔排序两种;选择排序主要包括直接选择排序和堆排序;交换排序主要包括气(冒)泡排序和快速排序。

一、冒泡排序

  已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变。再比较a[2]与a[3]的值,若a[2]大于a[3]则交换两者的值,否则不变。再比较a[3]与a[4],以此类推,最后比较a[n-1]与a[n]的值。这样处理一轮后,a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮,则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮,以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

优点:稳定,比较次数已知;

缺点:慢,每次只能移动相邻两个数据,移动数据的次数多。

二、选择排序

  已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变。再比较a[1]与a[3]的值,若a[1]大于a[3]则交换两者的值,否则不变。再比较a[1]与a[4],以此类推,最后比较a[1]与a[n]的值。这样处理一轮后,a[1]的值一定是这组数据中最小的。再将a[2]与a[3]~a[n]以相同方法比较一轮,则a[2]的值一定是a[2]~a[n]中最小的。再将a[3]与a[4]~a[n]以相同方法比较一轮,以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

优点:稳定,比较次数与冒泡排序一样;

缺点:相对之下还是慢。

三、插入排序

  已知一组升序排列数据a[1]、a[2]、……a[n],一组无序数据b[1]、b[2]、……b[m],需将二者合并成一个升序数列。首先比较b[1]与a[1]的值,若b[1]大于a[1],则跳过,比较b[1]与a[2]的值,若b[1]仍然大于a[2],则继续跳过,直到b[1]小于a数组中某一数据a[x],则将a[x]~a[n]分别向后移动一位,将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。(若无数组a,可将b[1]当作n=1的数组a)

优点:稳定,快;

缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决这个问题。

四、缩小增量排序

  由希尔在1959年提出,又称希尔排序 (shell排序)。

  已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。发现当n不大时,插入排序的效果很好。首先取一增量d(d<n),将a[1]、a[1+d]、a[1+2d]……列为第一组,a[2]、a[2+d]、a[2+2d]……列为第二组……,a[d]、a[2d]、a[3d]……列为最后一组以次类推,在各组内用插入排序,然后取d'<d,重复上述操作,直到d=1。

优点:快,数据移动少;

缺点:不稳定,d的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取。

五、快速排序

  快速排序是冒泡排序的改进版,是目前已知的最快的排序方法。

  已知一组无序数据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]中的每一个数据>a[x],然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。

优点:极快,数据移动少;

缺点:不稳定。

六、箱排序

已知一组无序正整数数据a[1]、a[2]、……a[n],需将其按升序排列。首先定义一个数组x[m],且m>=a[1]、a[2]、……a[n],接着循环n次,每次x[a]++.

优点:快,效率达到O(1)。

缺点:数据范围必须为正整数并且比较小。

插入算法的算法描述:

  一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序

  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描

  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置

  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

  5. 将新元素插入到该位置中

  6. 重复步骤2

如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。

示例代码:

示例代码为C语言,输入参数中,需要排序的数组为array[],起始索引为first,终止索引为last。示例代码的函数采用in-place排序,调用完成后,array[]中从first到last处于升序排列。

void insertion_sort(char array[], unsigned int first, unsigned int last)
{
  int i,j;
  int temp;
  for (i = first+1; i<=last;i++)
  {
  temp = array;
  j=i-1;
  //与已排序的数逐一比较, 大于temp时, 该数移后
  while((j>=first) && (array[j] > temp))
  {
  array[j+1] = array[j];
  j--;
  }
  array[j+1] = temp;
  }
  }
  这个更好:
  void InsertSort(char array[],unsigned int n)
  {
  int i,j;
  int temp;
  for(i=1;i<n;i++)
  {
  temp = array;//store the original sorted array in temp
  for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
  {
  array[j]=array[j-1];//all larger elements are moved one pot to the right
  }
  array[j]=temp;
  }
  }
  这个是c++语言版本的插入排序。为了支持list使用了std::advance()。
  #include <iterator>
  template<typename biIter>
  void insertion_sort(biIter begin, biIter end)
  {
  typedef typename std::iterator_traits<biIter>::value_type value_type;
  biIter bond = begin;
  std::advance(bond, 1);
  for(; bond!=end; std::advance(bond, 1)) {
  value_type key = *bond;
  biIter ins = bond;
  biIter pre = ins;
  std::advance(pre, -1);
  while(ins!=begin && *pre>key) {
  *ins = *pre;
  std::advance(ins, -1);
  std::advance(pre, -1);
  }
  *ins = key;
  }
}

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=210

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!