算法学习—排序

排序算法

一、选择排序

1.算法简介

选择排序是一个简单直观的排序方法,它的工作原理很简单,首先从未排序序列中找到最大的元素,放到已排序序列的末尾,重复上述步骤,直到所有元素排序完毕。

2.算法描述

1)假设未排序序列的第一个是最大值,记下该元素的位置,从前往后比较
2)若某个元素比该元素大,覆盖之前的位置
3)重复第二个步骤,直到找到未排序的末尾
4)将未排序元素的第一个元素和最大元素交换位置
5)重复前面几个步骤,直到所有元素都已经排序。

3.算法分析

选择排序的交换操作次数最好情况已经有序为0次,最坏情况逆序n-1次,因此交换操作次数位于0(n-1)次之间;比较操作次数(n-1+…+2+1+0)为n(n-1)/2次;交换元素赋值操作为3次,逆序需要n-1趟交换,因此,赋值操作位于03(n-1)次之间。由于需要交换位置,所以肯定是不稳定的。

时间复杂度均为o(n^2) 空间复杂度为o(1) 不稳定

4.代码实现

//选择排序
function selsetSort(arr){
	var len = arr.length;
	for(var i=0;i<len-1;i++){
		for(var j=i+1;j<len;j++){
			if(arr[i] > arr[j]){//寻找最小值
                var temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
			}
		}
	}
	return arr;
}

二、冒泡排序

1.算法简介

列表每两个相邻的数进行比较,如果前面的数比后面的数大,则交换这两个数,一轮排序完成后,则无序区减少一个数,有序区增加一个数。

2.算法描述

1)快速排序的特点就是随机设置一个基准点,比如是数组的第一个元素,然后数组的其他元素就跟这个基准线进行对比,比基准线大的放在左边,比基准线小的放在右边
2)再设置一个基准线,再这样小的放左边,大的放右边,递归。

3.算法分析

平均时间复杂度O(nn) 、最好情况O(n)、最差情况O(nn)

空间复杂度O(1) 稳定

4.代码实现

 function sort(arr){
     let len = arr.length;
     for (let i = 0; i < len - 1 ; i++) {
         // 用来标记在一轮冒泡过程中有无交换过
         let flag = false;
         for (let j = 0; j < len - i; j++) {
             if(arr[j] > arr[j+1]){
                 // 交换两个数
                 let temp = arr[j];
                 arr[j] = arr[j+1];
                 arr[j+1] = temp;
                 flag = true;
             }
         }
         // 如果在一轮冒泡过程中没有交换过,说明此时的列表已经是排序好的了,直接结束循环
         if(!flag){
             return;
         }
     } 
 }
let arr = [2,3,1,4,8,7,9,6];
this.sort(arr;
console.log(arr); 

三、插入排序

1.算法简介

所谓插入排序,就是把最小的(或者最大的),一次次插入到最前面,从而达到排序的效果

2.算法描述

刚开始将整个数组看作一个无序区,每一轮拿无序区的第一数与有序区的数从后往前依次进行比较,遇到更大的数则交换,每一轮排序完成后,有序区增加一个数,无序区减少一个数。

3.算法分析

时间复杂度是O(n*n) 空间复杂度为o(1) 稳定

4.代码实现

function sort(arr){
    let len = arr.length;
    for (let i = 1; i < len; i++) {
        for (let j = i - 1; j >= 0 ; j--) {
            if(arr[j] > arr[j+1]){
                let temp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = temp
            }  
        }  
    }
}, 

四、快速排序

1.算法简介

采用“分治”的思想,对于一组数据,选择一个基准元素(base),通常选择第一个或最后一个元素,通过第一轮扫描,比base小的元素都在base左边,比base大的元素都在base右边,再有同样的方法递归排序这两部分,直到序列中所有数据均有序为止。快速排序算法的性能比冒泡、选择排序都要好,和归并排序一样,是一个可以用于实战的算法。

2.算法描述

1)快速排序的特点就是随机设置一个基准点,比如是数组的第一个元素,然后数组的其他元素就跟这个基准线进行对比,比基准线大的放在左边,比基准线小的放在右边
2)再设置一个基准线,再这样小的放左边,大的放右边,递归。

