文档章节

基础算法笔记 - 排序

yhcast
 yhcast
发布于 2017/08/26 22:25
字数 1031
阅读 2
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

Idea

command + E : 打开最近编辑过的文件 command + shift + O : 打开指定文件 command + O : 打开指定类 shift+command+delete 打开上一次编辑过的地方 option + command + t 代码块包含 option...

xpttxsok
37分钟前
2
0
FTP 协议 1.0

自己制作的FTP协议:

Explorer0
47分钟前
2
0
Android 通过DrawableInflater加载自定义Drawable

一、Drawable 在Android系统张,图形图像的绘制需要在画布上进行操作和处理,但是绘制需要了解很多细节以及可能要进行一些复杂的处理,因此系统提供了一个被称之为Drawable的类来进行绘制处理...

IamOkay
59分钟前
3
0
灵活无处安放,所以选择流浪....《漆黑的空间》& 《灰色轨迹》

灵活无处安放,所以选择流浪....《漆黑的空间》& 《灰色轨迹》

yizhichao
今天
1
0
Kafka+Flink 实现准实时异常检测系统

1.背景介绍 异常检测可以定义为“基于行动者(人或机器)的行为是否正常作出决策”,这项技术可以应用于非常多的行业中,比如金融场景中做交易检测、贷款检测;工业场景中做生产线预警;安防...

架构师springboot
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部