十大排序算法思路总结面试过程中经常会遇到手写排序算法，所以本文就简单总结一下。不介绍算法的细节，只给出一般描述。交换类：排序是通过元素之间的两两交换来实现的插入类：将数分成两部分，将无序数依次插入到有序数组中选择类：从数组中寻找最小值或最大值待排序值元素，并将它们放在排序后的序列后面。“计数排序和基数排序可以认为是桶排序的一种特殊实现，它们不是通过比较元素来排序的。”冒泡排序冒泡排序，从头开始，依次比较数组中相邻的两个元素，如果后面的数大于前面的数，则交换两个数，否则不交换。对于每一轮比较，数组中最大的元素将放在末尾。如下图所示，一轮比对的过程如下。当数组有n个元素时，只需要n轮比较，整个数组就有序了。publicstaticvoidbubbleSort(int[]a){//I轮比较for(inti=0;ia[j+1]){swap(a,j,j+1);}}}}publicstaticvoidswap(int[]a,inti,intj){inttemp=a[i];a[i]=a[j];a[j]=temp;}fast排序和快速排序的执行过程主要分为以下三个步骤。从序列中取一个数作为参考数分区，将所有大于它的数放在它的右边，所有小于或等于它的数放在它的左边。对左右区间重复第二步，直到每个区间只有一个数publicstaticvoidquickSort(int[]a,intleft,intright){if(left>=right){return;}intindex=sort(a,left,right);quickSort(a,left,index-1);quickSort(a,index+1,right);}publicstaticintsort(int[]a,intleft,intright){intkey=a[left];while(left=key){right--;}a[left]=a[right];//从low指向的位置向后查找，找到key大于key的第一条记录，相互交换keywhile(left0;j--){while(a[j]=0&&a[j]>temp;j--){a[j+1]=a[j];}a[j+1]=temp;}}希尔排序“希尔排序是一种基于插入排序的改进算法。因为当数据移动太多次时会导致效率低下。所以我们可以先让数组整??体有序（开始移动范围大一些，然后小一些），这样移动的次数就会减少，从而提高效率。){for(intstep=a.length/2;step>0;step/=2){for(inti=step;i=0&&a[j]>temp;j-=step){a[j+step]=a[j];}a[j+step]=temp;}}}选择第一个排序time迭代，第二次迭代将最小的放在数组的第0位置，将次小的放在数组的第1位置publicstaticvoidselectionSort(int[]a){for(inti=0;ia[j]){index=j;}}if(index!=i){swap(a,index,i);}}}publicstaticvoidswap(int[]a,inti,intj){inttemp=a[i];a[i]=a[j];a[j]=temp;}heapsort让我们手写一个堆排序。首先，我们来解释一下什么是堆？堆是一种数据结构，需要满足以下特征。堆是一棵完全二叉树（生成节点的顺序是从左到右，从上到下。堆中某个节点的值总是不大于或不小于其父节点的值。”）根节点最大的堆称为最大堆或大根堆，根节点最小的堆称为最小堆或小根堆。”大根堆和小根堆如图所示下图，假设有一棵完整的二叉树如下，如何调整成堆呢？可以看到10及其子节点满足条件，3及其子节点满足条件，节点4不满足满足条件."所以我们需要对节点4进行调整，调整过程称为heapify"从节点4的左右两个节点中，找到一个大节点（即节点10），并与节点进行交换4.交换后，交换后的节点不一定是同一个，满足条件，所以需要调整（调整过程和1类似）最后交换4个节点和5个节点。二叉树变成堆在实际的开发过程中，我们不会用树结构来表示堆，而是用一个数组。通过下标的特点，可以总结出以下规律。如果数组中某个节点的下标为i，则父节点的下标为：parent=(i-1)/2左节点的下标为：c1=2*i+1右节点的下标就是：c2=2*i+2所以上图中的堆在数组中表示为[10,5,3,4,1,2,0]。知道怎么用数组表示一个堆，我们写下堆化以下4个节点的过程/***@parama数组*@paramn数组长度*@parami待堆化节点*/publicstaticvoidheapify(int[]a,intn,inti){//递归退出if(i>=n){return;}//左节点下标intc1=2*i+1;//右节点下标intc2=2*i+2;intmax=i;if(c1a[max]){max=c1;}if(c2a[max]){max=c2;}//交换左节点的最大值和右节点与父节点if(max!=i){swap(a,max,i);heapify(a,n,max);}}@Testpublicvoidheapify(){int[]array=newint[]{4,10,3,5,1,2};//调整为10,5,3,4,1,2HeapSort.heapify(array,array.length,0);“我们如何将一棵完全二叉树变成一个堆？”"只要将非叶子节点从左到右改为从左到右，就可以从下到上依次进行heapify。"如下图，只需要依次heapify10,3,4publicstaticvoidbuildTree(int[]a){//找到最后一个非叶子节点intlastNode=a.length-1;intparent=(lastNode-1)/2;for(inti=parent;i>=0;i--){heapify(a,a.length,i);}}让我们测试@TestpublicvoidbuildTree(){int[]array=newint[]{3,5,7,2,4,9,6};//9572436HeapSort.buildTree(array);}知道了堆是怎么产生的，怎么调整流程，我们分析流程就很简单了堆排序的！以大顶堆为例，最大值一定是根节点，将根节点与最后一个叶子节点交换，然后将叶子节点移出堆，此时根节点做不满足要求，所以对根节点heapify后，又变成了堆。重复步骤1和2，可以找到剩余节点的最大值，因为每次找到的最大值都在数组的最后一位，所以我们不需要实际执行移除堆的操作，但是执行heapify时，数组的长度逐渐减小。能。最后的数组是升序publicstaticvoidheapSort(int[]a){//先建一个堆buildTree(a);//每次交换堆的根节点和最后一个节点，然后执行heapifyfor(inti=a.length-1;i>=0;i--){swap(a,i,0);heapify(a,i,0);}}所以最后的堆排序代码如下publicclassHeapSort{publicstaticvoidheapSort(int[]a){buildTree(a);for(inti=a.length-1;i>=0;i--){swap(a,i,0);heapify(a,i,0);}}publicstaticvoidbuildTree(int[]a){//找到最后一个非叶子节点intlastNode=a.length-1;intparent=(lastNode-1)/2;for(inti=parent;i>=0;i--){heapify(a,a.length,i);}}/***@parama数组*@paramn数组长度*@parami待堆化的节点*/publicstaticvoidheapify(int[]a,intn,inti){if(i>=n){返回;}intc1=2*i+1;intc2=2*i+2;intmax=i;if(c1a[max]){max=c1;}if(c2a[max]){max=c2;}if(max!=i){swap(a,max,i);heapify(a,n,max);}}publicstaticvoidswap(int[]a,inti,intj){inttemp=a[i];a[i]=a[j];a[j]=temp;}}这里只演示如何建堆，proc是什么堆排序的问题？“要实现满堆，我们还需要提供插入节点和删除根节点的方法”。我不会写实现，而是用图来演示这个过程。有兴趣的可以写，《大部分语言都内置了堆的实现，也就是优先级队列（Java中的PriorityQueue），所以我们在使用堆场景的时候，可以直接使用PriorityQueue向堆中插入节点，向堆中插入节点时，插入的位置为完全二叉树的最后一个位置，比如我们插入一个值为8的新节点，我们将8与其父节点进行比较.如果8>5,让新节点往上浮.和父节点交换位置后,继续和父节点比较.如果8<9,就不用了.调整了堆删除节点.当删除一个节点从堆，删除堆顶的节点，比如我们删除大顶堆的9个节点，为了保持堆的结构，我们把堆的最后一个节点6加到堆顶堆的。然后我们将堆顶部的节点与其左右子节点进行比较。如果左右子节点是其中最大的一个比节点6大，则让节点6下沉，然后与左右节点比较，如果3<6，则前K个高频元素不用调整题目地址：剑指toOffer40.最小的k个数进入一个整数数组arr，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8的8个数，最小的4个数为1、2、3、4。输入：arr=[3,2,1],k=2Output:[1,2]or[2,1]Limit:0<=k<=arr.length<=100000<=arr[i]<=10000“堆”维护着一个大的顶堆。当堆中的元素不够k时，继续向堆中放入元素。当堆中元素大于等于k时，将堆顶元素与新加入的元素进行比较。如果新加入的元素小于堆顶元素，则删除堆顶元素，将新填充的元素放入堆中，以保证堆中的元素堆总是最小的kpublicint[]getLeastNumbers(int[]arr,intk){if(arr.length==0||k==0){returnnewint[0];}PriorityQueuequeue=newPriorityQueue<>((num1,num2)->num2-num1);for(intnum:arr){if(queue.size()k?quickSort(nums,left,index-1,k):quickSort(nums,index+1,right,k);}publicintsort(int[]a,intleft,intright){intkey=a[left];同时（左<右）{同时（左<右&&a[right]>=key){right--;}a[left]=a[right];while(left0&&index0){a[index++]=i;count[i]--;}}}上面的算法其实是有缺陷的，但是当数组中的元素为10000、10001、10002时，我们必须创建一个大小为10003的数组，这是不现实的。所以我们可以将映射关系num[i]的含义改为原数组中i+min的个数num[i]进阶版publicstaticvoidcountingSort(int[]a){intmax=Integer.MIN_VALUE;intmin=Integer。MAX_VALUE;for(intnum:a){max=Integer.max(max,num);min=Integer.min(min,num);}int[]count=newint[max-min+1];for(intnum:a){count[num-min]++;}intindex=0;for(inti=0;i0){a[index++]=i+min;count[i]--;}}}》在面试过程中，经常遇到数组中的一个模，可以用计数和排序的思想来解决“基数排序”快照和归并排序面试过程中问题很多，应用场景也很多。”基数排序基本不问，就不解释了。桶排序》前面我们提到的计数排序和基数排序可以说是桶排序思想的一种特殊体现，即不需要比较arrayelements之间。”基本不会被问到，不解释各种排序算法应用面试中经常被问到的Topk题，可以先排序，然后找到Topk的元素。各种排序算法的效率是如图所示“一个更有效的想法是使用堆和快速排序。TopK问题的出法有很多种，本质思路都是一样的。前K个高频元素》本文转载自微信公众号“Java知堂”，可通过以下二维码关注，转载请联系Java知堂公众号。