3.算法分析

时间复杂度是O(nlogn) 空间复杂度为o(logn) 不稳定

4.代码实现

 function sort(arr,l,r){
     if(l < r){
         let i = l;
         let j = r;
         let mid = arr[l];
         while(i < j){
             while(arr[j] > mid && i < j){
                 j--;
             }
             arr[i] = arr[j];
             while(arr[i] < mid && i < j){
                 i++;
             }
             arr[j] = arr[i];
         }
         arr[i] = mid
         this.test(arr,l,i-1)
         this.test(arr,i+1,j)
         return arr
     }else{
         return
     }
 }, 
 // 测试数据
let arr = [2,3,1,4,8,7,9,6];
let res = this.sort(arr,0,7);
console.log(res); 

五、归并排序

1.算法简介

使用分而治之的概念对给定的元素列表进行排序。它将问题分解为较小的子问题,直到它们变得足够简单以至可以直接解决为止。

2.算法描述

1)将给定的列表分为两半(如果列表中的元素数为奇数,则使其大致相等)。

2)以相同的方式继续划分子数组,直到只剩下单个元素数组。

3)从单个元素数组开始,合并子数组,以便对每个合并的子数组进行排序。

4)重复第 3 步单元,直到最后得到一个排好序的数组。

3.算法分析

时间复杂度是O(nlogn) 空间复杂度为O(n) 稳定

4.代码实现

function sort(arr){
    if(arr && arr.length > 1){
        const mid = Math.floor(arr.length/2)
        const left = arr.slice(0,mid)
        const right = arr.slice(mid);
        return this.merge(this.sort(left), this.sort(right))
    }
    return arr
},
function merge(leftList, rightList){
    const newList = [];
    const leftLength = leftList && leftList.length;
    const rightLength = rightList && rightList.length;
    let i = 0;
    let j = 0;
    while (i < leftLength && j < rightLength) {
        if (leftList[i] < rightList[j]) {
            newList.push(leftList[i++]);
        } else {
            newList.push(rightList[j++]);
        }
    }
    while (i < leftLength) {
        newList.push(leftList[i++]);
    }
    while (j < rightLength) {
        newList.push(rightList[j++]);
    }
    return newList;
}, 

六、堆排序

1.算法简介

堆是一种特殊的完全二叉树,堆分为大根堆和小根堆,满足任一节点都比其孩子节点大的一个完全二叉树就是大根堆,满足任一节点都比其孩子节点小的一个完全二叉树就是小根堆。

2.算法描述

首先构造一个大根堆(此时整个堆是无序区),然后将堆顶的元素取出放到有序区(也就是数组的最后),然后将堆的最后一个元素(也就是无序区的最后一个元素)放到堆顶,堆就少了一个元素,此时通过一次向下调整重新使堆有序,调整后的堆顶就是整个数组的第二大元素,然后重复之前的操作依次将元素放到有序区,直到堆变空,便可得到排序好的数组。

3.算法分析

时间复杂度是O(nlogn) 空间复杂度为O(1) 不稳定

4.代码实现

function sort(list) {
    if (list && list.length > 1) {
        const len = list.length;
        // 首先构造大根堆,从最后一个不是叶子节点的节点开始遍历,从后往前依次进行向下调整
        for (let i = Math.floor((len-2)/2); i>=0; i--) {
            sift(list, i, len-1);
        }
        // 然后将堆的第一元素与有序区的第一个元素进行交换,此时有序区增加一个,无序区减少一个,再进行一次堆的向下调整,然后重复上述操作,最终使整个数组有序
        for(let i = len-1; i>=0; i--){
            const m = list[0];
            list[0] = list[i];
            list[i] = m;
            sift(list, 0, i-1);
        } 
    }
}

