一些简单的数组排序算法
文章目录
arraySort 数组排序
这里为大家整理了一些简单的数组排序的算法
冒泡排序 --- 比较两个相邻的元素,替换成正确的位置(你选择的正序还是倒序)
快速排序 --- 基线条件 --- 只剩一个元素的时候就是有序的数组
选择排序 --- 无序中选择极值,进行排序
插入排序 --- 无序中循环,插入到有序中
冒泡排序
重复地走访过要排序的元素列,一次比较两个相邻的元素,重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
1. 从数组的第一项 **arr[0]** 项开始,与 **arr[1]** 进行对比,大的往后移动
2. 对每一个相邻的元素,都进行以上操作,直到没有相邻元素进行对比,最后一对相邻 **arr[length-2]-arr[length-1]**
3. 两两对比一轮之后,发现数组最后一个元素是最大的
4. 每走一轮,大的元素都到冒泡到了最后面,所以 ***n个元素,n-1个循环(n-1轮)(n-1个外循环)***(最后第二轮结束的时候,最小的元素已经在最前面了)
5. 每走一轮,最后的元素已经排好序,所以每走一轮,**比较相邻元素的次数少了一次 arr.length-1-当前外循环 **
function bubbleSort(arr){
var length = arr.length;
for(var i = 0;i<length-1;i++){
for(var j=0;j<length-i-1;j++){
var left = arr[j];
var right = arr[j+1];
if(left>right){
arr[j]=right;
arr[j+1]=left;
}
}
}
return arr;
}
冒泡排序的优点:每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值。
每进行一趟比较,每一趟少比较一次,一定程度上减少了算法的量。
快速排序 -递归-分而治之
通过一趟排序将要排序的数据分割成独立的两部分,然后再按此方法对这两部分数据分别进行快速排序,每次返回一个有序数组。
1. 基数条件(不再进行递归的操作):数组长度等于1
2. 递归条件:数组长度大于1
3. 选择一个基准值 **base**
4. 大于基准值的放一边,小于基准值的放一边 **left right**
5. 分开的每边 再次挑选基准值,重复3之后的步骤
6. 最后将返回的数组合并在一起
function quickSort(arr){
if(arr.length<2){
return arr;
}
var base = arr.splice(Math.floor(arr.length/2),1); //基准值
var left = [];
var right = [];
for(var i=0;i<arr.length;i++){
if(arr[i]<base){
left.push(arr[i]); //小于基准值
}else{
right.push(arr[i]); //大于基准值
}
}
return [].concat(quickSort(left),base,quickSort(right));
}
选择排序 无序中选择极值进行排序
1. 在数组中选择出 ** 最小的一项 极值 **(也就是没有排序的当中)
2. 将其插入到数组的开头(有序的开头)
3. 再把选出来的最小一项删除掉
3. 上面两部就行成了 (有序的开头+无序的数组)
4. 每走一轮,前面的有序+1,后面的无序-1,所以,n个元素,***n-1轮*** 第n轮已经找不到无序的了
function selectSort(arr){
var length = arr.length;
for(var i = 0;i<length-1;i++){
var min = arr[i];
var minIndex = i;
for(var j = i+1;j<length;j++){ //无序中选择最极值
if(arr[j]<min){
min = arr[j];
minIndex = j;
}
}
arr.splice(i,0,min); //将极值插入到有序中
arr.splice(minIndex+1,1);//将原先的位置删除
}
return arr;
}
插入排序 无序中循环,插入到有序中
1.假设**arr[0]**为有序的第一项,arr[0]之后的都为无序 (有序+无序)
2.从arr[0]之后无序进行循环,插入到**有序**相应的位置中
3.每走一轮,有序+1,无序-1
n.arr[n]和arr[n-1]对比,满足 arr[n-1] > arr[n], =>=> 在有序中找到相应的位置插入
function insertSort(arr){
var length = arr.length;
for(var i = 1;i<length;i++){
var insert = arr[i]; //插入元素
var insertIndex = i; // 插入位置
if(arr[i-1]>arr[i]){ //判断能不能动,只要前面那一项比他大就能动
for(var j = i-1;j>=0;j--){
if(arr[j]>insert){ //前面那一项比他大,那么将前面那一项的位置记录下来,
insertIndex = j;
}
}
arr.splice(insertIndex,0,insert); //插入到前面去
arr.splice(i+1,1); //原来位置上的删除,因为插入了一项,要在原来的位置上加1
}
}
return arr;
}
再来对比一下这四个排序
| ms \ 数组长度 | 6 | 10 | 3000 |
|---|---|---|---|
| 冒泡排序 | 0.19 | 0.56 | 19.6 |
| 快速排序 | 0.28 | 0.29 | 0.27 |
| 选择排序 | 0.22 | 0.82 | 12.6 |
| 插入排序 | 0.34 | 0.44 | 11 |
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论