hyman-海曼工具

一些简单的记录

0%

Python基本算法

发表于 更新于 分类于

时间复杂度

用来评估算法运行效率的一个东西

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def func():
    print("hello world")
 
def func1(n):
    for i in range(n):
        print("hello world")
 
def func2(n):
    for i in range(n):
        for j in range(n):
            print("hello world")
 
def func3(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print("hello world")

时间复杂度分别为：O(1),O(n),O(n^2),O(n^3)

特殊的时间复杂度

1
2
3
4
5
6
def func4(n):
    while n >1:
        print(n)
        n = n//2

时间复杂度叫O(logn)

时间复杂度是用来估计算法运行时间的一个式子（单位）

一般来说，时间复杂度高的算法比复杂度低的算法慢

常见的时间复杂度（按效率排序）

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n*nlogn)<O(n^3)

通常简单的判断时间复杂度的方法：

循环减半的过程——O(logn)

基层循环就是n的几次方的复杂度

空间复杂度

用来评估算法内存占用大小的一个式子

算法

二分查找

二分查找又叫折半查找，二分查找应该属于减治技术的成功应用。所谓减治法，就是将原问题分解成若干个子问题后，利用了规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间的关系。
二分查找利用了记录按关键码有序的特点，其基本思想为：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半边继续查找；若给定值大于中间记录的关键码，则在中间记录右半边区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。
二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)。

1
2
3
4
5
6
7
在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1
样例
给出数组 [1, 2, 2, 4, 5, 5].

对于 target = 2, 返回 1 或者 2.
对于 target = 5, 返回 4 或者 5.
对于 target = 6, 返回 -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#!/usr/bin/python
#coding=utf-8

#自定义函数，实现二分查找，并返回查找结果
def binary_search(find, list1) :
  low = 0
  high = len(list1)
  while low <= high :
    mid = (low + high) / 2
    if list1[mid] == find :
      return mid
    #左半边
    elif list1[mid] > find :
      high = mid -1
    #右半边
    else :
      low = mid + 1
  #未找到返回-1
  return -1

list1 = [1,2,3,7,8,9,10,5]
#进行二分查找算法前必须保证要查找的序列时有序的，这里假设是升序列表
list1.sort()

print "原有序列表为:",list1
try :
  find = int(raw_input("请输入要查找的数："))
except :
  print "请输入正整数！"
  exit()

result = binary_search(find, list1)
if result != -1 : 
  print "要找的元素%d的序号为：%d" %(find,result)
else :
  print "未找到！"

排序

插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
list = [55,45,345,6,7,2,88,53,12,889,21]
print list

def insert_sort(list):
        count = len(list)
        for i in range(1,count):
                k = list[i]
                #print i
                #print k
                j = i -1
                #print list[j]
                while j >= 0:
                        if list[j] >k:
                                list[j+1]=list[j]
                                list[j]=k
                        j -=1
                        #print list
        return list
print insert_sort(list)

冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
每一趟只能将一个数归位, 如果有n个数进行排序,只需将n-1个数归位, 也就是说要进行n-1趟操作(已经归位的数不用再比较)
缺点: 冒泡排序解决了桶排序浪费空间的问题, 但是冒泡排序的效率特别低

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python
# coding:utf-8

def bubbleSort(nums):
    for i in range(len(nums)-1):    # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(nums)-i-1):  # ｊ为列表下标
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

nums = [5,2,45,6,8,2,1]

print bubbleSort(nums)

选择排序

基本思想：第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/env python
# coding:utf-8

def selectSort(nums):
    for i in range(len(nums)):
        max_index = 0
        for j in range(len(nums)-i):
            if nums[max_index] < nums[j]:
                max_index = j
        nums[max_index], nums[len(nums)-i-1] = nums[len(nums)-i-1], nums[max_index]
    return nums

nums = [6,2,54435,3141]
print selectSort(nums)

桶排序

通排序非常浪费空间, 比如需要排序的范围在0~2000之间, 需要排序的数是[3,9,4,2000], 同样需要2001个空间

注意: 通排序不能排序小数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env python
# coding:utf-8

def bucketSort(nums):
    # 选择一个最大的数
    max_num = max(nums)
    # 创建一个元素全是0的列表, 当做桶
    bucket = [0]*(max_num+1)
    # 把所有元素放入桶中, 即把对应元素个数加一
    for i in nums:
        bucket[i] += 1

    # 存储排序好的元素
    sort_nums = []
    # 取出桶中的元素
    for j in range(len(bucket)):
        if bucket[j] != 0:
            for y in range(bucket[j]):
                sort_nums.append(j)

    return sort_nums

nums = [5,6,3,2,1,65,2,0,8,0]
print bucketSort(nums)

希尔排序

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env python
# coding:utf-8

def shellSort(nums):
    # 设定步长
    step = len(nums)/2
    while step > 0:
        for i in range(step, len(nums)):
            # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
            while i >= step and nums[i-step] > nums[i]:
                nums[i], nums[i-step] = nums[i-step], nums[i]
                i -= step
        step = step/2
    return nums


if __name__ == '__main__':
    nums = [9,3,5,8,2,7,1]
    print shellSort(nums)