虽然现在编程语言的库函数都提供了排序功能，但是在经典的排序算法中应用了非常重要的算法思想，面试官也喜欢问。《排序算法》是一本很好的学习资料。本文将给出我认为比较基础和重要的排序算法的例子。算法概述算法分类比较排序：通过比较确定元素之间的相对顺序，因其时间复杂度无法突破O(nlogn)，又称为非线性时间比较排序。非比较排序：元素的相对顺序不是通过比较来确定的。它可以突破基于比较排序的下界，在线性时间内运行，所以又称为线性时间非比较排序。算法复杂度相关的概念是稳定的：如果a原本在b的前面，并且a=b，排序后a还是在b的前面。不稳定：如果a原本在b的前面，并且a=b，排序后a可能出现在b的后面。时间复杂度：对已排序数据的操作总数。它反映了n变化时操作次数的规律性。空间复杂度：指算法在计算机中执行时所需存储空间的度量，也是数据大小n的函数。冒泡排序选择排序（Selection-sort）是一种简单直观的排序算法。工作原理：先在未排序的序列中找到最小（最大）的元素，将其存入已排序序列的开头，然后继续从剩余未排序的元素中寻找最小（最大）的元素，再放入已排序的序列中的序列结束。依此类推，直到所有元素都排序完毕。函数选择排序（arr）{varlen=arr.length;varminIndex,temp;for(vari=0;i0;j--){if(nums[j-1]>nums[j]){swap(nums,j-1,j);}else{休息;}}}返回数字；}privatevoidswap(int[]nums,intindex1,intindex2){inttemp=nums[index1];nums[index1]=nums[index2];nums[index2]=温度；}}合并排序所谓合并就是将两个或多个有序序列合并成一个新的有序序列的过程。publicclassSolution{publicint[]sortArray(int[]nums){intlen=nums.length;mergeSort(nums,0,len-1);返回数字；}/***对于数组nums[left..right]的子范围归并排序**@paramnums*@paramleft*@paramright*/privatevoidmergeSort(int[]nums,intleft,intright){如果（左==右）{返回；}intmid=left+(right-left)/2;mergeSort(nums,left,mid);mergeSort(nums,mid+1,右);mergeOfTwoSortedArray（nums，左，中，右）；}/***合并两个有序数组：先把值复制到一个临时数组，然后再合并回来**@paramnums*@paramleft*@parammid[left,mid]是有序的，[mid+1,right]是有序的*@paramright*/privatevoidmergeOfTwoSortedArray(int[]nums,intleft,intmid,intright){//每次合并时，使用一个新数组进行合并，这是昂贵的intlen=right-left+1;int[]temp=newint[len];对于(inti=0;i的情况，它不同于归并排序，请通过调试了解此事if(left>=right){return;}intp=partition(nums,left,right);快速排序（nums，左，p-1）；快速排序（nums，p+1，右）；}privateintpartition(int[]nums,intleft,intright){intpivot=nums[left];//循环不变量：lt表示小于//[left+1,lt]=pivotintlt=left;//注意这里使用等号for(inti=left+1;i<=right;i++){if(nums[i]p+1，说明第K大元素出现在A[p+1...n-1]的区间，我们在A[p+1...n-]中按照上面的思路递归1]在此区间内搜索。堆排序（Heapsort）是指利用堆的数据结构设计的一种排序算法。堆叠是一种近似完全二叉树的结构，同时满足堆叠的性质：即子节点的键值或索引总是小于（或大于）其父节点。大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中按升序排列使用小顶堆：每个节点的值小于或等于其子节点的值子节点，在堆排序中在算法中按降序使用/***下沉操作*@param{array}arr待调整的堆*@param{number}parentIndex待下沉的父节点*@param{number}length有效堆的大小*/functiondownAdjust(arr,parentIndex,length){//temp保存父节点的值以供最终赋值lettemp=arr[parentIndex]letchildrenIndex=2*parentIndex+1while(childrenIndexarr[childrenIndex]){childrenIndex++}//如果父节点大于任何子节点的值，直接跳出if(temp>=arr[childrenIndex]){break}//当左右子树都大于父节点时，进行交换arr[parentIndex]=arr[childrenIndex]parentIndex=childrenIndexchildrenIndex=2*childrenIndex+1}arr[parentIndex]=temp}/***堆排序（升序）*@param{array}arr待调整的堆*/functionheapSort(arr){//将无序数组构建成最大堆，这里-2，因为索引从0开始，另外一个是叶子节点【最后一层不用堆】for(leti=(arr.length-2)/2;i>=0;i--){downAdjust(arr,i,arr.length)}//循环删除堆顶元素，并移动到集合尾部，调整堆生成新的堆顶for(leti=arr.length-1;i>0;i--){//交换最后一个元素和第一个元素lettemp=arr[i]arr[i]=arr[0]arr[0]=temp//下沉调整最大堆??downAdjust(arr,0,i)}returnarr}//testcaseconsole.log(heapSort([4,4,6,5,3,2,8,1]))
