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
栏目导航