/**
* 堆的向下调整
* 先从根节点开始,如果孩子节点比父节点大,则将该孩子节点赋值给父节点
* 然后指针指向下一层,重复上面的操作,直到找到孩子节点没有比父节点大的节点,终止循环
* 最后将原始的根节点赋值给当前父节点
*/
function sift(li, low, high) {
    const tmp = li[low]; // 缓存根节点
    let i = low; // 当前的父节点,最开始指向根节点
    let j = i*2+1; // 当前的孩子节点,最开始指向根节点的左孩子节点

    while (j <= high) {
        // 如果有右孩子节点且比左孩子节点大,则j指向右孩子节点
        if (j+1 <= high && li[j+1] > li[j]) {
            j++;
        }
        if (li[j] > tmp) {
            li[i] = li[j]; // 将较大的孩子节点赋值给父节点
            i = j; // i指向下一层
            j = i*2 +1;
        } else {
            break; // 如果当前子节点没有比原始根节点大,结束循环
        }
    }

    li[i] = tmp; // 最后将原始的根节点赋值给当前父节点
}

总结

排序算法复杂度总结图.png

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/207488.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C语言-预处理与库

预处理、动态库、静态库 1. 声明与定义分离 一个源文件对应一个头文件 注意&#xff1a; 头文件名以 .h 作为后缀头文件名要与对应的原文件名 一致 例&#xff1a; 源文件&#xff1a;01_code.c #include <stdio.h> int num01 10; int num02 20; void add(int a, in…

uniapp 使用web-view外接三方

来源 前阵子有个需求是需要在原有的项目上加入一个电子签名的功能&#xff0c;为了兼容性和复用性后面解决方法是将这个电子签名写在一个新的项目中&#xff0c;然后原有的项目使用web-view接入这个电子签名项目&#xff1b; 最近又有一个需求&#xff0c;是需要接入第三方的…

蓝桥杯每日一题2023.11.30

题目描述 九数组分数 - 蓝桥云课 (lanqiao.cn) 题目分析 此题目实际上是使用dfs进行数字确定&#xff0c;每次循环中将当前数字与剩下的数字进行交换 eg.1与2、3、4、、、进行交换 2与3、4、、、进行交换 填空位置将其恢复原来位置即可&#xff0c;也就直接将其交换回去即可…

Linux(CentOS7.5):新增硬盘分区纪实

一、服务器概述 1、既有一块系统硬盘&#xff0c;新增一块100G硬盘。 2、要求&#xff0c;将新插入硬盘分为&#xff1a;20G、30G、50G。 二、操作步骤 1、确认新硬盘是否插入成功&#xff1a; fdisk -l# 红色框出来的&#xff0c;为识别出来的新硬盘信息 # 黄色框出来的&#…

Linux:锁定部分重要文件,防止误操作

一、情景描述 比如root用户或者拥有root权限的用户&#xff0c;登陆系统后&#xff0c;通过useradd指令&#xff0c;新增一个用户。 而我们业务限制&#xff0c;只能某一个人才有权限新增用户。 那么&#xff0c;这个时候&#xff0c;我们就用chattr来锁定/etc/passwd文件&…

一些ab命令

1.ab简介 ab是apache自带的压力测试工具&#xff0c;是apachebench命令的缩写。ab非常实用&#xff0c;它不仅可以对apache服务器进行网站访问压力测试&#xff0c;也可以对或其它类型的服务器如nginx、tomcat、IIS等进行压力测试。 ab的原理&#xff1a;ab命令会创建多个并发…

力扣 790. 多米诺和托米诺平铺(一维dp)

题目描述&#xff1a; 有两种形状的瓷砖&#xff1a;一种是 2 x 1 的多米诺形&#xff0c;另一种是形如 "L" 的托米诺形。两种形状都可以旋转。 给定整数 n &#xff0c;返回可以平铺 2 x n 的面板的方法的数量。返回对 109 7 取模 的值。 平铺指的是每个正方形都…

df新增一列数据,并指定列名

方法1&#xff1a;直接指定df列名赋值为list即可 skill_info_df[age] age_list ps:list的长度要和df对齐 方法二 使用insert&#xff1a;

智能优化算法应用:基于象群算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于象群算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于象群算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.象群算法4.实验参数设定5.算法结果6.参考文献7.MATLAB…

AntDB数据库,通信行业20年变迁的见证者

2000年至今&#xff0c;通信行业发展已过了20多年。面对通信行业巨大的数据信息&#xff0c;数据库在行业发展中发挥了巨大的作用&#xff0c;AntDB数据库便是其中较为知名的一款数据库。在通信行业快速发展的阶段&#xff0c;打破国外产品与技术垄断是产业发展的重点与难点。面…

