文档章节

基础算法笔记 - 排序

yhcast
 yhcast
发布于 2017/08/26 22:25
字数 1031
阅读 1
收藏 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
0
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
07/25
0
0
算法-美团2015校招笔试:写一个复杂度为n的排序算法

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

pointerException
2015/07/29
0
0
算法导论第二章小试牛刀

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

chambai
2015/09/11
0
0
Android 面试文档分享

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

泽毛
2017/11/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Sql语言与MySql数据库

1. 数据库简介 1. 数据库,就是存储数据的仓库,只能通过sql语言来访问,数据库也是一个文件系统。通常,MySQL、Oracle等数据库,也被称为关系型数据库,其保存的不仅仅只是数据,还包括数据...

江左煤郎
27分钟前
0
0
IDEA 取消自动import .*

打开设置 > Editor > Code Style > Java > Scheme Default > Imports ① 将 Class count to use import with "*" 改为 99 (导入同一个包的类超过这个数值自动变为 * ) ② 将 Names count ......

乔老哥
28分钟前
1
0
PostGIS学习笔记(开篇)

PostGIS事实上算是笔者开始写博客的第一篇内容。而事实上那篇博文的内容并不丰富,笔者对PostGIS的了解仍然不多,然而17年在OSGeo课程学习时对PostGIS又有了进一步了解,并逐步发现它的强大。...

胖胖雕
28分钟前
1
0
【Centos】在nginx服务器中配置php和mysql

接上一章《【Centos】利用Vultr服务器和namesilo布网》(https://my.oschina.net/u/3776619/blog/2051986),在Centos中配置好nginx,并在iptables中开启了80端口,和为了远程mysql操作方便开...

yongh701
52分钟前
3
0
flume -- fileChannel简要分析其过程

flume之event写入FileChannel doPut(event)-->获取共享锁后[log.lockShared();]-->FlumeEventPointer ptr = log.put(transactionID, event); 此处的log.put即将transactionID及event进行后续......

-九天-
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部