|
1.排序的概念和运用 1.1排序的概念： 排序：所谓排序，就是将一串数据，按照某种规律，或者以某种特性或关键字，将数据按照递增或者递减，将数据从无序转变为有序的操作。 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，则称之为稳定。例如a[i]=a[j]，且a[i]在a[j]之前，而在排序后的序列中，a[i]仍在a[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。 内部排序：内部排序也称为内排序，是指待排的记录全部在内存中完成排序的过程，是被排序的数据元素全部存放在计算机内存中的排序算法。 外部排序：外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。根据排序过程的要求，是不能在内外存之间移动数据的排序。 1.2.常见排序应用： 而排序其实在我们生活中运用十分广泛，例如在购物网站上选购一个电脑，可以通过综合、销量、评论数、新品价格来排序，如果对价格有需求，也可以按照价格升序，或者降序来排序，通过这种方式来买到心仪的商品。 不难发现，在我们的日常生活中排序算的使用随处可见，充斥着我们的各项生产活动，我们的考试排名、绩效考核、综测排名，包括CSDN的各种排名都广泛的使用到了许多种不尽相同的排序算法。 而究其根本，这些都需要排序算法来实现。那么在编程中有什么排序算法，它们的性能如何？如何模拟实现这些算法？ 接下来的几篇博客中，我们会依次学习常见的排序算法，并进行对比，以便于我们更好的理解这些算法的使用方式、使用条件与适用场景等等。 2.常见的排序算法： 最常用的排序算法可以分为四大类：插入排序、选择排序、交换排序与归并排序。插入排序的代表算法有直接插入排序与希尔排序；选择排序的排序算法代表是选择排序与堆排序；交换排序中我们要熟识冒泡排序与快速排序；归并排序则主要是以归并排序算法为主，及一些由归并思想衍生出的排序算法。 下图是常见八大排序的比较：  点击加载图片 2、直接插入排序 2.1排序思路 直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。 我们的扑克牌就使用了插入排序的思想：  点击加载图片 比如拿到牌之后，我们都会理牌，那么通常就会按照大小顺序，将牌理成整体有序，或者局部有序。 其实插入排序的过程就可以想象成之前我们学习顺序表的尾插，我们假定序列array[]只有1个数。假定每次都是插入一个元素，且插入的元素需要将这个”顺序表“构成有序，如果插入元素array[i]<>< p=""><> 动图演示插入排序过程：  点击加载图片 2.2代码实现 对于单趟插入排序，假设end是上一次排序的最后一个位置，那么本次需要排序的元素为tmp=a[end+1]。之后通过一个循环，如果a[end]>tmp，说明tmp插入的位置在前面，所以把a[end+1]=a[end]，将元素往后移1格，并将end−−，将索引向前调整；如果a[end]<=tmp，说明tmp在当前位置：end+1就可以直接插入，停止循环。 最后end停下来的位置永远是插入位置的前一个位置，比如看下图：  点击加载图片 这是单趟，那么完整的就是n−1趟，因为第一个元素是不用排的，第一趟其实就是排的序列的第二个元素了。每趟最终插入的位置为end+1，注意防止越界。 完整的多趟实现步骤： 1.从第一个元素开始，该元素可以认为已经被排序。 2.取下一个元素作为tmp，从已排序的元素序列从后向前扫描。 3.如果该元素大于tmp，则将该元素移到下一位。 4.重复步骤3，直到找到已排序元素中小于或等于tmp的元素。 5.将temp插入到该元素的后面，如果已排序所有元素都大于tmp，则将tmp插入到下标为0的位置。 重复步骤2~5，直至完成排序。 voidInserSort(int*a,intn){//多趟控制inti=0;for(i=0;i 2.3特性及复杂度 插入排序的最坏的情况为原始序列为降序。此时，时间复杂度最坏，为O(N^2)。 如果目的是升序，序列也正好是升序的话，为最好情况，这时时间复杂度为O(N)。 取其最坏，最终时间复杂度：O(N^2) 插入排序并没有开辟额外空间，所以空间复杂度：O(1) 特性：元素集合越接近有序，直接插入排序算法的时间效率越高。 时间复杂度：O(N^2)。 空间复杂度：O(1)。 稳定性：稳定。 3、希尔排序 3.1排序思路 希尔排序也属于插入排序，但是和直接插入排序又略微不同。 概念：希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把所有待排序记录记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，即所有记录在统一组内排好序。 简单来说，意思是取一个整数，作为间距gap，对于每个元素，与其间隔为gap的元素分成一个组，对每组排序。不断调整gap，对每组进行不断排序，在gap调整到1后进行插入排序，就可以将数据排成有序。而按照间距gap分组并排序被称为预排序。 所以可以归纳希尔排序的步骤就是两点： 预排序-目标：让数组接近有序（分组插排） 直接插入排序 比如，一次完整希尔排序就像下图： 3.2代码实现 希尔排序属于插入排序，而它的思想其实是和直接插入排序差不多的，因为最后一次希尔排序为插入排序。希尔排序无非就是多了几组预排序的过程。所以它的代码和直接插入排序十分相似。 对于插入排序，我们其实就可以看做是gap=1的希尔排序，那么把插入排序一些数据做一下替换，就得出了单组希尔排序： //对于一组for(inti=0;i 这里的gap不仅是每组中元素的间距，也是组数。上面代码只完成了单组，对于完整的一组需要在外面套上一层循环，需要循环gap次： for(intj=0;j<> 我们发现，只需要把之前的挪动1位看成挪动gap位。 注意对单组进行排序时的结束条件i<>< p=""><> 但这样写，就套了三层循环了，看起来比较繁琐，我们可以做出一些调整，上方代码为排gap组，每次排一组。我们可以改进为gap组并排： for(inti=0;i 这里就只有两层循环了，代码更加简洁，唯一改变的是i+=gap变为i++ 这里就相当于，每一次都是排其他组的数据，举个例子：当前i=0，那么此刻排的就是第一组，之后i++，i=1，那么此刻就是排的第二组…当循环结束，这gap组数据也就都被排好了。这就是gap组并排。 而希尔排序的预排序的gap越大时，那么对于单组中的数据就可以更快地到后面(挪动间距为gap)，但这时的数据并不接近有序；而gap越小时，数据跳动越慢，但是越来越接近有序(比如插入排序)。综合这两点，所以我们一般进行希尔排序时，gap是动态变化的，gap的初值一般为数组长度。之后每次除以一半或者除以三分之一。 比如每次除以三分之一： while(gap>1)//gap=1已经排过了{gap=gap/3+1;//或gap/=2;//gap组并排for(inti=0;i 分析： 这里调整是用的gap=gap/3+1，为什么在这边+1呢？原因是希尔排序最后1次为插入排序，所以最后1次gap=1，如果gap初值为8，如果每次仅仅让gap/=3，由于c语言中/是下取整，那么每次gap就为820，最后1次为0，无法完成希尔排序，所以要加上一个1，这样就可以保证最后1次gap=1。 但是如果每次除以2的情况就不需要，因为每gap/=2最终结果必定等于1，可以通过举例子证明。 3.3特性及复杂度 数据被分为gap组，每组有N/gap个数据。对于单组，最坏的挪动次数就是1+2+3+…+N/gap−1，是公差为1的等差数列。 一共有gap组，那么对于一次预排序的总次数就为(1+2+3+…+N/gap−1)×gap，但是这里gap是不确定的。那对于每次预排序的时间复杂度，该怎么计算? 1.首先，根据代码分析 如果gap每次除以3，那么就大约进行N/3/3/3…/3=log3N次； 如果gap每次除以2，那么就大约进行N/2/2/2…/2=log2N次； 2.其次，假设gap每次除以3，一开始N很大，gap=N/3+1，将当前gap的取值带入上方对于一次预排序的次数的公式中，通过极限的思想，(1+2+3+...+N(N/3+1)N\over(N/3+1) (N/3+1) N 快结束时，gap很小，本应该是N^2，但因为此刻由于预排序的作用，数组几乎有序，几乎不需要排序，这时次数也约为N 而中间的计算结果需要的数学知识比较难，所以暂时先就将起始两次的结果作为每次预排序的结果，时间复杂度为O(N)。 3.那么综合起来，实际上希尔排序的时间复杂度大约在[log3N∗N,log2N∗N] 这个量级之间，和我们之前学习过的堆排序的时间复杂度相近。 但是这只是我们的一些计算推导，实际上希尔排序真正的时间复杂度很难计算，上面的计算只是简单推导而已，里面其实涉及到了很多数学知识，所以我们参考一下一些著名的数据结构书籍中对于希尔排序时间复杂度的分析： 《数据结构(C语言版)》—严蔚敏： 而gap是按照Knuth大佬提出的方式取值的，Knuth大佬进行了大量的试验统计，得出最接近的结论，希尔排序的最终时间复杂度为O(N^1.3)左右。但如果有一天能找到最佳的gap，说不定快速排序的位置就被希尔取代了(bushi) 而空间复杂度就很简单了，并没有开辟额外的空间，所以空间复杂度为O(1)。 特性：希尔排序是对直接插入排序的优化。 当增量>1时都是预排序，目的是让数组更接近于有序。当增量为1时，数组已经接近有序了，再进行排序就能提高算法执行的时间效率。 时间复杂度：O(N^1.3)。 空间复杂度：O(1)。 稳定性：不稳定。 4.总结： 今天我们认识并学习了排序算法的相关概念，并且具体学习了插入排序算法中的直接插入排序和希尔排序。下一篇博客，我们将继续学习交换排序中的直接选择排序和堆排序。希望我的文章和讲解能对大家的学习提供一些帮助。 当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~ 点 |
|
|
