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

结尾

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

欢迎关注微信公众号:小狮子前端Vue

谢谢您的支持!✿✿ヽ(°▽°)ノ✿