首页 > 编程语言 >排序算法(常见的排序算法的时间复杂度 O(n2))

排序算法(常见的排序算法的时间复杂度 O(n2))

时间:2022-10-27 21:35:31浏览次数:55  
标签:arr 复杂度 冒泡排序 算法 n2 排序

排序算法(常见的排序算法的时间复杂度 O(n2))

1.冒泡排序(俩俩(相邻的俩个)相比 位置交换)O(n2)

```js
//冒泡排序
function bubleSort(arr){
    //冒泡排序 外层的轮数
    for(var i=0;i<arr.length-1;i++){
        //控制比较的次数
        for(var j=1;j<arr.length-i;j++){
            //j和j-1 俩俩进行比较
            if(arr[j]<arr[j-1]){
                //换位置
                var temp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = temp
            }
        }
    }
    return arr
}

```

2.选择排序 (选择一个值 跟所有的值进行比较 然后这个值不是开始的 就换位置)O(n2)

```js
//选择排序
function selectorSort(arr){
    for(var i=0;i<arr.length-1;i++){
        //将当前的i值当做最大值
        var max = i
        for(var j = i+1;j<arr.length;j++){
            //判断当前的最大值小于j下标所在的值
            if(arr[max]<arr[j]){
                max = j
            }
        }
        //判断当前的最大值不是开始设置的值 要进行位置交换
        if(max != i){
            var temp = arr[i]
            arr[i] = arr[max]
            arr[max] = temp
        }
    }
    return arr
}

```

3.快速排序(冒泡排序的进阶 二分法)O(nlogn)

```js
//快速排序
function quikSort(arr){
    //当我们的数组里面只有一个元素或者一个元素都没有的时候 退出返回这个数组
    if(arr.length <= 1){
        return arr
    }
    //取基数值 取第一个
    var mid = arr[0]
    var left = []
    var right = []
    //for循环 拿出所有的值跟中间值比较
    for(var i=1;i<arr.length;i++){
        arr[i]>=mid?right.push(arr[i]):left.push(arr[i])
    }
    return quikSort(left).concat([mid],quikSort(right))
}

```

 

4.插入排序

5.希尔排序(插入排序的进阶)

6.堆排序

7.桶排序

8.基数排序

9.归并排序(大数据排序)

....

标签:arr,复杂度,冒泡排序,算法,n2,排序
From: https://www.cnblogs.com/hofenglang/p/16833805.html

相关文章

  • 选择排序
    选择排序概述选择排序是一种简单直观的排序算法,无论什么数据进去都是O(n²)的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间......
  • 冒泡排序
    算法详解以从小到大排序为例,冒泡排序法的思路是:遍历原始数据,从第一个数开始,到倒数第二个数结束,比较这个数和下一个数的大小,如果这个数比下一个数大,则交换这两个数。这样便......
  • mysql排序问题
    记一次排序参数导致的分页异常一个业务表中包含主要字段如下:IDSAVE_DATEUPDATE_TIMEVALUEINTyyyy-MM-ddtimeint主键日期时间戳业务数据业务要求......
  • 算法导论 Introduction to Algorithms #1
    目录算法基础分析算法设计算法练习思考题函数函数记号练习思考题分治策略练习思考题概论分析和随机算法练习思考题算法基础分析算法循环不变式设计算法分治法练......
  • 字典排序
    #按照列表中的每个字典的values大小进行排序,形成一个新的列表。listvar=[ {'sales_volumn':0}, {'sales_volumn':108}, {'sales_volumn':337}, {'sales_volumn':47......
  • 算法基础 Introduction
    算法要求正确性(Correctness)语法正确输入输出(IO)正确可读性(Readability)使用注释(不注释比坏注释好,代码易读比过多注释好)命名契合(camelCase、PascalCase、......
  • 反证法证明, 抓住定义的意义,不惧Corner case, 抓住循环不变量 | 代码随想录算法训练
    目录977.有序数组的平方算法的正确性采用反证法证明思路解题方法Code209.长度最小的子数组思维打开,抓住滑动窗口定义本质与意义,笑对CornerCases59.螺旋矩阵II......
  • 力扣(leetcode) 83. 删除排序链表中的重复元素(双指针算法)
    题目在这​​:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/​​思路分析:删除链表中相同的元素嘛。要注意这个链表是升序链表哦~~~~我们建立三......
  • 数据结构与算法---二分法 超详细解,保证你能看懂!!!!!
    二分法不难,看完这篇文章,你必懂。假如我们遇到了一道算法题,要求我们从数组A=[a,b,c,d,e]里找到d,那通常我们会逐个遍历,遍历a,b,c,d一共需要对比4个数字才能找到d。那如果使用......
  • 力扣(leetcode) 28. 实现 strStr() (一行代码解决问题) KMP算法解法待更新!!!!!!
    题目在这:https://leetcode-cn.com/problems/implement-strstr/法一:思路分析:Pythonfind()方法:检测字符串中是否包含子字符串str,如果指定beg(开始)和end(结束)范围,则......