一些简单的数组排序算法

AndroidTraveler 发布于2019-08-23 10:41 / 3202人阅读

摘要：快速排序递归分而治之通过一趟排序将要排序的数据分割成独立的两部分，然后再按此方法对这两部分数据分别进行快速排序，每次返回一个有序数组。

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;iright){
                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

选择排序    无序中选择极值进行排序
1. 在数组中选择出 ** 最小的一项 极值 **（也就是没有排序的当中）
2. 将其插入到数组的开头（有序的开头）
3. 再把选出来的最小一项删除掉
3. 上面两部就行成了 （有序的开头+无序的数组）
4. 每走一轮，前面的有序+1，后面的无序-1，所以，n个元素，***n-1轮*** 第n轮已经找不到无序的了

function selectSort(arr){
    var length = arr.length;
    for(var i = 0;i

插入排序 无序中循环，插入到有序中

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;iarr[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



数组越长，快速排序>插入排序>选择排序>冒泡排序

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

云服务器 GPU云服务器最简单的排序算法字符串排序数组排序算法数组排序算法c语言简单的c语言排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96592.html

【算法日积月累】1-选择排序

摘要：选择排序算法实现实现选择排序，记录最小元素的索引，最后才交换位置说明交换两个数组中的元素，在中有更简单的写法，这是的语法糖，其它语言中是没有的。和语言中比较器的实现前面我们说到了，我们为了突出排序算法的思想，将所有的例子仅限在数组排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

neuSnail 2019-07-31 11:21 评论0 收藏0
归并排序 - Algorithms, Part I, week 3 MERGESORTS

摘要：两个单元素数组的合并实际就是对这两个数进行了排序，即变为，同样再对后一组的两个数归并排序，即变为，再将两单元数组归并成四单元数组即和归并为。前言本周讲解两个50多年前发明，但今天仍然很重要的经典算法 (归并排序和快速排序) 之一 -- 归并排序，几乎每个软件系统中都可以找到其中一个或两个的实现，并研究这些经典方法的新变革。我们的涉及范围从数学模型中解释为什么这些方法有效到使这些算法...

Jokcy 2019-08-19 11:35 评论0 收藏0
JavaScript数据结构和算法

摘要：栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构，比如下面介绍的二叉查找树。前言在过去的几年中，得益于Node.js的兴起，JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器，程序员发现他们需要更多传统语言（比如C++和Java）提供的工具。这些工具包括传统的数据结构（如链表，栈，队列，图等），...

EastWoodYang 2019-08-21 16:23 评论0 收藏0
一些前端算法詳解 --- (不定时更新)

摘要：也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因於年提出而得名。前言因為比较随心所欲,所以我不按难度分享算法,所以你们会看到有时候顺序有变化,因為我发表的时候会按照难度修改下位置,尽量让你们看的时候能从简单开始,以后每次更新都加个更新时间好了,让你们知道我进度.新增计时函数直观对比效率并且因為资料比较杂,很多都是我个人理解说法,如果有发...

Baaaan 2019-08-26 10:35 评论0 收藏0