2 选择排序

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

:::warning O(n) = 线性时间
O(1) = 常量时间 ::: | | 数组 | 链表 | | —- | —- | —- | | 读取 | O(1) | O(n) | | 插入 | O(n) | O(1) | | 删除 | O(n) | O(1) |

算法图解 - 图1

算法 — 快速排序

  1. // 将数组元素按从小到大的顺序排列。先编写一个用于找出数组中最小元素的函数。
  3. def findSmallest(arr):
  4.     smallest = arr[0]   // 存储最小的值
  5.     smallest_index = 0  // 存储最小元素的索引
  7.     for i in range(1, len(arr)):
  8.         if arr[i] < smallest:
  9.             smallest = arr[i]
  10.             smallest_index = i
  11.     return smallest_index
  13. // 使用这个函数来编写选择排序算法
  15. def selectionSort(arr):  // 对数组进行排序
  16.     newArr = []
  17.     for i in range(len(arr)):
  18.         smallest = findSmallest(arr)   // 找出数组中最小的元素
  19.         newArr.append(arr.pop(smallest)) // 将其加入到新数组中
  20.     return newArr
  22. print selectionSort([5, 3, 6, 2, 10])

1 算法简介

算法图解 - 图2

算法 — 二分查找

  1. 函数binary_search接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个
  2. 函数将返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组。
  4. def    binary_search(list,item):
  5.     //low-high是要查找的范围
  6.     //low和high用于跟踪要在其中查找的列表部分
  7.     low=0
  8.     high=len(list)-1
  9.     //只要范围没有缩小到只包含一个元素，就检查中间的元素
  10.     while    low    <=    high:
  11.             mid    =    (low+high)/2
  12.             guess=    list[mid]
  13.             //找到了元素
  14.             if    guess    ==    item:
  15.                 return    mid
  16.             //猜的数字大了
  17.             if    guess    >    item:
  18.                 high    =mid    -1
  19.                 //猜的数字小了
  20.             else:    
  21.                 low    =    mid    +1
  22.    //没有指定的元素             
  23.    return    None
  25.             my_list = [1, 3, 5, 7, 9]
  26.         //索引从0开始，第二个位置的索引为1
  27.             print binary_search(my_list, 3) # => 1
  28.         //在Python中，None表示空，意味着没有找到指定的元素
  29.             print binary_search(my_list, -1) # => None