上篇文章介绍了大O表示方法和5种常见算法的大O表示时间,本篇文章主要对二分法查找、选择排序、快速排序算法进行了实现。
1 二分法查找
二分法查找是一种速度非常快的算法,但是它有固定的应用范围。仅当列表是有序的时候,二分查找才管用。例如,电话簿中的名字是按照顺序排列的,因此可以使用二分查找来找名字。二分法查找需要执行log n 次操作,大O表示法为 O(log n)。
算法问题描述:
函数binary_search接受一个有序数组和元素。如果指定的元素包含在数组中,如何编写函数binary_search返回元素的位置。
算法实现:
二分查找每次都检查中间元素,比较中间元素与查询元素的大小,不断缩小查询区域
#二分法查找(python代码)
def binary_search(list,item):
low = 0
high = len(list) -1
while low <= high:
mid = (low + high)/2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [1,3,5,7,9]
print binary_search(my_list,3)
1 #返回值
print binary_search(my_list,-1)
None #返回值
2 选择排序
有很多算法只有经过排序后的数据才能使用,例如上部分介绍的二分法查找。排序是最基础、最重要的算法之一,很多编程语言都内置了排序算法,基本上不需要你从头开始编写自己的版本。但是,对基础排序算法的学习是掌握其他重要算法的基础。本部分介绍的选择排序算法就是一种最简单的排序算法。选择性排序需要执行n+(n-1)+(n-2)+...+2+1次操作,大O表示法为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
print selectionSort([5,3,6,3,6,2,1])
[1, 2, 3, 3, 5, 6, 6] #返回值
3 快速排序
选择排序的大O表示法为O(n2),快速排序排序的大O表示法为O(n log n)。快速排序的速度是选择排序的n/logn倍。快速排序主要是应用了分而治之(divide and conquer, D&C)——一种著名的递归式的问题解决方法。
使用 D&C 解决问题主要包括两个步骤:
(1)找出基线条件,这种基线条件必须尽可能的简单。(注意:递归函数的基线条件通常是数组为空或者只包含一个元素)
(2)不断将问题分解(或者说缩小规模),直到符合基线条件。
算法问题描述:
函数 quicksort 接受一个无序列表。如何编写函数 quicksort 对列表中的元素进行快速排序。
算法实现:
快速排序 D&C 策略(如下图所示):
1 、快速排序的基线——列表为空或者只有一个元素的列表是天然“有序”的列表
2、快速排序问题分解:(1)选择基准值(2)将数组分成两个子列表:小于基准值的列表和大于基准值的列表(3)对两个子列表再进行快速排序
快速排序的代码还是比较优雅的!
#快速排序(python代码)
def quicksort(array):
if len(array) < 2:
return array #基线条件
else:
#递归条件
pivot = array[0] #选取基准值
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([2,3,6,8,1,2])
[1, 2, 2, 3, 6, 8] #返回值
4 冒泡排序
冒泡排序和选择排序的思路比较类似,大O表示法为O(n2)。它的思路为:
1、比较相邻的元素,如果第一个比第二个大,就交换他们两个
2、对每一对儿相邻的元素做同样的工作,执行完毕后,找到第一个最大值
3、重复以上的步骤,每次比较次数 - 1,直到不需要比较
//冒泡排序 C++代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
int arr[] = { 4,2,8,0,5,7,3,9 };
//总共排序的轮数为:元素个数 - 1
for (int i = 0; i < 9 - 1; i++) {
//内层循环次数:元素个数 - 当前轮数 -1
for (int j = 0; j < 9 - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int i = 0; i < 9; i++) {
cout << arr[i] << endl;
}
}
参考资料
1、《算法图解》
网友评论