文档章节

基础算法笔记 - 排序

yhcast
 yhcast
发布于 2017/08/26 22:25
字数 1031
阅读 0
收藏 0
点赞 0
评论 0

1. 选择排序

输入:A = {a1, a2, a3, ..., an}; (未排序)

输出:A = {a1', a2', a3', ..., an'}; (其中a1' <= a2' <= a3' <= ... <= an',非降序排序)

假设:

  • 第一个元素下标为1
  • 最后一个元素下标为A.length
  • n = A.length

时间复杂度:O(n^2)

  • 最优:θ(n^2)
  • 最差:θ(n^2)

伪代码:

SELECTION_SORT(A)
    for i=1 to A.length - 1
        indexForMin = i
        for j=i+1 to A.length
            if A[j] < A[indexForMin]
                indexForMin = j
        swap A[i] with A[indexForMin]

2. 插入排序

输入:A = {a1, a2, a3, ..., an}; (未排序)

输出:A = {a1', a2', a3', ..., an'}; (其中a1' <= a2' <= a3' <= ... <= an',非降序排序)

假设:

  • 第一个元素下标为1
  • 最后一个元素下标为A.length

时间复杂度:O(n^2)

  • 最优:θ(n)
  • 最差:θ(n^2)

伪代码:

INSERTION_SORT(A)
    for i=2 to A.length
        key = A[i]
        j = i - 1
        while j > 0 and A[j] > key
            A[j+1] = A[j]
            j--
        A[j+1] = key

3. 希尔排序(Shell Sort)

为插入排序的一种,该方法实质上是一种分组插入方法。

输入:A = {a1, a2, a3, ..., an}; (未排序)

输出:A = {a1', a2', a3', ..., an'}; (其中a1' <= a2' <= a3' <= ... <= an',非降序排序)

假设:

  • 第一个元素下标为1
  • 最后一个元素下标为A.length
  • floor()表示向下取整
  • n = A.length

时间复杂度:O(n^2)

  • 最优:θ(n)
  • 最差:θ(n^2)

伪代码:

SHELL_SORT(A)
    for (gap = floor(n/2); gap > 0; gap = floor(gap/2))
        for (i = gap+1; i <= n; i++)
            key = A[i]
            j = i - gap
            while(j > 0 and A[j] > key)
                A[j+gap] = A[j]
                j -= gap
            A[j+gap] = key

4. 冒泡排序

输入:A = {a1, a2, a3, ..., an}; (未排序)

输出:A = {a1', a2', a3', ..., an'}; (其中a1' <= a2' <= a3' <= ... <= an',非降序排序)

假设:

  • 第一个元素下标为1
  • 最后一个元素下标为A.length

时间复杂度:O(n^2)

  • 最优:θ(n) 或 θ(n^2) 取决于具体算法
  • 最差:θ(n^2)

伪代码:

BUBBLE_SORT(A)
    for i = 1 to A.length - 1
        for j = A.length to i + 1
            if A[j] < A[j-1]
                swap A[j] with A[j-1]

or

BUBBLE_SORT(A)
    sorted = false
    unsorted_head = 1
    while !sorted and unsorted_head < A.length
        sorted = true
        for i = A.length down to unsorted_head + 1
            if A[i] < A[i-1]
                sorted = false
                swap A[i] with A[i-1]
        ++unsorted_head

5. 鸡尾酒排序

又称双向冒泡排序

输入:A = {a1, a2, a3, ..., an}; (未排序)

输出:A = {a1', a2', a3', ..., an'}; (其中a1' <= a2' <= a3' <= ... <= an',非降序排序)

假设:

  • 第一个元素下标为1
  • 最后一个元素下标为A.length

时间复杂度:O(n^2)

  • 最优:θ(n)
  • 最差:θ(n^2)

伪代码:

COCKTAIL_SORT(A)
    sorted = false
    begin = 0
    end = A.length - 1
    while !sorted
        sorted = true
        ++begin
        for i = begin to end    // 从左往右比较
            if A[i] > A[i+1]
                sorted = false
                swap A[i] with A[i+1]
        if sorted    // 如果排序完成,退出while循环
             break while loop
        sorted = true
        --end
        for i = end down to begin    // 从右往左比较
            if A[i] > A[i+1]
                sorted = false
                swap A[i] with A[i+1]

6. 归并排序