latex表格中内容过多如何换行【已解决】

最近在写论文的时候放了一个表格&#xff0c;但是表格看起来特别大&#xff0c;因为想让某些内容多的单元格完成换行操作 首先在main.tex引入makecell包 \usepackage{makecell} 然后回到表格找到你想换行的单元格&#xff0c;把\makecell{}加进去&#xff0c;然后在需要换行的…

深入浅出强化学习

目录 一、强化学习的概念 二、强化学习的特点 三、强化学习的训练过程 一、强化学习的概念 强化学习是一种机器学习方法&#xff0c;旨在教会算法如何通过与环境的交互来进行学习和决策。与传统的监督学习和无监督学习不同&#xff0c;强化学习侧重于学习与奖励和惩罚&#…

首批量子计算机即将部署!欧盟为波兰提供新算力优势

&#xff08;图片来源&#xff1a;网络&#xff09; 英国量子计算机开发商ORCA公司将为波兰的波兹南超级计算和网络中心&#xff08;PSNC&#xff09;提供两个PT-1光量子系统&#xff0c;以加速其在量子计算领域的研究和应用工作&#xff0c;如生物学、化学和机器学习领域。 …

机器人最优控制开源库 Model-based Optimization for Robotics

系列文章目录 文章目录 系列文章目录前言一、开源的库和工具箱1.1 ACADO1.2 CasADi1.3 Control Toolbox1.4 Crocoddyl1.5 Ipopt1.6 Manopt1.7 LexLS1.8 NLOpt1.9 qpOASES1.10 qpSWIFT1.11 Roboptim 二、其他库和工具箱2.1 MUSCOD2.2 OCPID-DAE12.3 SNOPT 前言 机器人&#xff…

Conductor之动态分叉

Conductor之动态分叉 动态分叉 关于动态分叉&#xff0c;参考1 动态分叉 有时候我们希望在运行时能动态添加分叉任务&#xff08;注意是分叉任务&#xff0c;不是动态任务&#xff09;&#xff0c;Conductor当前版本也是支持的&#xff0c;但是经过试验的版本只支持串行分叉&…

进程间通信方式——管道

进程间通信方式——管道 1、管道2、匿名管道2.1 创建匿名管道2.2 进程间通信 3、有名管道3.1 创建有名管道3.2 进程间通信 4、管道的读写行为 原文链接 1、管道 管道的是进程间通信&#xff08;IPC - InterProcess Communication&#xff09;的一种方式&#xff0c;管道的本质…

进程(process) vs 线程(Thread)

文章目录 前言一、进程&#xff08;process) vs 线程&#xff08;Thread&#xff09;引用自维基百科引用自CSDN INCOE AI引用自 geeksforgeeksOS( Operating System )如何调度线程的线程锁的核心原理是什么? 总结 前言 &#x1f680; 多方面理解进程(process) &#xff0c;线…

Python程序的计时

# -*- coding: UTF-8 -*- import timedef fun():time.sleep(5)sinceTime time.time() print("开始计时时刻&#xff1a;", sinceTime) fun() endTime time.time() print("结束时刻&#xff1a;", endTime) program_time endTime - sinceTime print(&quo…

振南技术干货集:各大平台串口调试软件大赏(5)

注解目录 &#xff08;串口的重要性不言而喻。为什么很多平台把串口称为 tty&#xff0c;比如 Linux、MacOS 等等&#xff0c;振南告诉你。&#xff09; 1、各平台上的串口调试软件 1.1Windows 1.1.1 STCISP &#xff08;感谢 STC 姚老板设计出 STCISP 这个软件。&#xf…

特殊二叉树——堆

&#x1f308;一、堆的基本概念 1.堆&#xff1a;非线性结构&#xff0c;是完全二叉树 2.堆分为大堆和小堆。 大堆&#xff1a;树中任意一个父亲都大于等于孩子&#xff0c;根节点值大于等于其所有子孙节点的值。 小堆&#xff1a;树中任意一个父亲都小于等于孩子&#xff0c;…