这次，真的不怕面试官要你手写排序算法了！

2021/6/14 22:21:15

编程Tag： 排序 return var int 手写 arr swap 面试官 maxn

本文主要是介绍这次，真的不怕面试官要你手写排序算法了！，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

写在开头

大家好，这里是lionLoveVue，基础知识决定了编程思维，学如逆水行舟，不进则退。金三银四，为了面试也还在慢慢积累知识，Github上面可以直接查看所有前端知识点梳理，github传送门，觉得不错，点个Star★，好运连连，Offer终究鼠于你，持续更新中。另外，也可以关注微信公众号：小狮子前端Vue，源码以及资料今后都会放在里面。

一直想着成为一个up主，正值时间挺多的，4月份左右面试的面经我会制作视频去分享，赶快捧个场吧。哔哩哔哩：一百个Chocolate

1、冒泡排序

基本思路

1.依次比较相邻的两个数，如果第一个比第二个小，不变。如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数


2.对除了最后一个之外的数重复第一步，直到只剩一个数

图示

640?wx_fmt=other

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

2、选择排序

基本思路

1.找出最小的数，和第一个交换位置


2.在剩下的数中，找出最二小的数，放在第二个


3.依次类推，排出顺序

图示

640?wx_fmt=other

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

3、插入排序

基本思路

1.把数组分为[已排序]和[未排序]两部分,第一个数为[已排序]，其余为[未排序]


2.从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置

图示

640?wx_fmt=other

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

4、归并排序(分而治之)

基本思路

1.不断将数组对半分，直到每个数组只有一个


2.将分出来的部分重新合并


3.合并的时候按顺序排列

图示

640?wx_fmt=other

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

5、快速排序

基本思路

1.以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边


2.再按此方法对这两部分数据分别进行快速排序（递归进行）


3.不能再分后退出递归，并重新将数组合并

图示

640?wx_fmt=other

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

算法实现（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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

结尾

如若本文有瑕疵需修改的地方，请提出来，谢谢您的贡献！

 

在后台留言回复【笔记】即可获得一份精心整理的前端笔记（持续更新中）

 



这篇关于这次，真的不怕面试官要你手写排序算法了！的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程