输入:A = {a1, a2, a3, ..., an}; (未排序)

输出:A = {a1', a2', a3', ..., an'}; (其中a1' <= a2' <= a3' <= ... <= an',非降序排序)

假设:

  • 第一个元素下标为1
  • 最后一个元素下标为A.length
  • 3个整数p, q, r,其中 p <= q < r
  • floor()表示向下取整

时间复杂度:O(n*log(n))

伪代码:

MERGE_SORT(A, p ,r)
    if p < r
        q = floor((p + r) / 2)
        MERGE_SORT(A, p ,q)
        MERGE_SORT(A, q+1, r)
        MERGE(A, p, q, r)

MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1 ... n1] and R[1 ... n2] be new arrays
    for i=1 to n1
        L[i] = A[p+i-1]
    for j=1 to n2
        R[j] = A[q+j]
    i = 1
    j = 1
    for k=p to r
        if (j > n2) or (i <= n1 and L[i] < R[j])
            A[k] = L[i]
            i += 1
        else
            A[k] = R[j]
            j += 1

7. 快速排序

输入:A = {a1, a2, a3, ..., an}; (未排序)

输出:A = {a1', a2', a3', ..., an'}; (其中a1' <= a2' <= a3' <= ... <= an',非降序排序)

假设:

  • 第一个元素下标为1
  • 最后一个元素下标为A.length
  • 默认主元(pivot)为数组的第一个元素

时间复杂度:O(n*log(n))

伪代码:

QUICK_SORT(A, first, last)
    if last > first
        pivotIndex = PARTITION(A, first, last)
        QUICK_SORT(A, first, pivotIndex-1)
        QUICK_SORT(A, pivotIndex+1, last)

PARTITION(A, first, last)
    pivot = A[first]
    lowIndex = first + 1
    highIndex = last
    while highIndex > lowIndex
        while lowIndex <= highIndex and A[lowIndex] <= pivot
            lowIndex++
        while lowIndex <= highIndex and A[highIndex] > pivot
            highIndex--
        if highIndex > lowIndex
            swap A[lowIndex] with A[highIndex]
    while highIndex > first and A[highIndex] >= pivot
        highIndex--
    if pivot > A[highIndex]
        A[first] = A[highIndex]
        A[highIndex] = pivot
        return highIndex
    else
        return first

© 著作权归作者所有

共有 人打赏支持
yhcast
粉丝 0
博文 1
码字总数 1031
作品 0
二叉树算法笔记:二叉排序树(二叉搜索树) in java

本内容仅贴出三链二叉树的操作(在二叉树的两篇文章里已经有了如下代码,完全相同,只是这里把二叉排序树的代码提取出来而已)。 二叉树算法笔记:二叉树基础操作(三链二叉树) in java http:...

CheN_exe ⋅ 2014/01/26 ⋅ 0

算法-美团2015校招笔试:写一个复杂度为n的排序算法

一组随机排序的字母数字。请编写一个时间复杂度为O(n)的算法,使这些字母从小到大顺序排序。说明:字母区分大小写,相同的字母,排序护小写排在前面。例如:R,B,B,b,W,W,B,R,B,w排序为:b,B...

pointerException ⋅ 2015/07/29 ⋅ 0

算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于恨,是因为它在进行算法分析的时候所体现的数学思想...

chambai ⋅ 2015/09/11 ⋅ 0

Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛 ⋅ 2017/11/10 ⋅ 0

MoreWindows博客目录(微软最有价值专家,原创技术文章152篇)

为了方便大家查找和学习,现将本人博客中所有博客文章列出目录。 一. 白话经典算法 目前有17篇,分为七大排序和经典面试题讲解两大类 1. 《白话经典算法系列之一 冒泡排序的三种实现》 2. 《...

morewindows ⋅ 2013/12/24 ⋅ 0

好书一起读(85):算法笔记

这阵子看了两本算法书,《算法》和《算法导论》。 前一本读着很轻松,内容基本与大学数据结构课程重叠,示例代码用java编写,学习曲线平缓,对应用程序员来说,读它就挺好。 后一本我是边看麻...

祁达方 ⋅ 2016/09/07 ⋅ 0

stl-stable_sort源码学习笔记

