JavaScript：十大排序算法思想及代码实现排序（优化）、堆排序、希尔排序。您可以在此处测试代码。leetcode的更多javascript解决方案也可以在我的算法仓库中找到，欢迎查看~另外，附上前十类的C++版本。因为我习惯写JavaScript，所以这个C++版本有点难看，请不要介意。如果觉得有帮助，就点个星鼓励一下吧，谢蟹😊首先推荐一个数据结构和算法的动态可视化工具，可以查看各种算法的动画演示。下面开始正文。冒泡排序通过比较和交换相邻的元素，使得每次循环都能找到无序数组的最大值或最小值。***:O(n)，数组只需要冒泡一次就可以排序了。最差：O(n2)平均：O(n2)单向冒泡函数bubbleSort(nums){for(leti=0,len=nums.length;inums[j+1]){[nums[j],nums[j+1]]=[nums[j+1],nums[j]];mark=false;}}if(mark)return;}}双向风险普通冒泡排序一个循环只能找到一个最大值或最小值，而双向冒泡排序可以在多个循环中同时找到最大值和最小值。functionbubbleSort_twoWays(nums){letlow=0;lethigh=nums.length-1;while(lownums[i+1]){[nums[i],nums[i+1]]=[nums[i+1],nums[i]];mark=false;}}high--;//求最小值放在左边for(letj=high;j>low;j--){if(nums[j]nums[j]){[nums[i],nums[j]]=[nums[j],nums[i]];}}}}插入排序把第一个元素作为一个有序数组，后面的元素通过在这个有序数组中寻找合适的位置来插入。***:O(n)，原来的数组已经是升序了。最差：O(n2)平均：O(n2)functioninsertSort(nums){for(leti=1,len=nums.length;i=0&&temp=right)return;letindex=partition(arr,left,right);recursive(arr,left,index-1);recursive(arr,index+1,right);returnarr;}//把比基数小的数放在基数左边，比基数大的数放在右边基数，并返回基数的位置functionpartition(arr,left,right){//以***数为基数[right]>=temp)right--;arr[left]=arr[right];while(left=right)return;letindex=partition(arr,left,right);recursive(arr,left,index-1);recursive(arr,index+1,right);returnarr;}functionpartition(arr,left,right){lettemp=arr[left];letp=left+1;letq=right;while(p<=q){while(p<=q&&arr[p]temp)q--;if(p<=q){[arr[p],arr[q]]=[arr[q],arr[p]];//交换值后，双方向中间前进一位p++;q--;}}//修改基数的位置[arr[left],arr[q]]=[arr[q],arr[left]];returnq;}recursive(nums,0,nums.length-1);}归并排序将数组递归分成两个序列，将两个序列按顺序合并。***:O(n*logn)worst:O(n*logn)average:O(n*logn)参考学习链接：图解排序算法（四）合并排序函数mergeSort(nums){//有序合并两个数组函数merge(l1,r1,l2,r2){letarr=[];letindex=0;leti=l1,j=l2;while(i<=r1&&j<=r2){arr[index++]=nums[i]=right)return;//相对于(left+right)/2，推荐如下写法，避免数字溢出letmid=parseInt((right-left)/2)+left;recursive(left,mid);recursive(mid+1,right);merge(left,mid,mid+1,right);returnnums;}recursive(0,nums.length-1);}桶排序取n个桶，根据数组的最大值和最小值确认每个桶中存储的数字范围，插入数组元素放入相应的桶中，最后合并每个桶。***：O(n)，每个数分布在一个桶中，这样就不需要将数插入桶中并排序（类似于以空间换时间的计数排序）。最差：O(n2)，所有数字都分布在一个桶中。平均：O(n+k)，k代表桶数。参考学习链接：拜托，面试不要问我桶排序的问题！！！functionbucketSort(nums){//桶的个数，只要是正数就可以letnum=5;letmax=Math.max(...nums);letmin=Math.min(...nums);//计算每个存储桶中的取值范围至少为1，letrange=Math.ceil((max-min)/num)||1;//创建一个二维数组，***维表示的个数buckets，第二个维度表示存储在bucket中的个数letarr=Array.from(Array(num)).map(()=>Array().fill(0));nums.forEach(val=>{//计算元素应该分布在哪个桶中letindex=parseInt((val-min)/range);//防止索引越界，比如当[5,1,1,2,0,0],索引会出现5indexindex=index>=num?num-1:index;lettemp=arr[index];//插入排序，将元素按顺序插入桶中letj=temp.length-1;while(j>=0&&val{nums[i]=res[i];})}基数排序使用0-9十个桶，将每个数按照位数从低到高放入对应的桶中，然后循环***值中的位数。但是只能排正整数，因为负号和小数点不能比较。***：O(n*k)，k表示***值的位数。最差：O(n*k)平均：O(n*k)参考学习链接：算法总结系列五：基数排序（RadixSort）函数radixSort(nums){//计算位数函数getDigits(n){letsum=0;while(n){sum++;n=parseInt(n/10);}returnsum;}//***维度表示位数，为0-9，第二个维度表示存储的值在letarr=Array.from(Array(10)).map(()=>Array());letmax=Math.max(...nums);letmaxDigits=getDigits(max);for(leti=0,len=nums.length;i=0;i--){//循环每个bucketfor(letj=0;j<=9;j++){lettemp=arr[j]letlen=temp.length;//放数bucket中根据当前数字i放入对应的bucketwhile(len--){letstr=temp[0];temp.shift();arr[str[i]].push(str);}}}//修改回原来的数组letres=[].concat.apply([],arr);nums.forEach((val,index)=>{nums[index]=+res[index];})}计数排序以数组元素值作为键，出现次数作为值存入一个临时数组，最后遍历临时数组恢复原数组。因为JavaScript数组下标是以字符串的形式存储的，所以可以使用计数排序来排列负数，但不能排列小数。***：O(n+k)，k为***值与最小值之差。最差：O(n+k)平均：O(n+k)functioncountingSort(nums){letarr=[];letmax=Math.max(...nums);letmin=Math.min(...nums);//为(leti=0,len=nums.length;i0){nums[index++]=i;arr[i]--;}}}计数排序优化添加每个数组元素的最小数量相反，以避免在特殊情况下浪费空间。通过这种优化，可以将开辟空间的大小从max+1缩小到max-min+1，max和min分别是数组中的最大值和最小值。比如数组[103,102,101,100]中，一个普通的计数排序需要开一个长度为104的数组，前100个值都是undefined。使用这种优化方式后，只能开一个长度为4的数组functioncountingSort(nums){letarr=[];letmax=Math.max(...nums);letmin=Math.min(...nums);//加上最小值的相反数，缩小数组的范围letadd=-min;for(leti=0,len=nums.length;i0){nums[index++]=i;temp--;}}}堆排序??根据数组构建一个堆（类似完全二叉树），每个节点的值都大于左右节点（***堆，一般用于升序），或者小于左右节点（最小堆，一般用于降序）。对于升序排序，在构造第一个堆后，交换堆顶元素（代表最高值）和堆底元素，每次交换都可以得到无序序列的最高值。重新调整第一个堆，然后交换堆顶元素和堆底元素。重复n-1次后，可以得到一个递增的数组。***:O(n*logn)，logn是调整***堆所花费的时间。最差：O(n*logn)平均：O(n*logn)参考学习链接：常用排序算法-堆排序（HeapSort）图形排序算法（三）堆排序函数heapSort(nums){//调整***堆，使index的值大于左右节点functionadjustHeap(nums,index,size){//交换后堆结构可能会被破坏，需要循环使每个父节点都大于左右节点while(true){letmax=index;letleft=index*2+1;//左节点letright=index*2+2;//右节点if(left=0;i--){adjustHeap(nums,i,size);}}buildHeap(nums);//循环n-1次，每次循环后交换堆顶元素和堆底部元素并重新调整堆结构for(leti=nums.length-1;i>0;i--){[nums[i],nums[0]]=[nums[0],nums[i]];adjustHeap(nums,0,i);}}希尔排序将整个序列通过一定的增量间隙分成若干组，从后往前比较交换组内成员，然后逐步将增量减为1。希尔排序是与插入排序类似，只是将开始时的前进步数由1改为gap。***:O(n*logn)，步长一直二分。最差：O(n*logn)平均：O(n*logn)参考学习链接：图解排序算法（二）希尔排序函数shellSort(nums){letlen=nums.length;//初始步数letgap=parseInt(len/2);//逐步减少步数while(gap){//从gap元素开始遍历for(leti=gap;i=0;j-=gap){if(nums[j]>nums[j+gap]){[nums[j],nums[j+gap]]=[nums[j+gap],nums[j]];}else{break;}}}gap=parseInt(gap/2);}}看完后，有什么问题或者发现错误的可以在下方评论留言留言，或者在我的仓库提问题，一起讨论吧#128522;
