【算法】算法图解笔记_选择排序

mylxsw 发布于2019-07-31 10:12 / 2575人阅读

摘要：选择排序是下一章将介绍的快速排序的基石。需要存储多项数据时有两种基本方式数组和链表。但它们并非都适用于所有的情形因此知道它们的差别很重要。选择排序是一种灵巧的算法但其速度不是很快。

选择排序是下一章将介绍的快速排序的基石。

内存的工作原理

计算机就像是很多抽屉的集合体,每个抽屉都有地址。

fe0ffeeb是一个内存单元的地址。

【细抠起来，这个图形有问题：实际上，计算机的内存是一维的，而图形是二维的。】

需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据时,有两种基本方式——数组和链表。但它们并非都适用于所有的情形,因此知道它们的差别很重要。

数组和链表 数组

数组中所有元素占用连续的内存，所以通过数组首元素地址，可以计算每个元素的地址。元素的位置称为索引，数组的索引从0开始，几乎所有的编程语言都从0开始对数组元素进行编号。在同一个数组中,所有元素的类型都必须相同(都为int、double等)。

数组具有以下特点：

知道每个元素的地址，支持随机访问方式；时间复杂度O(1)

插入元素时，可能导致元素的移动，最坏情况下，会移动所有元素；由于数组需要连续的内存，当前内存可能无法满足元素的存储，需要重新分配内存空间和进行元素的拷贝；插时间复杂度O(n)

删除元素后,必须将后面的元素都向前移；时间复杂度O(n)

链表

链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。链表中的元素可存储在内存的任何地方。只要有足够的内存空间,就能为链表分配内存。

链表具有以下特点：

支持顺序访问方式，只能从第一个元素开始逐个地读取元素；时间复杂度O(n)

在链表中添加元素很容易:只需将其放入内存,并将其地址存储到前一个元素中；时间复杂度O(1)

删除元素只需修改前一个元素指向的地址即可；时间复杂度O(1)

数组和链表还被用来实现其他数据结构，比如散列表等。

选择排序

算法思想：遍历待排序列表,找出最大或最小的元素，并添加到到新列表的第一个位置；然后找第二大或第二小的元素，依次类推，直到待排序列表里没有元素为止，此时新列表的元素已按降序或升序排列。

选择排序是一种灵巧的算法,但其速度不是很快。需要的总时间为 O(n × n),即O(n2)。

Python版本：

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):
  newArr = []
  for i in range(len(arr)):
    smallest = findSmallest(arr)
    newArr.append(arr.pop(smallest))
  return newArr

Haskell版本：

import Data.List (delete)

selectionSort :: Ord a => [a] -> [a]
selectionSort []  = []
selectionSort arr =
      let smallest = minimum arr
      in  smallest : selectionSort (delete smallest arr)

请关注我的公众号哦

GPU云服务器云服务器排序算法图解选择排序的算法过程字符串选择排序算法排序算法总结

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43430.html

【算法】算法图解笔记_算法简介

摘要：在本书中你将学习比较不同算法的优缺点该使用合并排序算法还是快速排序算法或者该使用数组还是链表。这样的算法包括快速排序一种速度较快的排序算法。在读《算法图解》这本书，这本书有两个优点：手绘风格的图，看着很让人入戏；算法采用Python语言描述，能更好的表达算法思想。关于算法的学习有两点心得：算法思想最重要，理解了思想，算法是很容易写出来的，所以尽量不要把过多精力放在细节上...

tomlingtm 2019-07-31 10:10 评论0 收藏0
【算法】算法图解笔记_快速排序

摘要：再谈大表示法快速排序的独特之处在于其速度取决于选择的基准值。在平均情况下快速排序的运行时间为在最糟情况下退化为。快速排序和合并排序的算法速度分别表示为和，是算法所需的固定时间量被称为常量。分而治之分而治之(divide and conquer,D&C)是一种著名的递归式问题解决方法。只能解决一种问题的算法毕竟用处有限,而D&C提供了解决问题的思路,是另一个可供你使用的工具。 D&C...

YanceyOfficial 2019-07-31 10:14 评论0 收藏0
【算法】算法图解笔记_递归

递归是个有意思的概念，正如在前面所说，递归能让算法的可读性大大提高，而且通常要比使用循环结构更能写出准确的算法。这本书形象引入了递归，并没有太深入，所以我进行了一点添油加醋。递归概念递归其实就是自己调用自己。可以从多种维度对递归分类，我见过的最常见的分类：直接递归自己直接调用自己。如： --haskell length :: [a] -> Int length [] = 0 length...

tomlingtm 2019-07-31 10:12 评论0 收藏0
【算法】计数排序 + 各个排序算法的稳定性

摘要：将大的先放在后面，再下一次可以把相同大的放在上一次的之前，顺序改变。之前介绍的排序算法：【算法】插入排序——希尔排序+直接插入排序_Rinne’s blog-C...

不知名网友 2021-11-29 10:50 评论0 收藏0