排序

<article class=“article fmt article-content”><h2>抉择排序</h2><h4>目录</h4><ul><li>1.算法思维</li><li>2.从[算法思维]到[代码实现]</li><li>3.代码实现(C、Python)</li></ul><h3>1. 算法思维</h3><blockquote>抉择排序：每一轮抉择出 <code>以后未排序区间中最小的元素</code>放到 <code>对应的地位</code>上</blockquote><p>排序过程：</p><p>数组a有n个元素</p><ul><li>第一轮：a[0]-a[n-1]为待排序区间，在此区间中选出最小的元素放在a[0]上；</li><li>第二轮：a[1]-a[n-1]是新的待排序区间，在此区间中选出最小的元素放到a[1]上；</li><li><p>第三轮：a[2]-a[n-1]是新的待排序区间，在此区间中选出最小的元素放到a[2]上；</p><p>….</p></li><li>第 n-1 轮：通过下面的排序，从a[0]-a[n-2]顺次放入了最小、次小..的元素，a[0]-a[n-2]为有序区间，此时待排序区间只剩下一个元素即最初一个元素，无需再进行排序，整个数组排序结束。</li></ul><h3>2.从“算法思维”到“代码实现”</h3><p>察看上述算法中的排序过程</p><ol><li>共须要n-1轮排序，每一轮排序外部的操作都一样，因而能够用for循环来实现每一轮排序。循环变量 i 的取值范畴为[0,n-1]</li><li>在每一轮排序外部为了最终找出剩下区间中最小的元素，须要遍历整个剩下的区间。因而每一轮排序外部也有一个for循环。循环变量 j 的取值范畴为[i+1,n-1]</li></ol><p>综上所述，算法能够应用2层for循环来实现</p><ul><li>外层的循环次数是排序轮次，有n个元素，则循环n-1次；这个for循环实现每一轮排序</li><li><p>内层for循环实现在每一轮排序外部找出剩下区间中的最小元素</p><p>双层for循环示意图：<br/><br/></p></li></ul><h3>3. 代码实现(C、Python)</h3><p>C语言实现</p><pre><code>//替换2个变量的值void Swap(int *a,int *b){ int temp = *a; *a =*b; *b = temp;}//抉择排序void SelectionSort(int *arr, int n) { //从数组起始地位开始，i初始化为0; for (int i = 0; i < n - 1; i++) { // 假如以后地位为最小元素 int min_index = i; //遍历待排序区间[i+1 - n-1]，如果存在更小的元素则更新min_index for (int j = i + 1; j < n; ++j) { if (arr[min_index] > arr[j]) { //循环查找最小值 min_index = j; } } //查看min_index是否被更新过，是则将最小元素替换到地位i if(min_index!=i) { //应用替换，防止笼罩掉原先地位的元素 Swap(&arr[i], &arr[min_index]); } }}</code></pre><p>Python实现</p><pre><code>def SelectSort(arr): length = len(arr) for i in range(0,length-1): min_tmp=i for j in range(i+1,length): if arr[j]<arr[min_tmp]: min_tmp=j if min_tmp!=i: arr[i],arr[min_tmp] = arr[min_tmp],arr[i] </code></pre></article> ...

随着美团零售商品类业务的一直倒退，美团搜寻在多业务商品排序场景上面临着诸多的挑战。本文介绍了美团搜寻在商品多业务排序上相干的摸索以及实际，心愿能对从事相干工作的同学有所帮忙或者启发。 参考资料[1] 多业务建模在美团搜寻排序中的实际[2] Ma X, Zhao L, Huang G, et al. Entire space multi-task model: An effective approach for estimating post-click conversion rate[C]//The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval. 2018: 1137-1140.[3] Friedman et al., A note on the group lasso and a sparse group lasso.[4] Kendall et al., Multi-Task Learning Using Uncertainty to Weigh Losses for Scene Geometry and Semantics. In CVPR, 2018.[5] Guo et al., Dynamic Task Prioritization for Multitask Learning. In ECCV, 2018.[6] Sheng et al., One Model to Serve All: Star Topology Adaptive Recommender for Multi-Domain CTR Prediction. In CIKM, 2021.[7] Zhou G, Zhu X, Song C, et al. Deep interest network for click-through rate prediction[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2018: 1059-1068.[8] Zhou G, Mou N, Fan Y, et al. Deep interest evolution network for click-through rate prediction[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2019, 33: 5941-5948.[9] Feng Y, Lv F, Shen W, et al. Deep Session Interest Network for Click-Through Rate Prediction[J]. arXiv preprint arXiv:1905.06482, 2019.[10] Chen Q, Zhao H, Li W, et al. Behavior sequence transformer for e-commerce recommendation in Alibaba[C]//Proceedings of the 1st International Workshop on Deep Learning Practice for High-Dimensional Sparse Data. 2019: 1-4[11] Kan Ren, Jiarui Qin, Yuchen Fang, Weinan Zhang, Lei Zheng, Weijie Bian, Guorui Zhou, Jian Xu, Yong Yu, Xiaoqiang Zhu, et al. Lifelong sequential modeling with personalized memorization for user response prediction. In SIGIR, 2019.[12] Qi Pi, Weijie Bian, Guorui Zhou, Xiaoqiang Zhu, and Kun Gai. Practice on long sequential user behavior modeling for click-through rate prediction. In KDD, 2019.[13] Jiarui Qin, W. Zhang, Xin Wu, Jiarui Jin, Yuchen Fang, and Y. Yu. User behavior retrieval for click-through rate prediction. In SIGIR, 2020.[14] Search-based User Interest Modeling with Lifelong Sequential Behavior Data for Click-Through Rate Prediction.[15] Transformer 在美团搜寻排序中的实际[16] Ma J, Zhao Z, Yi X, et al. Modeling task relationships in multi-task learning with multi-gate mixture-of-experts[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 1930-1939.[17] Xi D, Chen Z, Yan P, et al. Modeling the Sequential Dependence among Audience Multi-step Conversions with Multi-task Learning in Targeted Display Advertising[J]. arXiv preprint arXiv:2105.08489, 2021.[18] Burges C J C. From ranknet to lambdarank to lambdamart: An overview[J]. Learning, 2010, 11(23-581): 81.[19] https://en.wikipedia.org/wiki...[20] Liu et al., AutoFIS: Automatic Feature Interaction Selection in Factorization Models for Click-Through Rate Prediction, In ADS-KDD, 2020.[21] Khawar et al., AutoFeature: Searching for Feature Interactions and Their Architectures for Click-through Rate Prediction, In CIKM, 2020.[22] Tang et al., Progressive Layered Extraction (PLE): A Novel Multi-Task Learning (MTL) Model for Personalized Recommendations, In Recsys, 2020.作者简介曹越、瑶鹏、诗晓、李想、家琪、可依、晓江、肖垚、培浩、达遥、陈胜、云森、利前均来自美团平台搜寻与 NLP 部。 ...

