Nemo
Nemo
《算法图解》-第二章:选择排序
《算法图解》-第二章:选择排序

本章内容

  • 学习两种最基本的数据结构:数组、链表
  • 学习第一种排序算法:选择排序

数组和链表

  • 需要存储多项数据时,有两种基本方式——数组和链表。
  • 在数组中所有的数据在内存中都是相连的,如要添加新元素时,原本数据后没有空余空间时,计算机就会迁移这些数据到合适的内存空间。
    • 额外请求的位置可能根本用不上,这将浪费内存,即使没有使用,其他数据也利用不了。
    • 数据存储超过预先分配的空间后会被整体迁移。

链表

  • 链表中的元素可能会被存储在任何地方。
  • 链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。
  • 在链表中添加元素很容易:只需要将其放入内存,并将其地址存储到前一个元素中。
  • 链表支持顺序访问。

数组

  • 链表中存在着这样的问题,在需要读取链表的最后一个元素时,并不能直接读取,因为不知道它所处的地址,必须先访问元素#1,从中获取元素#2的地址,再访问元素#2并从中获取元素#3的地址,…,直到访问到最后一个元素。如果需要跳跃访问,链表的效率真的很低。
  • 数组不一样,我们知道每个元素的地址索引。
  • 数组支持随机访问。

常见的数组和链表操作的运行时间:

数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n)
O(1)

O(n)=线性时间

O(1)=常量时间

选择排序

  • 运行时间:O(n^2)

示例代码:

  1. 找出数组中最小元素:
def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

2.编写排序算法

def selectionSort(arr):
    newArry = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArry.append(arr.pop(smallest)) #arr剔除一个值,newArry添加一个
    return newArry
  1. 完整运行:
def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index


def selectionSort(arr):
    newArry = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArry.append(arr.pop(smallest))
    return newArry


print(selectionSort([5, 3, 6, 9, 9, 6, 9]))

小结

  • 计算机内存犹如一大堆抽屉
  • 需要存储多个元素时,可使用数组或链表
  • 数组的元素都在一起
  • 链表的元素是分开的,其中每个元素存储了下一个元素的地址
  • 数组的读取速度很快
  • 链表的插入和删除速度很快
  • 在同一个数组中,所有元素的类型都必须相同(都为int,double等)
赞赏
Nemo版权所有丨如未注明,均为原创丨本网站采用BY-NC-SA协议进行授权,转载请注明转自:https://kanghaov.com/87.html
https://secure.gravatar.com/avatar/9fd8359b8faa6f7789f9623ba6041e4a?s=256&d=monsterid&r=g

kanghaov

文章作者

推荐文章

发表评论

textsms
account_circle
email

Nemo

《算法图解》-第二章:选择排序
本章内容 学习两种最基本的数据结构:数组、链表 学习第一种排序算法:选择排序 数组和链表 需要存储多项数据时,有两种基本方式——数组和链表。 在数组中所有的数据在内存中都是…
扫描二维码继续阅读
2019-05-15