下载文档原格式
⼗⼤经典排序算法总结最近⼏天在研究算法，将⼏种排序算法整理了⼀下，便于对这些排序算法进⾏⽐较，若有错误的地⽅，还请⼤家指正0、排序算法说明0.1 排序术语稳定：如果a=b,且a原本排在b前⾯，排序之后a仍排在b的前⾯不稳定：如果a=b,且a原本排在b前⾯，排序之后排在b的后⾯时间复杂度：⼀个算法执⾏所耗费的时间空间复杂度：⼀个算法执⾏完所需内存的⼤⼩内排序：所有排序操作都在内存中完成外排序：由于数据太⼤，因此把数据放在磁盘中，⽽排序通过磁盘和内存的数据传输才能进⾏0.2算法时间复杂度、空间复杂度⽐较0.3名词解释n:数据规模k:桶的个数In-place:占⽤常数内存，不占⽤额外内存Out-place:占⽤额外内存0.4算法分类1.冒泡排序冒泡排序是⼀种简单的排序算法。
它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果它们的顺序错误就把它们交换过来。
⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端1.1算法描述⽐较相邻的元素，如果前⼀个⽐后⼀个打，就交换对每⼀对相邻元素做同样的⼯作，从开始第⼀对到结尾最后⼀对，这样在最后的元素应该会是最⼤的数针对所有的元素重复以上的步骤，除了最后⼀个重复步骤1-3，知道排序完成1.2动图演⽰1.3代码实现public static int[] bubbleSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++)for (int j = 0; j < array.length - 1 - i; j++)if (array[j + 1] < array[j]) {int temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}return array;}1.4算法分析最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)2.选择排序表现简单直观的最稳定的排序算法之⼀，因为⽆论什么数据都是O(n2)的时间复杂度，⾸先在未排序序列中找到最⼩（⼤）元素，与数组中第⼀个元素交换位置，作为排序序列的起始位置，然后再从剩余未排序元素中继续寻找最⼩（⼤）的元素，与数组中的下⼀个元素交换位置，也就是放在已排序序列的末尾2.1算法描述1.初始状态：⽆序区为R[1..n],有序区为空2.第i躺排序开始时，当前有序区和⽆序区R[1..i-1]、R[i..n]3.n-1趟结束，数组有序化2.2动图演⽰2.3代码实现public static int[] selectionSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i; j < array.length; j++) {if (array[j] < array[minIndex]) //找到最⼩的数minIndex = j; //将最⼩数的索引保存}int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}return array;}2.4算法分析最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)3、插⼊排序是⼀种简单直观的排序算法，通过构建有序序列，对于未排序序列，在已排序序列中从后向前扫描，找到相应位置并插⼊，需要反复把已排序元素逐步向后挪位，为最新元素腾出插⼊空间3.1算法描述1.从第⼀个元素开始，该元素可以认为已经被排序2.取出下⼀个元素（h），在已排序的元素序列中从后往前扫描3.如果当前元素⼤于h，将当前元素移到下⼀位置4.重复步骤3，直到找到已排序的元素⼩于等于h的位置5.将h插⼊到该位置6.重复步骤2-53.2动图演⽰3.3代码实现public static int[] insertionSort(int[] array) {if (array.length == 0)return array;int current;for (int i = 0; i < array.length - 1; i++) {current = array[i + 1];int preIndex = i;while (preIndex >= 0 && current < array[preIndex]) {array[preIndex + 1] = array[preIndex];preIndex--;}array[preIndex + 1] = current;}return array;}3.4算法分析最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)4、希尔排序是简单插⼊排序经过改进之后的⼀个更⾼效的版本，也称为缩⼩增量排序，同时该算法是冲破O(n2）的第⼀批算法之⼀。
![[已整理]20世纪科学界十大算法](https://img.taocdn.com/s1/m/6bf2028e680203d8ce2f2419.png)
算法竞赛入门经典代码算法竞赛是一个旨在提高计算机编程技能和算法设计能力的竞赛活动。
对于初学者来说，入门经典代码是学习算法竞赛的重要一步。
下面是一些常见的入门经典代码。
【排序算法】在算法竞赛中，排序算法是最基础且重要的算法之一、常见的排序算法有冒泡排序、选择排序、插入排序、归并排序和快速排序等。
冒泡排序的代码如下：```cppvoid bubbleSort(int arr[], int n)for (int i = 0; i < n-1; i++)for (int j = 0; j < n-i-1; j++)if (arr[j] > arr[j+1])swap(arr[j], arr[j+1]);}}}```【查找算法】查找算法是另一个常见的算法问题。
常见的查找算法有线性查找和二分查找。
线性查找的代码如下：```cppint linearSearch(int arr[], int n, int key)for (int i = 0; i < n; i++)if (arr[i] == key)return i;}}return -1;```二分查找的代码如下：```cppint binarySearch(int arr[], int low, int high, int key)if (high >= low)int mid = low + (high - low) / 2;if (arr[mid] == key)return mid;if (arr[mid] > key)return binarySearch(arr, low, mid - 1, key);}return binarySearch(arr, mid + 1, high, key);}return -1;```【动态规划】动态规划是一种常用的解决最优化问题的算法，针对具有重叠子问题和最优子结构性质的问题进行求解。
优先级排序算法1. 优先级排序算法，听起来好高大上啊！其实呢，它就像是我们生活中的"任务管家"，帮我们决定先做什么后做什么。
想象一下，你的作业、游戏时间、社交活动都在排队等你处理，这个算法就是来帮你安排这个队伍的！2. 最简单的优先级排序算法就是冒泡排序啦！它就像是在水里冒泡泡，大泡泡（高优先级的任务）会慢慢浮到顶部。
比如说，你有一堆作业：[数学, 语文, 英语, 体育]。
经过冒泡排序后，可能变成：[数学, 英语, 语文, 体育]。
数学作业像个大泡泡，"噗通"一下就浮到最前面啦！3. 接下来是选择排序，它就像是挑西瓜，每次都挑最大的（最重要的）拿出来。
想象你的待办事项是：[看电影, 写作业, 打游戏, 读书]。
用选择排序后可能变成：[写作业, 读书, 看电影, 打游戏]。
每次都选最重要的事儿放前面，简单吧？4. 插入排序就像是在整理扑克牌，你拿到一张新牌，就把它插到合适的位置。
比如你的日程安排是：[吃早餐, 上班, 开会]。
突然插入一个"紧急电话"，经过插入排序可能变成：[紧急电话, 吃早餐, 上班, 开会]。
5. 快速排序是个小机灵鬼，它选一个"基准"，然后把其他任务分成两组：比基准重要的和不重要的。
假设你的任务列表是：[看电影, 遛狗, 写报告, 健身, 购物]。
选"写报告"作为基准，可能最后变成：[写报告, 健身, 遛狗, 看电影, 购物]。
6. 堆排序就像是在玩"国王游戏"，最大的（最重要的）总是在顶部。
想象你的待办事项是一个金字塔，最重要的事在塔尖。
每次你完成塔尖的任务，下面的任务就会争先恐后地往上爬，最重要的又会到塔尖。
7. 归并排序有点像是"分而治之"的战术。
把大问题分成小问题，解决完再合并。
比如你要安排一周的计划，可以先分别安排工作日和周末，然后再把它们合并成一个完整的周计划。
统治世界⼗⼤数学算法列表软件正在统治世界，⽽软件的核⼼是算法；互联⽹即将统治世界，其管理、使⽤的核⼼也是算法；算法统治着软件和互联⽹，所以说“算法统治世界”这句话应是有⼀定道理的，⽽所有算法的底层是数学原理。
什么是算法？直⽩地说，算法就是任何明确定义的计算过程，它接收⼀些值或集合作为输⼊，并产⽣⼀些值或集合作为输出。
这样，算法就是将输⼊转换为输出的⼀系列计算过程。
简⽽⾔之，我们可以说算法就是⽤来解决⼀个特定任务的⼀系列步骤（是的，不⽌计算机在使⽤算法，⼈类也同样如此）。
⽬前，⼀个有效的算法应该含有三个重要特性：它必须是有限的：如果你设计的算法永⽆休⽌地尝试解决问题，那么它是⽆⽤的。
1. 它必须是有限的它必须具备明确定义的指令：算法的每⼀步都必须准确定义，在任何场景下指令都应当没有2. 它必须具备明确定义的指令歧义。
它必须是有效的：⼀个算法被设计⽤以解决某个问题，那么它就应当能解决这个问题，并且3. 它必须是有效的仅仅使⽤纸和笔就能证明该算法是收敛的。
还有⼀个要点需要指出，算法不仅仅在计算机科学中使⽤，同时也存在于数学领域中。
事实上，⾸个被记载的数学算法要追溯到公元前1600年，古巴⽐伦⼈开发了已知最早的算法，⽤作因式分解和计算平⽅根。
这⾥，我们回答了前⾯所提到的那篇⽂章中的第⼀个问题，它认为算法是计算机范畴的实体，但如果你知晓算法这个词的真正内涵的话，真正统治世界的⼗⼤算法也能在数学书籍中找到（加法、减法、乘积等等）。
不过在这篇⽂章中，让我们将算法的定义限定在计算机算法上，所以剩下的问题是：哪⼗个算法统治了世界？在此我整理了⼀个⼩型列表，排名不分先后。
1.归并排序，快速排序和堆排序哪个排序算法最好？这取决于你的需求，这也是为什么我要将这三个使⽤频率较⾼的排序算法置于⼀处的原因。
可能你⽐较偏爱其中⼀个，但它们都是同等重要的。
归并排序算法是⽬前为⽌我们拥有的最重要的算法之⼀。
它是⼀种基于⽐较的排序算法，使⽤分治法解决那些原本复杂度为O(N^2)的问题。
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
冒泡法：这是最原始，也是众所周知的最慢的算法了。
他的名字的由来因为它的工作看来象是冒泡：复杂度为O(n*n)。
当数据为正序，将不会有交换。
复杂度为O(0)。
直接插入排序：O(n*n)选择排序：O(n*n)快速排序：平均时间复杂度log2(n)*n，所有内部排序方法中最高好的，大多数情况下总是最好的。
归并排序：l og2(n)*n堆排序：l og2(n)*n希尔排序：算法的复杂度为n的1.2次幂这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况1.数组的大小是2的幂，这样分下去始终可以被2整除。
假设为2的k次方，即k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2)......所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n所以算法复杂度为O(lo g2(n)*n) 其他的情况只会比这种情况差，最差的情况是每次选择到的midd le都是最小值或最大值，那么他将变成交换法（由于使用了递归，情况更糟）。
但是你认为这种情况发生的几率有多大？？呵呵，你完全不必担心这个问题。
实践证明，大多数的情况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。
「⼲货」编程语⾔⼗⼤经典算法，你知道⼏个？算法与数据结构是计算机学习路上的内功⼼法，也是学好编程语⾔的重要基础。
今天给⼤家介绍⼀下⼗⼤经典算法。
⼗⼤经典算法分别是：冒泡排序，插⼊排序，选择排序，希尔排序，快速排序，归并排序，桶排序，堆排序，计数排序，基数排序。
预备知识：算法稳定性如果a==b，排序前a在b的前⾯，排序后a在b的后⾯，只要会出现这种现象，我们则说这个算法不稳定（即使两个相等的数，在排序的过程中不断交换，有可能将后⾯的b交换到a的前⾯去）。
⼀、冒泡排序冒泡排序（Bubble Sort）是基于交换的排序，它重复⾛过需要排序的元素，依次⽐较相邻的两个元素的⼤⼩，保证最后⼀个数字⼀定是最⼤的，即它的顺序已经排好，下⼀轮只需要保证前⾯n-1个元素的顺序即可。
之所以称为冒泡，是因为最⼤/最⼩的数，每⼀次都往后⾯冒，就像是⽔⾥⾯的⽓泡⼀样。
排序的步骤如下：1. 从头开始，⽐较相邻的两个数，如果第⼀个数⽐第⼆个数⼤，那么就交换它们位置。
2. 从开始到最后⼀对⽐较完成，⼀轮结束后，最后⼀个元素的位置已经确定。
3. 除了最后⼀个元素以外，前⾯的所有未排好序的元素重复前⾯两个步骤。
4. 重复前⾯ 1 ～ 3 步骤，直到都已经排好序。
例如，我们需要对数组[98，90，34，56，21]进⾏从⼩到⼤排序，每⼀次都需要将数组最⼤的移动到数组尾部。
那么排序的过程如下动图所⽰：⼆、选择排序前⾯说的冒泡排序是每⼀轮⽐较确定最后⼀个元素，中间过程不断地交换。
⽽选择排序就是每次选择剩下的元素中最⼩的那个元素，直到选择完成。
排序的步骤如下：从第⼀个元素开始，遍历其后⾯的元素，找出其后⾯⽐它更⼩的元素，若有，则两者交换，保证第⼀个元素最⼩。
对第⼆个元素⼀样，遍历其后⾯的元素，找出其后⾯⽐它更⼩的元素，若存在，则两者交换，保证第⼆个元素在未排序的数中（除了第⼀个元素）最⼩。
依次类推，直到最后⼀个元素，那么数组就已经排好序了。
经典⼗⼤排序算法前⾔排序种类繁多，⼤致可以分为两⼤类：⽐较类排序：属于⾮线性时间排序，时间复杂度不能突破下界O(nlogn);⾮⽐较类排序：能达到线性时间O(n)，不是通过⽐较来排序，有基数排序、计数排序、桶排序。
了解⼀个概念：排序的稳定性稳定是指相同⼤⼩的元素多次排序能保证其先后顺序保持不变。
假设有⼀些学⽣的信息，我们先根据他们的姓名进⾏排序，然后我们还想根据班级再进⾏排序，如果这时使⽤的时不稳定的排序算法，那么第⼀次的排序结果可能会被打乱，这样的场景需要使⽤稳定的算法。
堆排序、快速排序、希尔排序、选择排序是不稳定的排序算法，⽽冒泡排序、插⼊排序、归并排序、基数排序是稳定的排序算法。
1、冒泡排序⼤多数⼈学编程接触的第⼀种排序，名称很形象。
每次遍历排出⼀个最⼤的元素，将⼀个最⼤的⽓泡冒出⽔⾯。
时间复杂度：平均：O(n2)；最好：O(n)；最坏：O(n2)空间复杂度：O(1)public static void bubbleSort(int[] arr) {/*** 总共⾛len-1趟即可，每趟排出⼀个最⼤值放在最后*/for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {int tp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tp;}}}}2、选择排序最直观易理解的排序算法，每次排出⼀个最⼩的元素。
也是最稳定的算法，时间复杂度稳定为O(n^2)。
需要⼀个变量记录每次遍历最⼩元素的位置。
时间复杂度：O(n2)空间复杂度：O(1)public static void selectSort(int[] arr){int n = arr.length;for (int i = 0; i < n; i++) {int maxIdx = 0;for(int j = 1; j < n - i; j++){if(arr[maxIdx] < arr[j]){maxIdx = j;}}int tp = arr[maxIdx];arr[maxIdx] = arr[n - 1 - i];arr[n - 1 - i] = tp;}}3、插⼊排序⼀种直观的排序算法，从第⼆个元素开始，每次往前⾯遍历找到⾃⼰该在的位置。
【十大经典排序算法（动图演示）】必学十大经典排序算法0.1 算法分类十种常见排序算法可以分为两大类：比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
0.2 算法复杂度0.3 相关概念稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后a 可能会出现在b 的后面。
时间复杂度：对排序数据的总的操作次数。
反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
1、冒泡排序（Bubble Sort）冒泡排序是一种简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.1 算法描述比较相邻的元素。
如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。
1.2 动图演示1.3 代码实现1.unction bubbleSort(arr) {2. varlen = arr.length;3. for(vari = 0; i arr[j+1]) {// 相邻元素两两对比6. vartemp = arr[j+1];// 元素交换7. arr[j+1] = arr[j];8. arr[j] = temp;9. }10. }11. }12. returnarr;13.}2、选择排序（Selection Sort）选择排序(Selection-sort)是一种简单直观的排序算法。
它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
2.1 算法描述n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。
具体算法描述如下：初始状态：无序区为R[1..n]，有序区为空；第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。
该趟排序从当前无序区中-选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化了。
2.2 动图演示代码实现function selectionSort(arr) {varlen = arr.length;varminIndex, temp;for(vari = 0; i 2.4 算法分析表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。
唯一的好处可能就是不占用额外的内存空间了吧。
理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
3、插入排序（Insertion Sort）插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
3.1 算法描述一般来说，插入排序都采用in-place在数组上实现。
具体算法描述如下：从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5。
3.2 代码实现function insertionSort(arr) {varlen = arr.length;varpreIndex, current;for(vari = 1; i = 0 && arr[preIndex] > current) {arr[preIndex + 1] = arr[preIndex];preIndex--;}arr[preIndex + 1] = current;}returnarr;}3.4 算法分析插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
4、希尔排序（Shell Sort）1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。
它与插入排序的不同之处在于，它会优先比较距离较远的元素。
希尔排序又叫缩小增量排序。
4.1 算法描述先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k 趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4.2 动图演示4.3 代码实现function shellSort(arr) {varlen = arr.length;for(vargap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {// 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行for(vari = gap; i = 0 && current 4.4 算法分析希尔排序的核心在于间隔序列的设定。
既可以提前设定好间隔序列，也可以动态的定义间隔序列。
动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。
5、归并排序（Merge Sort）归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为2-路归并。
5.1 算法描述把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。
5.2 动图演示5.3 代码实现function mergeSort(arr) {varlen = arr.length;if(len 0 && right.length>0) {if(left[0]5.4 算法分析归并排序是一种稳定的排序方法。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。
代价是需要额外的内存空间。
6、快速排序（Quick Sort）快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
6.1 算法描述快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。
具体算法描述如下：从数列中挑出一个元素，称为“基准”（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
在这个分区退出之后，该基准就处于数列的中间位置。
这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
6.2 动图演示6.3 代码实现function quickSort(arr, left, right) {varlen = arr.length,partitionIndex,left =typeofleft !='number'? 0 : left,right =typeofright !='number'? len - 1 : right;if(left 7、堆排序（Heap Sort）堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
7.1 算法描述将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
7.2 动图演示7.3 代码实现varlen;// 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量function buildMaxHeap(arr) {// 建立大顶堆len = arr.length;for(vari = Math.floor(len/2); i >= 0; i--) {heapify(arr, i);}}function heapify(arr, i) {// 堆调整varleft = 2 * i + 1,right = 2 * i + 2,largest = i;if(left arr[largest]) {largest = left;}if(right arr[largest]) {largest = right;}if(largest != i) {swap(arr, i, largest);heapify(arr, largest);}}function swap(arr, i, j) {vartemp = arr[i];arr[i] = arr[j];arr[j] = temp;}function heapSort(arr) {buildMaxHeap(arr);for(vari = arr.length - 1; i > 0; i--) {swap(arr, 0, i);len--;heapify(arr, 0);}returnarr;}8、计数排序（Counting Sort）计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