前几天,一个新同事前来询问算法stl-stablesort的情况。由于离上次研读stl源码时间久已(两三年前的事儿了),有些细节笔记模糊了。所以就找了sgi-stl和ms-stl俩版本,重新复习一遍其中的stl...

huangjunkun ⋅ 2011/11/07 ⋅ 0

数据结构复习笔记(4)

1, 归并排序无论初始序列如何排列,记录的比较次数不会受到影响,都是O(nlogn),但会影响到记录的移动次数,初始序列为正序时,记录移动次数为0,为逆序时,记录移动次数最大。 2, 若在100...

嗯哼9925 ⋅ 2017/12/27 ⋅ 0

DeepLearning笔记:Docker 入门和用 Python 实现词频统计

一、神经网络简介 神经网络简史: 40年代:概念雏形(没有学习算法) 50年代:可用的学习算法 - 感知机 1969年:Minsky 泼冷水 70年代:BP 算法,训练多层神经网络 90年代:SVM 支持向量机「...

Kidult ⋅ 2017/12/27 ⋅ 0

hjimce算法类博文目录 个人博客:http://blog.csdn.net/hjimce 个人qq:1393852684 知乎:https://www.zhihu.com/people/huang-jin-chi-28/activities 一、深度学习 深度学习(七十)darknet...

hjimce ⋅ 2016/01/24 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

windows profesional 2017 build problem

.net framework .... https://stackoverflow.com/questions/43330915/could-not-load-file-or-assembly-microsoft-build-frameworkvs-2017...

机油战士 ⋅ 30分钟前 ⋅ 0

python3中报错的解决方法(长期更新)

1、ImportError: No module named ‘DjangoUeditor’ 出错原因:安装DjangoUeditor库适用于python2,需要下载适用python3的 下载地址:https://github.com/twz915/DjangoUeditor3 2、python3......

xiaoge2016 ⋅ 35分钟前 ⋅ 0

数据结构与算法之双向链表

一、双向链表 1.双向链表的结点结构 typedef struct DualNode{ ElemType data; struct DualNode *prior; // 前驱结点 struct DualNode *next; // 后继结点}DualNode, *DuL...

aibinxiao ⋅ 55分钟前 ⋅ 0

五大最核心的大数据技术

大数据技术有5个核心部分,数据采集、数据存储、数据清洗、数据挖掘、数据可视化。关于这5个部分,有哪些核心技术?这些技术有哪些潜在价值?看完今天的文章就知道了。 大数据学习群:7165810...

董黎明 ⋅ 56分钟前 ⋅ 0

PhpStorm 头部注释、类注释和函数注释的设置

首先,PhpStorm中文件、类、函数等注释的设置在:setting-》Editor-》FIle and Code Template-》Includes下设置即可,其中方法的默认是这样的: /**${PARAM_DOC}#if (${TYPE_HINT} != "v...

nsns ⋅ 56分钟前 ⋅ 0

spring.net AOP

http://www.springframework.net/doc-latest/reference/html/aop-quickstart.html https://www.cnblogs.com/wujy/archive/2013/04/06/3003120.html...

whoisliang ⋅ 今天 ⋅ 0

【HAVENT原创】创建 Dockerfile 生成新的镜像,并发布到 DockerHub

注意:Win7 与 Win10 的版本存在差异,Win7 版本使用 Docker Quickstart Terminal 进入控制台,Win10下面直接用管理员权限打开控制台或者 PowerShell 即可;另外 Win7 下面只能访问 C盘,/ap...

HAVENT ⋅ 今天 ⋅ 0

pom.xml出现web.xml is missing ...解决方案

提示信息应该能看懂。也就是缺少了web.xml文件,<failOnMissingWebXml>被设置成true了。 搜索了一下,Stack Overflow上的答案解决了问题,分享一下。 目前被顶次数最多的回答原文如下: This...

源哥L ⋅ 今天 ⋅ 0

js时间戳与日期格式之间相互转换

1. 将时间戳转换成日期格式 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 简单的一句代码 var date = new Date(时间戳); //获取一个时间对象 /** 1. 下面是获取时间日期的方法,需要什么样的格式自己...

Jack088 ⋅ 今天 ⋅ 0

web添加log4j

添加xml配置log4j.properties # Global logging configuration---root日志设置#log4j.rootLogger=info,dailyRollingFile,stdoutlog4j.rootLogger=debug,stdout,dailyRollingFile---......

黄柳淞 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部