一、参考数据结构与算法 学习系列目录——更新ing 排序（上）：为什么插入排序比冒泡排序更受欢迎？ 二、如何剖析一个排序算法？

长度为N的数组记录中1-N个数字将数组中的数从小到大排序不能够间接赋值let arr = [1, 6, 3, 2, 9, 10, 11, 4, 7, 5, 12, 8]; let i = 0, temp = 0;while(temp++ < arr.length) { if (arr[i] === i + 1) { i ++ } else { const temp = arr[arr[i] - 1]; arr[arr[i] - 1] = arr[i]; arr[i] = temp; }}

/* * 排序算法 */class Solution { public void swap(int[] arr, int i, int j) { int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } // 间接插入排序, O(n^2), 稳固 public void directInsert(int[] arr) { for (int i = 0; i < arr.length; i ++) { for (int j = 0; j < i; j ++) { if (arr[j] > arr[i]) { int temp = arr[i]; System.arraycopy(arr, j, arr, j + 1, i - j); arr[j] = temp; } } } } // 折半插入排序，O(nlogn)，稳固 public void binaryInsert(int[] arr) { for (int i = 0; i < arr.length; i ++) { int left = 0, right = i - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] < arr[i]) { left = mid + 1; } else { right = mid - 1; } } int temp = arr[i]; System.arraycopy(arr, left, arr, left + 1, i - left); arr[left] = temp; } } // 抉择排序， O(n^2)，不稳固 public void directSelect(int[] arr) { for (int i = 0; i < arr.length - 1; i ++) { for (int j = i + 1; j < arr.length; j ++) { if (arr[i] > arr[j]) { swap(arr, i, j); } } } } // 堆排序， O(nlogn)，不稳固，最大堆 public void heap(int[] arr) { for (int i = arr.length - 1; i >= 0; i --) { for (int j = i / 2 - 1; j >= 0; j --) { if (j * 2 + 1 == i && i % 2 == 1) { if (arr[j] < arr[j * 2 + 1]) { swap(arr, j, j * 2 + 1); } } else { if (arr[j] < arr[j * 2 + 1]) { swap(arr, j, j * 2 + 1); } if (arr[j] < arr[j * 2 + 2]) { swap(arr, j, j * 2 + 2); } } } swap(arr, 0, i); } } // 冒泡排序，O(n^2), 稳固 public void bubble(int[] arr) { for (int i = arr.length - 1; i >= 0; i --) { for (int j = 0; j < i; j ++) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); } } } } // 快排，O(nlogn)，不稳固 public void quick(int[] arr) { quickSort(arr, 0, arr.length - 1); } private void quickSort(int[] arr, int left, int right) { if (arr == null || left >= right || arr.length <= 1) { return; } int mid = partition(arr, left, right); quickSort(arr, left, mid); quickSort(arr, mid + 1, right); } private int partition(int[] arr, int left, int right) { int temp = arr[left]; while (left < right) { while (left < right && temp <= arr[right]) { right --; } if (left < right) { arr[left] = arr[right]; left ++; } while (left < right && temp >= arr[left]) { left ++; } if (left < right) { arr[right] = arr[left]; right --; } } arr[left] = temp; return left; } // 归并排序， O(nlogn)， 稳固 public void mergeSort(int[] arr) { sort(arr, 0, arr.length - 1); } private void sort(int[] arr, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; sort(arr, left, mid); sort(arr, mid + 1, right); merge(arr, left, mid, right); } } private void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, index = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[index ++] = arr[i ++]; } else { temp[index ++] = arr[j ++]; } } while (i <= mid) { temp[index ++] = arr[i ++]; } while (j <= right) { temp[index ++] = arr[j ++]; } for (int k = 0; k < temp.length; k ++) { arr[left ++] = temp[k]; } }}

冒泡排序简介冒泡排序（Bubble Sort），是一种计算机科学畛域的较简略的排序算法。它反复地走访过要排序的元素列，顺次比拟两个相邻的元素，如果程序（如从大到小、首字母从Z到A）谬误就把他们替换过去。走访元素的工作是反复地进行直到没有相邻元素须要替换，也就是说该元素列曾经排序实现。这个算法的名字由来是因为越小的元素会经由替换缓缓“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。 算法原理将邻近的两个数字两两进行比拟，依照从小到大或者从大到小的程序进行替换。 算法原理示意图数组冒泡排序前↓↓↓ 冒泡排序执行过程[gif动图]↓↓↓ 数组冒泡排序后↓↓↓ 代码实现public class Sort { public static void main(String[] args) { int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; bubbleSort(arr); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] System.out.println(Arrays.toString(arr)); } /** * 冒泡排序 * @param arr 想要排序的数组 */ public static void bubbleSort(int[] arr){ //管制比拟轮数 for (int i = 0; i < arr.length; i++) { //每轮比拟多少次 for (int j = 0; j < arr.length - i -1; j++) { if (arr[j] > arr[j + 1]) { // temp为一个长期变量，为了存储替换时的长期值 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }}这里须要思考几个问题外层的循环起到什么作用/外层循环代表什么？外层循环中的 -1 是做什么的？内层的循环起到什么作用/内层循环代表什么？内层循环中的 -1 是做什么的？内层循环中的 -i 是做什么的？长期变量temp起到什么作用？首先须要了解的是冒泡排序是从头开始，两两比拟，将最大的数放到开端。而后再次从头开始，以此类推……。 ...

(PS：原博客戳这里。原博主写的太好了，所以间接转载过去。为了本人可能学习分明，我将代码局部删掉替换成本人写的代码，不便当前查看。) 0、算法概述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 代码实现 public static void bubbleSort(int[] 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 tmp = array[j + 1]; array[j + 1] = array[j]; array[j] = tmp; } } } }2、抉择排序（Selection Sort）抉择排序(Selection-sort)是一种简略直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，寄存到排序序列的起始地位，而后，再从残余未排序元素中持续寻找最小（大）元素，而后放到已排序序列的开端。以此类推，直到所有元素均排序结束。  ...

