Java教程
这次，真的不怕面试官要你手写排序算法了！
本文主要是介绍这次，真的不怕面试官要你手写排序算法了！，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
写在开头
大家好，这里是lionLoveVue，基础知识决定了编程思维，学如逆水行舟，不进则退。金三银四，为了面试也还在慢慢积累知识，Github上面可以直接查看所有前端知识点梳理，github传送门，觉得不错，点个Star★，好运连连，Offer终究鼠于你，持续更新中。另外，也可以关注微信公众号：小狮子前端Vue，源码以及资料今后都会放在里面。
一直想着成为一个up主，正值时间挺多的，4月份左右面试的面经我会制作视频去分享，赶快捧个场吧。哔哩哔哩：一百个Chocolate
1、冒泡排序
基本思路
1.依次比较相邻的两个数，如果第一个比第二个小，不变。如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数
2.对除了最后一个之外的数重复第一步，直到只剩一个数
图示
算法实现（JS代码）
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title></head><body> <script> function bubbleSort(arr){ var len=arr.length; var i,j; for(i=0;i<len;i++){ for(j=0;j<len-i-1;j++){ if(arr[j]>arr[j+1]) //两两之间进行比较 swap(arr,j,j+1); } } return arr; } function swap(arr,i,j){ var tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } var arr=[1,12,6,3,5]; bubbleSort(arr); console.log(arr);</script></body></html>
执行结果1
算法实现（C++代码）
#include<bits/stdc++.h>using namespace std;const int maxn=1e3+5;int a[maxn],n;int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++){ for(int j=0;j<n-i-1;j++){ if(a[j]>a[j+1]) swap(a[j],a[j+1]); } } for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0;}
执行结果2
2、选择排序
基本思路
1.找出最小的数，和第一个交换位置
2.在剩下的数中，找出最二小的数，放在第二个
3.依次类推，排出顺序
图示
算法实现（JS代码）
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title></head><body> <script> function selectionSort(arr){ var len=arr.length; var i,j,xmin; for(i=0;i<len;i++){ xmin=i; //将当前值设为最小值 for(j=i+1;j<len;j++){ if(arr[j]<arr[xmin]) xmin=j; //在后面找到更小的值 } if(i!=xmin) swap(arr,i,xmin) //将找到的更小值进行交换 } return arr; } function swap(arr,i,j){ var tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } var arr=[1,12,6,3,5]; selectionSort(arr); console.log(arr);</script></body></html>
执行结果1
算法实现（C++代码）
#include<bits/stdc++.h>using namespace std;const int maxn=1e3+5;int a[maxn],n;int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++){ int xmin=i; for(int j=i+1;j<n;j++){ if(a[j]<a[xmin]) xmin=j; } if(xmin!=i) swap(a[xmin],a[i]); } for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0;}
执行结果2
3、插入排序
基本思路
1.把数组分为[已排序]和[未排序]两部分,第一个数为[已排序]，其余为[未排序]
2.从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置
图示
算法实现（Js代码）
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title></head><body> <script> function insertSort(arr){ var len=arr.length; var i,j,val; for(i=0;i<len;i++){ val=arr[i]; for(j=i-1;j>=0;j--){ if(arr[j]<val) break; //找到可以放的位置即跳出 arr[j+1]=arr[j]; } arr[j+1]=val; } return arr; } var arr=[1,12,6,3,5]; insertSort(arr); console.log(arr);</script></body></html>
执行结果1
算法实现（C++代码）
#include<bits/stdc++.h>using namespace std;const int maxn=1e3+5;int a[maxn],n;int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++){ int val=a[i],j; for(j=i-1;j>=0;j--){ if(a[j]<val) break; a[j+1]=a[j]; } a[j+1]=val; } for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0;}
执行结果2
4、归并排序(分而治之)
基本思路
1.不断将数组对半分，直到每个数组只有一个
2.将分出来的部分重新合并
3.合并的时候按顺序排列
图示
算法实现（JS代码）
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title></head><body> <script> function merge(left,right){ var res=[], i=0,j=0; //合并两个数组（按照从小到大的顺序） while(i<left.length&&j<right.length){ if(left[i]<right[j]){ res.push(left[i++]); }else{ res.push(right[j++]); } } //数组拼接 return res.concat(left.slice(i)).concat(right.slice(j)); }
function mergeSort(arr){ var len=arr.length; var i,j; //不断拆分至只有一个数 if(len<=1) return arr; var mid=Math.floor(len/2); var left=arr.slice(0,mid), right=arr.slice(mid); return merge(mergeSort(left),mergeSort(right)); } var arr=[1,12,6,3,5]; arr=mergeSort(arr); console.log(arr);</script></body></html>
执行结果1
算法实现（C++代码）
#include<bits/stdc++.h>using namespace std;const int maxn=1e3+5;int a[maxn],n;void mergeArray(int le,int mid,int re){ int len=re-le+1; int * tmp=new int[len]; int cnt=0; int i=le,j=mid+1; while(i<=mid&&j<=re){ if(a[i]<=a[j]) tmp[cnt++]=a[i++]; else tmp[cnt++]=a[j++]; } while(i<=mid) tmp[cnt++]=a[i++]; while(j<=re) tmp[cnt++]=a[j++]; for(int j=0;j<len;j++) a[le+j]=tmp[j]; delete [] tmp;}void mergeSort(int le,int re){ if(le<re){ int mid=(le+re)/2; mergeSort(le,mid); mergeSort(mid+1,re); mergeArray(le,mid,re); }}int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; mergeSort(0,n-1); for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0;}
执行结果2
5、快速排序
基本思路
1.以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边
2.再按此方法对这两部分数据分别进行快速排序（递归进行）
3.不能再分后退出递归，并重新将数组合并
图示
算法实现（JS代码）
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title></head><body> <script> function partition(arr,p,q){ var i = p; var x= arr[p]; var j; for(j=p+1;j<=q;j++){ if(arr[j]<=x){ ++i; swap(arr,i,j); } } swap(arr,i,p); return i; //返回划分中间位置 } function quickSort(arr,p,q){ if(p<q){ var k = partition(arr,p,q); //确定划分中间位置 quickSort(arr,p,k-1); //对左边部分进行递归 quickSort(arr,k+1,q); //对右边部分进行递归 } } //交换函数 function swap(arr,i,j){ var tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } var arr=[1,12,6,3,5]; quickSort(arr,0,arr.length-1); console.log(arr);</script></body></html>
执行结果1
算法实现（C++代码）
#include<bits/stdc++.h>using namespace std;const int maxn=1e3+5;int a[maxn],n;int quick_partition(int p,int q){ int i=p; int x=a[p]; for(int j=p+1;j<=q;j++){ if(a[j]<=x){ ++i; swap(a[i],a[j]); } } swap(a[i],a[p]); return i;}void quick_sort(int p,int q){ if(p<q){ int k=quick_partition(p,q); quick_sort(p,k-1); quick_sort(k+1,q); }}int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; quick_sort(0,n-1); for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0;}
执行结果2
6、随机化快速排序
基本思路
随机化快速排序只是在快排基础上将主元通过随机函数选取一下了。
关于js中随机产生【n , m】随机数实例：
在本例中，我们将取得介于 1 到 10 之间的一个随机数：
Math.floor((Math.random()*10)+1);
输出结果：
5
算法实现（Js代码）
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title></head><body> <script> //随机选取主元 function randk(arr,p,q){ var k = Math.floor(Math.random()*q+p); swap(arr,p,k); return partition(arr,p,q); } function partition(arr,p,q){ var i = p; var x= arr[p]; var j; for(j=p+1;j<=q;j++){ if(arr[j]<=x){ ++i; swap(arr,i,j); } } swap(arr,i,p); return i; //返回划分中间位置 } function quickSort(arr,p,q){ if(p<q){ var k = randk(arr,p,q); //确定划分中间位置 quickSort(arr,p,k-1); //对左边部分进行递归 quickSort(arr,k+1,q); //对右边部分进行递归 } } //交换函数 function swap(arr,i,j){ var tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } var arr=[1,12,6,3,5]; quickSort(arr,0,arr.length-1); console.log(arr);</script></body></html>
执行结果1
算法实现（C++代码）
#include<bits/stdc++.h>using namespace std;const int maxn=1e3+5;int a[maxn],n;int quick_partition(int p,int q){ int i=p; int x=a[p]; for(int j=p+1;j<=q;j++){ if(a[j]<=x){ ++i; swap(a[i],a[j]); } } swap(a[i],a[p]); return i;}int rand(int p,int q){ int k=rand()%(q-p+1)+p; swap(a[k],a[p]); return quick_partition(p,q);}void qsort(int p,int q){ if(p<q){ int k=rand(p,q); qsort(p,k-1); qsort(k+1,q); }}int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; qsort(0,n-1); for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0;}
执行结果2
结尾
如若本文有瑕疵需修改的地方，请提出来，谢谢您的贡献！
在后台留言回复【笔记】即可获得一份精心整理的前端笔记（持续更新中）
这篇关于这次，真的不怕面试官要你手写排序算法了！的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
RocketMQ底层原理资料详解：新手入门教程11-29
-
RocketMQ源码资料解析与入门教程11-29
-
[开源]6.1K star！这款电视直播源神器真的太赞啦！11-29
-
HTTP压缩入门教程：轻松提升网页加载速度11-29
-
JWT开发入门指南11-29
-
知识管理革命：文档软件的新玩法了解一下！11-28
-
低代码应用课程：新手入门全攻略11-28
-
哪些办公软件适合团队协作，且能够清晰记录每个阶段的工作进展？11-28
-
全栈低代码开发课程：零基础入门到初级实战11-28
-
拖动排序课程：轻松掌握课程拖动排序功能11-28
-
如何高效管理数字化转型项目11-28
-
SMART法则好用吗？有哪些项目管理工具辅助实现？11-28
-
深度剖析：6 款办公软件如何构建设计团队项目可视化管理新生态？11-28
-
HTTP缓存课程：新手入门指南11-28
-
实战丨证券 HTAP 混合业务场景的难点问题应对11-28
栏目导航
