舞动的排序算法~1

H9enRy

　在计算机中，排序算法有很多，包括插入排序，堆排序，归并排序，选择排序，计数排序，基数排序，桶排序，快速排序等。插入排序，堆排序，选择排序，归并排序和快速排序都是比较排序，它们通过对数组中的元素进行比较来实现排序，其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。

　　下面是 admin10000.com 整理的视频案例来介绍选择，冒泡，插入，归并，快速和希尔排序。视频由 Sapientia University 创作，他们以舞蹈的方式演绎各种排序算法，创意无限，非常精彩。

　　一、选择排序 select sort

　　选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

　　算法思路：

　　每一次从待排序的数据元素中选出最小的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

　　算法描述：

　　1、第一轮排序，在无序区中选出最小的记录，将它与无序区的第1个记录交换，使有序区记录个数增加1个（即记录个数变为1个），无序区记录个数减少1个。

　　2、第二轮排序，在无序区中选出最小的记录，将它与无序区的第1个记录交换，使有序区记录个数增加1个（即记录个数变为2个），无序区记录个数减少1个。

　　3、如此下去，重复以上过程，直至最终完成排序。

二、冒泡排序 Bubble Sort

　　冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

　　算法思路：

　　依次比较相邻的两个数，将小数放在前面，大数放在后面。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

　　设想被排序的数组垂直竖立，将每个数据元素看作有重量的气泡（为了便于理解，此处规定大数对应轻气泡），根据轻气泡不能在重气泡之下的原则，从下往上扫描数组，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

　　算法描述：

　　1、在第一轮，首先比较第1个和第2个数，将小数放前，大数放后；然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一轮结束，将最大的数放到了最后。

　　2、在第二轮，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二轮结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。

　　3、如此下去，重复以上过程，直至最终完成排序。

　　三、插入排序 Insert sort

　　插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

　　算法思路：

　　假定一个数组的序是排好的，然后从前往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止。这种算法在排完前k个数之后，可以保证前k个元素是局部有序的，保证了插入过程的正确性。

　　算法描述：

　　1、从第一个元素开始，该元素可以认为已经被排序。

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

　　3、如果该元素（已排序）大于新元素，将该元素移到下一位置。

　　4、重复第3步，直到找到已排序的元素小于或者等于新元素的位置。

　　5、将新元素插入到下一位置中。

　　6、重复第2步。

　四、归并排序 Merge sort

　　归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

　　算法思路：

　　将两个或两个以上有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

　　算法描述：

　　1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。

　　2、设定两个指针，最初位置分别为两个已经排序序列的起始位置。

　　3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。

　　4、重复第3步，直到某一指针达到序列尾。

　　5、将另一序列剩下的所有元素直接复制到合并序列尾。

　　五、快速排序 Quick sort

　　快速排序（Quick sort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

　　算法思路：

　　通过一轮排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

　　算法描述：

　　1、设置两个变量i、j，排序开始的时候，i是第一个元素的下标，j是最后一个元素的下标。

　　2、从第j个元素开始向前搜索，即由后开始向前搜索，找到第一个小于第i个元素的数，设其下标为m，第i个元素与第m个元素交换。

　　3、从第i个元素开始向后搜索，即由前开始向后搜索，找到第一个大于第m个元素的数，设其下标为n，第m个元素与第n个元素交换。

　　4、重复第2步和第3步，直到m与n相等，则第一轮排序结束，确定下来的一个元素将数组分割成独立的两部分，对这独立的两部分再进行快速排序，直至最终完成排序。

　六、谢尔排序 Shell sort

　　希尔排序（Shell Sort），也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的：插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率,但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。

　　算法思路：

　　取一个小于数组元素个数的整数作为第一个增量，把数组的全部元素分组，同一组中的所有元素下标距离均为增量的倍数，先在各组内进行直接插入排序。然后，取第二个增量小于第一个增量重复上述的分组和排序，直至所取的增量等于1，即所有元素放在同一组中进行直接插入排序为止。

　　算法描述：

　　1、取一个小于数组元素个数的整数d1作为第一个增量，把数组的全部元素分成d1个组，所有距离为d1的倍数的记录放在同一个组中。在各组内进行直接插入排序。

　　2、取第二个增量d2＜d1重复上述的分组和排序。

　　3、取更小的增量重复上述的分组和排序，直至所取的增量dt＝1（dt＜dt－1＜……<d2＜d1），即所有记录放在同一组中进行直接插入排序为止。