首发公众号：bigsai 转载请分割 文章已收录在 Github:bigsai-algorithm绪论身为程序员，十大排序是是所有合格程序员所必备和把握的，并且热门的算法比方快排、归并排序还可能问的比拟粗疏，对算法性能和复杂度的把握有要求。bigsai作为一个负责任的Java和数据结构与算法方向的小博主，在这方面必定不能让读者们有所破绽。跟着本篇走，带你捋一捋常见的十大排序算法，轻轻松松把握！ 首先对于排序来说大多数人对排序的概念停留在冒泡排序或者JDK中的Arrays.sort()，手写各种排序对很多人来说都是一种奢望，更别说十大排序算法了，不过还好你遇到了本篇文章！ 对于排序的分类，次要不同的维度比方复杂度来分、内外部、比拟非比拟等维度来分类。咱们失常讲的十大排序算法是外部排序，咱们更多将他们分为两大类：基于比拟和非比拟这个维度去分排序品种。 非比拟类的有桶排序、基数排序、计数排序。也有很多人将排序演绎为8大排序，那就是因为基数排序、计数排序是建设在桶排序之上或者是一种非凡的桶排序，然而基数排序和计数排序有它特有的特色，所以在这里就将他们演绎为10种经典排序算法。而比拟类排序也可分为比拟类排序也有更粗疏的分法，有基于替换的、基于插入的、基于抉择的、基于归并的，更粗疏的能够看上面的脑图。 替换类冒泡排序冒泡排序，又称起泡排序，它是一种基于替换的排序典型，也是快排思维的根底，冒泡排序是一种稳固排序算法，工夫复杂度为O(n^2).根本思维是：循环遍历屡次每次从前往后把大元素往后调，每次确定一个最大(最小)元素，屡次后达到排序序列。(或者从后向前把小元素往前调)。 具体思维为(把大元素往后调)： 从第一个元素开始往后遍历，每到一个地位判断是否比前面的元素大，如果比前面元素大，那么就替换两者大小，而后持续向后，这样的话进行一轮之后就能够保障最大的那个数被替换替换到最末的地位能够确定。第二次同样从开始起向后判断着后退，如果以后地位比前面一个地位更大的那么就和他前面的那个数替换。然而有点留神的是，这次并不需要判断到最初，只须要判断到倒数第二个地位就行(因为第一次咱们曾经确定最大的在倒数第一，这次的目标是确定倒数第二)同理，前面的遍历长度每次减一，直到第一个元素使得整个元素有序。例如2 5 3 1 4排序过程如下： 实现代码为： public void maopaosort(int[] a) { // TODO Auto-generated method stub for(int i=a.length-1;i>=0;i--) { for(int j=0;j<i;j++) { if(a[j]>a[j+1]) { int team=a[j]; a[j]=a[j+1]; a[j+1]=team; } } }}疾速排序疾速排序是对冒泡排序的一种改良，采纳递归分治的办法进行求解。而快排相比冒泡是一种不稳固排序,工夫复杂度最坏是O(n^2),均匀工夫复杂度为O(nlogn),最好状况的工夫复杂度为O(nlogn)。 对于快排来说，根本思维是这样的 快排须要将序列变成两个局部，就是序列右边全副小于一个数，序列右面全副大于一个数，而后利用递归的思维再将左序列当成一个残缺的序列再进行排序，同样把序列的右侧也当成一个残缺的序列进行排序。其中这个数在这个序列中是能够随机取的，能够取最右边，能够取最左边，当然也能够取随机数。然而通常不优化状况咱们取最右边的那个数。 实现代码为： public void quicksort(int [] a,int left,int right){ int low=left; int high=right; //上面两句的程序肯定不能混，否则会产生数组越界！！！very important！！！ if(low>high)//作为判断是否截止条件 return; int k=a[low];//额定空间k，取最左侧的一个作为掂量，最初要求左侧都比它小，右侧都比它大。 while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。 { while(low<high&&a[high]>=k)//右侧找到第一个小于k的进行 { high--; } //这样就找到第一个比它小的了 a[low]=a[high];//放到low地位 while(low<high&&a[low]<=k)//在low往右找到第一个大于k的，放到右侧a[high]地位 { low++; } a[high]=a[low]; } a[low]=k;//赋值而后左右递归分治求之 quicksort(a, left, low-1); quicksort(a, low+1, right); }插入类排序间接插入排序间接插入排序在所有排序算法中的是最简略排序形式之一。和咱们上学时候 从前往后、按高矮程序排序，那么一堆高下无序的人群中，从第一个开始，如果后面有比本人高的，就直接插入到适合的地位。始终到队伍的最初一个实现插入整个队列能力满足有序。 ...

一、插入排序插入排序算法是所有排序办法中最简略的一种算法，其次要的实现思维是将数据依照肯定的程序一个一个的插入到有序的表中，最终失去的序列就是曾经排序好的数据。 间接插入排序是插入排序算法中的一种，采纳的办法是：在增加新的记录时，应用程序查找的形式找到其要插入的地位，而后将新记录插入。 很多初学者所说的插入排序，实际上指的就是间接插入排序算法，插入排序算法还包含折半插入排序、2-路插入排序，表插入排序和希尔排序等，后序文章都会一一讲到。例如采纳间接插入排序算法将无序表{3,1,7,5,2,4,9,6}进行升序排序的过程为： 首先思考记录 3 ，因为插入排序刚开始，有序表中没有任何记录，所以 3 能够间接增加到有序表中，则有序表和无序表能够如图 1 所示： 图 1 间接插入排序（1） 向有序表中插入记录 1 时，同有序表中记录 3 进行比拟，1<3，所以插入到记录 3 的左侧，如图 2 所示： 图 2 间接插入排序（2） 向有序表插入记录 7 时，同有序表中记录 3 进行比拟，3<7，所以插入到记录 3 的右侧，如图 3 所示： 图 3 间接插入排序（3） 向有序表中插入记录 5 时，同有序表中记录 7 进行比拟，5<7，同时 5>3，所以插入到 3 和 7 两头，如图 4 所示： 图 4 间接插入排序（4） 向有序表插入记录 2 时，同有序表中记录 7进行比拟，2<7，再同 5，3，1别离进行比拟，最终确定 2 位于 1 和 3 两头，如图 5 所示： 图 5 间接插入排序（5） ...

原创公众号：bigsai前言在排序算法中，快排是占比十分多的一环，然而快排其思维始终被考查钻研，也有很多的优化计划。这里次要解说双轴快排的思维和实现。 首选，双轴快排也是一种快排的优化计划，在JDK的Arrays.sort()中被次要应用。所以，把握快排曾经不可能满足咱们的需要，咱们还要学会双轴快排的原理和实现才行。 回顾单轴快排单轴快排也就是咱们常说的一般疾速排序，对于疾速排序我想大家应该都很相熟：基于递归和分治的，工夫复杂度最坏而O(n2),最好和均匀状况为O(nlogn). 而快排的具体思路也很简略，每次在待排序序列中找一个数(通常最左侧多一点)，而后在这个序列中将比他小的放它左侧，比它大的放它右侧。 如果运气肯不好遇到O(n)平方的，那的确就很被啦： 实现起来也很容易，这里间接贴代码啦： private static void quicksort(int [] a,int left,int right){ int low=left; int high=right; //上面两句的程序肯定不能混，否则会产生数组越界！！！very important！！！ if(low>high)//作为判断是否截止条件 return; int k=a[low];//额定空间k，取最左侧的一个作为掂量，最初要求左侧都比它小，右侧都比它大。 while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。 { while(low<high&&a[high]>=k)//右侧找到第一个小于k的进行 { high--; } //这样就找到第一个比它小的了 a[low]=a[high];//放到low地位 while(low<high&&a[low]<=k)//在low往右找到第一个大于k的，放到右侧a[high]地位 { low++; } a[high]=a[low]; } a[low]=k;//赋值而后左右递归分治求之 quicksort(a, left, low-1); quicksort(a, low+1, right); }双轴快排剖析咱们明天的主题是双轴快排，双轴和单轴的区别你也能够晓得，多一个轴，后面讲了快排很多时候选最左侧元素以这个元素为轴将数据划分为两个区域，递归分治的去进行排序。但单轴很多时候可能会遇到较差的状况就是以后元素可能是最大的或者最小的，这样子元素就没有被划分区间，快排的递推T(n)=T(n-1)+O(n)从而为O(n2). 双轴就是选取两个主元素现实将区间划为3局部，这样不仅每次可能确定元素个数增多为2个，划分的区间由原来的两个变成三个，最坏最坏的状况就是左右同大小并且都是最大或者最小，但这样的概率相比一个最大或者最小还是低很多很多，所以双轴快排的优化力度还是挺大的。 总体状况剖析至于双轴快排具体是如何工作的呢？其实也不难理解，这里通过一系列图解说双轴快排的执行流程。 首先在初始的状况咱们是选取待排序区间内最左侧、最右侧的两个数值作为pivot1和pivot2 .作为两个轴的存在。同时咱们会提前解决数组最左侧和最右侧的数据会比拟将最小的放在左侧。所以pivot1<pivot2. 而以后这一轮的最终目标是，比privot1小的在privot1左侧，比privot2大的在privot2右侧，在privot1和privot2之间的在两头。 这样进行一次后递归的进行下一次双轴快排，始终到完结，然而在这个执行过程应该去如何解决剖析呢？须要几个参数呢？ 假如晓得排序区间[start，end]。数组为arr， pivot1=arr[start],pivot2=arr[end]还须要三个参数left，right和k。 lleft初始为start，[start,left]区域即为小于等于pivot1小的区域(第一个等于)。right与left对应，初始为end，[right,end]为大于等于pivot2的区域(最初一个等于)。k初始为start+1，是一个从左往右遍历的指针，遍历的数值与pivot1，pivot2比拟进行适当替换，当k>=right即可进行。 k替换过程而后你可能会问k遍历时候到底怎么去替换？left和right该如何解决呢？不急我带你缓缓剖析，首先K是在left和right两头的，遍历k的地位和pivot1，pivot2进行比拟： 如果arr[k]<pivot1,那么先++left，而后swap(arr,k,left),因为初始在start在这个过程不完结start先不动。而后k++；持续进行 而如果arr[k]>pivot2.(区间自行安排即可)有点区别的就是right可能间断的大于arr[k],比方9 3 3 9 7如果咱们须要跳过7后面9到3能力失常替换，这和快排的替换思维统一，当然再具体的实现上就是right--到一个适合比arr[k]小的地位。而后swap(arr,k,right)切记此时k不能自加。因为带替换的那个有可能比pivot1还小要和left替换。 ...

一、算法的分类1、概念 将横七竖八的数据元素，通过肯定的办法按关键字顺序排列的过程叫做排序。 2、分类 非线性工夫比拟类排序：通过比拟来决定元素间的绝对秩序，因为其工夫复杂度不能冲破O(nlogn)，因而称为非线性工夫比拟类排序。 线性工夫非比拟类排序：不通过比拟来决定元素间的绝对秩序，它能够冲破基于比拟排序的工夫下界，以线性工夫运行，因而称为线性工夫非比拟类排序。 3、比拟 阐明： 稳固：如果a本来在b后面，而a=b，排序之后a依然在b的后面； 不稳固：如果a本来在b的后面，而a=b，排序之后a可能会呈现在b的前面； 内排序：所有排序操作都在内存中实现； 外排序：因为数据太大，因而把数据放在磁盘中，而排序通过磁盘和内存的数据传输能力进行； 二、各算法原理及实现1、冒泡排序（Bubble Sort） ①根本思维：两个数比拟大小，较大的数下沉，较小的数冒起来。 ②算法形容： 比拟相邻的元素。如果第一个比第二个大，就替换它们两个； 对每一对相邻元素作同样的工作，从开始第一对到结尾的最初一对，这样在最初的元素应该会是最大的数； 针对所有的元素反复以上的步骤，除了最初一个； 反复步骤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;}2、抉择排序（Selection Sort） ...

冒泡排序思维根本思维: 冒泡排序，相似于水中冒泡，较大的数沉下去，较小的数缓缓冒起来，假如从小到大，即为较大的数缓缓往后排，较小的数缓缓往前排。直观表白，每一趟遍历，将一个最大的数移到序列开端。 算法形容比拟相邻的元素，如果前一个比后一个大，替换之。第一趟排序第1个和第2个一对，比拟与替换，随后第2个和第3个一对比拟替换，这样直到倒数第2个和最初1个，将最大的数挪动到最初一位。第二趟将第二大的数挪动至倒数第二位因而须要n-1趟；代码实现(js)function bubbleSort(nums) { let length = nums.length; for (let i = 0;i < length - 1;i++) { console.log('第', i + 1, '趟'); for (let j = 0;j < length - 1 - i;j++) { if (nums[j] > nums[j + 1]) { let a = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = a; } console.log(nums); } }};bubbleSort([90, 89, 78, 67, 56, 45, 34, 23, 12]); ...

public class InsertSort{ public static void main(String[] args) { int[] array = {34,8,64,51,32,21}; int[] a = insertionSort(array); for (int i = 0; i < a.length; i++) { System.out.println(a[i]); } } public static int[] insertionSort(int[] array){ for (int i = 1; i < array.length; i++) { int tmp = array[i]; for (int j = i; j>0 && tmp <array[j-1];j--){ array[j] = array[j-1]; array[j-1] = tmp; } } return array; }}以后元素tmp之前是曾经排好序，那么将以后元素和后面元素一个一个地去比拟，如果但钱元素更小，阐明该元素应该放到后面，也就是说须要替换这两个元素的地位。而后循环执行，直到tmp元素的值比后面的元素要大。这时候，后面的元素就是有序的了。 ...

冒泡排序（Bubble Sort）1.什么是冒泡排序冒泡排序须要反复地走访过要排序的元素列，顺次比拟两个相邻的元素，如果程序（如从大到小、首字母从Z到A）谬误就把他们替换过去。走访元素的工作是反复地进行直到没有相邻元素须要替换，也就是说该元素列曾经排序实现。工夫复杂度为O（n²） 2.算法步骤比拟相邻的元素。如果第一个比第二个大，就替换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最初一对。这步做完后，最初的元素会是最大的数。 针对所有的元素反复以上的步骤，除了最初一个。 3.动图演示 4.代码演示 public static void main(String[] args) { //初始化数组 int[] arr = {3,1,2,5,4}; for (int i = 1; i < arr.length; i++) { //设置标记位 boolean flag = true; for (int j = 0; j < arr.length - i; j++) { //如果以后值比下一个值大，则替换单方地位 if(arr[j] > arr[j + 1]){ int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1]= temp; flag =false; } } //如果一次替换都没有，则阐明曾经有序，无需持续循环 if(flag) { break; } } System.out.println(Arrays.toString(arr)); }5.输入后果[1, 2, 3, 4, 5]

明天的知识点 (2020.08.15) —— 第487天 (我也要出题)[html] html元素哪些标签是不可替换元素？哪些是可替换元素？[css] 应用display: table-cell有什么利用场景呢？[js] 写一个办法对对象中的key进行排序[软技能] 有ios和android两个下载链接，如何把它们合并成一个二维码？《论语》，曾子曰：“吾日三省吾身”（我每天屡次检查本人）。前端面试每日3+1题，以面试题来驱动学习，每天提高一点！让致力成为一种习惯，让奋斗成为一种享受！置信 保持 的力量！！！欢送在 Issues 和敌人们一起探讨学习！ 我的项目地址：前端面试每日3+1【举荐】欢送跟 jsliang 一起折腾前端，零碎整顿前端常识，目前正在折腾 LeetCode，打算买通算法与数据结构的任督二脉。GitHub 地址 微信公众号欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个Star, 同时欢送微信扫码关注 前端剑解 公众号，并退出 “前端学习每日3+1” 微信群互相交换（点击公众号的菜单：交换）。 学习不打烊，充电加油只为遇到更好的本人，365天无节假日，每天早上5点纯手工公布面试题（死磕本人，愉悦大家）。心愿大家在这虚夸的前端圈里，放弃沉着，保持每天花20分钟来学习与思考。在这变幻无穷，类库层出不穷的前端，倡议大家不要等到找工作时，才狂刷题，提倡每日学习！（不忘初心，html、css、javascript才是基石！）欢送大家到Issues交换，激励PR，感激Star，大家有啥好的倡议能够加我微信一起交换探讨！心愿大家每日去学习与思考，这才达到来这里的目标！！！（不要为了谁而来，要为本人而来！）交换探讨欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个[Star]

前言在数据结构与算法的排序中，咱们很多人可能更多的相熟冒泡排序、疾速排序、归并排序。可能对堆排序、桶排序、计数排数等比拟陌生，其实这个也没啥简单的，算法的排序中，咱们很多人可能更多的相熟冒泡排序、疾速排序、归并排序。可能对堆排序、桶排序、计数排数等比拟陌生，其实这个也没啥简单的，桶排序是所有排序中最简略的排序之一。 没故障老铁，就是最简略的之一。 并且桶排序和计数排序，基数排序有很多类似和渊源之处。前面会进行比照剖析记得先关注！ 桶排序思维其实桶排序重要的是它的思维，而不是具体实现，桶排序从字面的意思上看： 桶：若干个桶，阐明此类排序将数据放入若干个桶中。桶：每个桶有容量，桶是有肯定容积的容器，所以每个桶中可能有多个元素。桶：从整体来看，整个排序更心愿桶可能更匀称，即既不溢出(太多)又不太少。 然而这些桶跟排序又有什么关系呢？首先先说下桶排序的思维，百度百科是这么说的 工作的原理是将数组分到无限数量的桶子里。每个桶子再个别排序（有可能再应用别的排序算法或是以递归形式持续应用桶排序进行排序）。桶排序是鸽巢排序的一种演绎后果。当要被排序的数组内的数值是平均调配的时候，桶排序应用线性工夫（（n））。但桶排序并不是 比拟排序，他不受到 O(n log n) 上限的影响。用通俗易懂的话来了解： 将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。工夫复杂度最好可能是线性O(n)，桶排序不是基于比拟的排序当然，桶排序是一种用空间换取工夫的排序。 既然是排序，那么最终的后果必定是从小到大的，桶排序借助桶的地位实现一次初步的排序——将待排序元素别离放至各个桶内。 而咱们通常依据待排序元素整除的办法将其较为平均的放至桶中，如8 5 22 15 28 9 45 42 39 19 27 47 12这个待排序序列，假如放入桶编号的规定为：n/10。这样首先各个元素就能够间接通过整除的办法放至对应桶中。而右侧所有桶内数据都比左侧的要大！ 在刚刚放入桶中的时候，各个桶的大小绝对能够确定，右侧都比左侧大，但桶内还是无序的，对各个桶内别离进行排序，再顺次依照桶的程序、桶内序列程序失去一个最终排序的序列。 以上就是桶排序在算法上的思维了。如果应用java具体实现的话思路也很简略：用List[]类型的汇合数组示意桶，每个List代表一个桶，将数据依据整除失去的值间接放到对应编号的汇合外面去，再顺次进行排序就能够了。 桶排序算法剖析下面讲了桶排序的具体思维，然而你是不是总感觉心理没那么虚浮呢，这就完了？总感觉怪怪的是吧？ 桶排序的确有很多不一样的中央，无论是算法工夫复杂度还是整个算法的流程，都不如啥快排啦、归并啦这些传统排序来的切实。 工夫复杂度剖析桶排序的工夫复杂度到底是多少？ 咱们假如有n个待排序数字。分到m个桶中，如果调配平均这样均匀每个桶有n/m个元素。首先在这里我郑重阐明一下桶排序的算法工夫复杂度有两局部组成： 1.遍历解决每个元素，O(n)级别的一般遍历2.每个桶内再次排序的工夫复杂度总和对于第一个局部，我想大家都应该了解最初排好序的取值遍历一趟的O(n);而第二局部咱们能够进行这样的剖析： 如果桶内元素调配较为平均假如每个桶外部应用的排序算法为疾速排序，那么每个桶内的工夫复杂度为(n/m) log(n/m)。有m个桶，那么工夫复杂度为m * (n/m)log(n/m)=n (log n-log m).所以最终桶排序的工夫复杂度为：O(n)+O(n*(log n- log m))=O(n+n*(log n -log m)) 其中m为桶的个数。咱们有时也会写成O(n+c),其中c=n*(log n -log m); 在这里如果达到极限状况n=m时。就能确保防止桶内排序，将数值放到桶中不须要再排序达到O(n)的排序成果,当然这种状况属于计数排序，前面再详解计数排序记得再回顾。 桶排序实用状况桶排序并且像惯例排序那样没有限度，桶排序有相当的限度。因为桶的个数和大小都是咱们人为设置的。而每个桶又要防止空桶的状况。所以咱们在应用桶排序的时候即须要对待排序数列要求偏平均，又要要求桶的设计兼顾效率和空间。 待排序序列要求平均？我要不平均又会怎么样呢？会这样：这样其实相当于只用了无效的很少个数桶，而再看桶排序的工夫复杂度：O(n+n*(log n -log m))m取向1，log m去向0.整个复杂度变成O(n+nlogn)从级别来看就是O(nlogn)，你瞅瞅你瞅瞅，这种状况就跟没用桶一样，就是快排(或其余排序)的工夫复杂度。 那，那不能我搞100000个桶嘛？不能够，真的不能够，如果100000个桶，你看看会造成什么状况：这才短短不到100个数，你为了一一映射用100000个空间，空间内容节约不说，你遍历尽管O(n)也是100000次也比100个的O(nlogn)大上很多啊，真是折了夫人又折兵。 所以当初明确后面说的话了吧：数要绝对均匀分布，桶的个数也要正当设计。总之桶排序是一种用空间换取工夫的排序。在设计桶排序，你须要晓得输出数据的上界和下界，看看数据的散布状况，再思考是否用桶排序，当然如果能用好桶排序，效率还是很高的！ 实现一个桶排序在这里用java给大家实现一个桶排序。假如序列为：1 8 7 44 42 46 38 34 33 17 15 16 27 28 24；咱们选用5个桶进行桶排序。 ...

[toc] 前言声明：参考来源互联网，有任何争议可以留言。站在前人的肩上，我们才能看的更远。本教程纯手打，致力于最实用教程，不需要什么奖励，只希望多多转发支持。欢迎来我公众号，希望可以结识你，也可以催更，微信搜索：JavaPub 有任何问题都可以来谈谈 ！ 如果看上一篇计数排序，你有没有这样疑问，当每个数据之间跨度过大(如从 0-2亿 数字中排序 20 个数)，就需要大量空间消耗。桶排序就是对计数排序的改进。 1.桶排序(Bucket sort)百度百科: 桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是 鸽巢排序 的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。继续 --> 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点： 在额外空间充足的情况下，尽量增大桶的数量使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。 桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。 快速排序是将集合拆分为两个值域，这里称为两个桶，再分别对两个桶进行排序，最终完成排序。桶排序则是将集合拆分为多个桶，对每个桶进行排序，则完成排序过程。两者不同之处在于，快排是在集合本身上进行排序，属于原地排序方式，且对每个桶的排序方式也是快排。桶排序则是提供了额外的操作空间，在额外空间上对桶进行排序，避免了构成桶过程的元素比较和交换操作，同时可以自主选择恰当的排序算法对桶进行排序。2.原理2.1.关键元素值域的划分，也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择，若规则设计的过于模糊、宽泛，则可能导致待排序集合中所有元素全部映射到一个桶上，则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛，则可能导致待排序集合中每一个元素值映射到一个桶上，则桶排序向计数排序方式演化。排序算法的选择，从待排序集合中元素映射到各个桶上的过程，并不存在元素的比较和交换操作，在对各个桶中元素进行排序时，可以自主选择合适的排序算法，桶排序算法的复杂度和稳定性，都根据选择的排序算法不同而不同。2.2.算法过程根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；遍历待排序集合，将每一个元素移动到对应的桶中；对每一个桶中元素进行排序，并移动到已排序集合中。步骤 3 中提到的已排序集合，和步骤 1、2 中的待排序集合是同一个集合。与计数排序不同，桶排序的步骤 2 完成之后，所有元素都处于桶中，并且对桶中元素排序后，移动元素过程中不再依赖原始集合，所以可以将桶中元素移动回原始集合即可。示意图元素分配到不同桶中： 然后，元素在每个桶中排序： 3.代码基于 Java 的代码，代码逻辑很好理解，使用到插入排序，如果不理解，点击传送。package utils;import java.util.Arrays;/** * @author wangshiyu rodert * @date 2020/6/21 15:13 * @description */public class BucketSort { public static void main(String[] args) throws Exception { int[] array = {2, 1, 5, 3, 4}; BucketSort bucketSort = new BucketSort(); int[] sort = bucketSort.sort(array); System.out.println(Arrays.toString(sort)); } private static final InsertSort insertSort = new InsertSort(); public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); return bucketSort(arr, 5); } private int[] bucketSort(int[] arr, int bucketSize) throws Exception { if (arr.length == 0) { return arr; } int minValue = arr[0]; int maxValue = arr[0]; for (int value : arr) { if (value < minValue) { minValue = value; } else if (value > maxValue) { maxValue = value; } } int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;//向下取整 + 1 int[][] buckets = new int[bucketCount][0]; // 利用映射函数将数据分配到各个桶中 for (int i = 0; i < arr.length; i++) { int index = (int) Math.floor((arr[i] - minValue) / bucketSize); buckets[index] = arrAppend(buckets[index], arr[i]); } int arrIndex = 0; for (int[] bucket : buckets) { if (bucket.length <= 0) { continue; } // 对每个桶进行排序，这里使用了插入排序 bucket = insertSort.sort(bucket); for (int value : bucket) { arr[arrIndex++] = value; } } return arr; } /** * 自动扩容，并保存数据 * * @param arr * @param value */ private int[] arrAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr; }}class InsertSort { //插入排序 public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的 for (int i = 1; i < arr.length; i++) { // 记录要插入的数据 int tmp = arr[i]; // 从已经排序的序列最右边的开始比较，找到比其小的数 int j = i; while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 存在比其小的数，插入 if (j != i) { arr[j] = tmp; } } return arr; }}返回结果： ...

[toc] 前言声明：参考来源互联网，有任何争议可以留言。站在前人的肩上，我们才能看的更远。本教程纯手打，致力于最实用教程，不需要什么奖励，只希望多多转发支持。欢迎来我公众号，希望可以结识你，也可以催更，微信搜索：JavaPub 有任何问题都可以来谈谈 ！ 计数排序是比较容易的排序算法，但是对数量级较小的整数排序很实用。1.计数排序(Counting Sort)1.1.计数排序(Counting Sort)计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为 (n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当 O(k)>O(n*log(n)) 的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如 归并排序，堆排序）例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。 计数排序是一个简单的排序算法，看下边原理很容易理解。2.原理2.1.步骤算法的步骤如下：找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数，存入数组C的第i项对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1 如果有疑问，看下边一个例子2.2.实例题目题目：数组里有20个随机数，取值范围为从0到10，要求用最快的速度把这20个整数从小到大进行排序。无论是[归并排序]()，[冒泡排序]()还是[快速排序]()等等，都是基于元素之间的比较来进行排序的。但是有一种特殊的排序算法叫计数排序，这种排序算法不是基于元素比较，而是利用 数组下标 来确定元素的正确位置。 通过计数排序特性分析题目，我们知道整数的取值范围是从0到10，那么这些整数的值肯定是在0到10这11个数里面。于是我们可以建立一个长度为11的数组，数组下标从0到10，元素初始值全为0，如下所示： 先假设20个随机整数的值是： 9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9 让我们先遍历这个无序的随机数组，每一个整数按照其值对号入座，对应数组下标的元素进行 加1 操作。比如第一个整数是 9，那么数组下标为 9 的元素加 1： 第二个整数是3，那么数组下标为 3 的元素加 1： 继续遍历数列并修改数组......最终，数列遍历完毕时，数组的状态如下： 数组中的每一个值，代表了数列中对应整数的出现次数。 有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次： 0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10 ...

[toc] 原文地址 前言声明：参考来源互联网，有任何争议可以留言。站在前人的肩上，我们才能看的更远。本教程纯手打，致力于最实用教程，不需要什么奖励，只希望多多转发支持。欢迎来我公众号，希望可以结识你，也可以催更，微信搜索：JavaPub 有任何问题都可以来谈谈 ！ 堆排序在常用排序算法中属于比较难理解的，本篇就以最简单的方式讲解。如果还有什么疑问，1.什么是堆？弄清楚<font color=#159957>堆排序</font>以前，我们先要知道什么是<font color=#159957>堆</font>？堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。下图： 简单用公式描述一下就是： 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 问题二：什么是<font color=#159957>完全二叉树</font>？ 百度百科: 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。2.堆排序百度百科: 堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序是利用<font color=#159957>堆</font>这种数据结构而设计的一种排序算法，堆排序是一种<font color=#159957>选择排序</font>，它的最坏，最好，平均<font color=#159957>时间复杂度</font>均为O(nlogn)，它也是<font color=#159957>不稳定排序</font>。 3.原理堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了<font color=#159957>步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。</font> a.假设给定无序序列结构如下　b.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。　c.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。　d.这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。　此时，就将一个无需序列构造成了一个大顶堆。　<font color=#159957>步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。</font> a.将堆顶元素9和末尾元素4进行交。　b.重新调整结构，使其继续满足堆定义。　c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8。　后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序。　...