python中排序和查找的基础算法

一、排序算法 1、交换变量

        交换变量比其他语言要省事得多。

var1 = 1
var2 = 2
var1,var2 = var2,var1
print(var1,var2)

2、冒泡排序

        由于存在两层循环，最坏情况下的运行时复杂度是O(n2)。

# 声明数组
list = [25,21,22,24,23,27,26]

# 定义排序方法
def BubbleSort(list):
    # Excahnge the elements to arrange in order
    lastElementIndex = len(list)-1
    for passNo in range(lastElementIndex,0,-1):
        for idx in range(passNo):
            if list[idx]>list[idx+1]:
                list[idx],list[idx+1]=list[idx+1],list[idx]
    return list

# 进行排序
InsertionSort(list)

3、插入排序

        插入排序的基本思想是，在每次迭代中，都会从数据集中移除一个数据点，然后将其插入到正确的位置，这就是为什么将其称为插入排序算法。

def InsertionSort(list):
    for i in range(1, len(list)):
        j = i-1
        next = list[i]
        # Compare the current element with next one
    
        while (list[j] > next) and (j >= 0):
            list[j+1] = list[j]
            j=j-1
        list[j+1] = next
    return list

4、归并排序

        该算法的主要特点是，其性能不取决于输入数据是否已排序。同MapReduce和其他大数据算法一样，归并排序算法也是基于分治策略而设计的。

def MergeSort(list):
    if len(list)>1:
        mid = len(list)//2 #splits list in half
        left = list[:mid]
        right = list[mid:]

        MergeSort(left) #repeats until length of each list is 1
        MergeSort(right)

        a = 0
        b = 0
        c = 0
        while a < len(left) and b < len(right):
            if left[a] < right[b]:
                list[c]=left[a]
                a = a + 1
            else:
                list[c]=right[b]
                b = b + 1
            c = c + 1
        while a < len(left):
            list[c]=left[a]
            a = a + 1
            c = c + 1

        while b < len(right):
            list[c]=right[b]
            b = b + 1
            c = c + 1
    return list

5、希尔排序

        希尔排序并不适用于大数据集，它用于中型数据集。粗略地讲，它在一个最多有6000个元素的列表上有相当好的性能，如果数据的部分顺序正确，则性能会更好。在最好的情况下，如果一个列表已经排好序，则它只需要遍历一次N个元素来验证顺序，从而产生O(N)的最佳性能。

def ShellSort(list):
    distance = len(list) // 2
    while distance > 0:
        for i in range(distance, len(list)):
            temp = list[i]
            j = i
            # Sort the sub list for this distance
            while j >= distance and list[j - distance] > temp:
                list[j] = list[j - distance]
                j = j-distance
            list[j] = temp
        # Reduce the distance for the next element
        distance = distance//2
    return list

6、选择排序

        选择排序的最坏时间复杂度是O(N2)。请注意，其最坏性能近似于冒泡排序的性能，因此不应该用于对较大的数据集进行排序。不过，选择排序仍是比冒泡排序设计更好的算法，由于交换次数减少，其平均复杂度比冒泡排序好。

def SelectionSort(list):
    for fill_slot in range(len(list) - 1, 0, -1):
        max_index = 0
        for location in range(1, fill_slot + 1):
            if list[location] > list[max_index]:
                max_index = location
        list[fill_slot],list[max_index] = list[max_index],list[fill_slot]
    return list

二、查找算法 1、线性查找

        查找数据的最简单策略就是线性查找，它简单地遍历每个元素以寻找目标。

def LinearSearch(list, item):
    index = 0
    found = False

    # Match the value with each data element       
    while index < len(list) and found is False:
        if list[index] == item:
            found = True
        else:
            index = index + 1
    return found

list = [12, 33, 11, 99, 22, 55, 90]
print(LinearSearch(list, 12))
print(LinearSearch(list, 91))

        线性查找是一种执行穷举搜索的简单算法，其最坏时间复杂度是O(N)。

2、二分查找

        二分查找算法的前提条件是数据有序。算法反复地将当前列表分成两部分，跟踪最低和最高的两个索引，直到找到它要找的值为止。

def BinarySearch(list, item):
    first = 0
    last = len(list)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if list[midpoint] == item:
            found = True
        else:
            if item < list[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
    return found


list = [12, 33, 11, 99, 22, 55, 90]
sorted_list = BubbleSort(list)
print(BinarySearch(list, 12))
print(BinarySearch(list, 91))

        二分查找在每次迭代中，算法都会将数据分成两部分。如果数据有N项，则它最多需要O(log N)步来完成迭代，这意味着算法的运行时间为O(log N)。 

 3、插值查找

        二分查找的基本逻辑是关注数据的中间部分。插值查找更加复杂，它使用目标值来估计元素在有序数组中的大概位置。

def IntPolsearch(list,x ):
    idx0 = 0
    idxn = (len(list) - 1)
    found = False
    while idx0 <= idxn and x >= list[idx0] and x <= list[idxn]:

        # Find the mid point
        mid = idx0 +int(((float(idxn - idx0)/( list[idxn] - list[idx0])) * ( x - list[idx0])))

        # Compare the value at mid point with search value 
        if list[mid] == x:
            found = True
            return found

        if list[mid] < x:
            idx0 = mid + 1
    return found

list = [12, 33, 11, 99, 22, 55, 90]
sorted_list = BubbleSort(list)
print(IntPolsearch(list, 12))
print(IntPolsearch(list,91))

        如果数据分布不均匀，则插值查找算法的性能会很差，该算法的最坏时间复杂度是O(N)。如果数据分布得相当均匀，则最佳时间复杂度是O(log(log N))。

4、深度优先搜索

# 深度优先dfs算法
def dfs(aGraph, root): 
    stack = [root] 
    parents = {root: root} 
    path = list 
    while stack: 
        print ('Stack is: %s' % stack) 
        vertex = stack.pop(-1) 
        print ('Working on %s' % vertex) 
        for element in aGraph[vertex]: 
            if element not in parents: 
                parents[element] = vertex 
                stack.append(element)
                print ('Now, adding %s to the stack' % element) 
                path.append(parents[vertex]+'>'+vertex) 
    return path[1:] 


# 构造树
g = dict() 
g['Amine'] = ['Wassim', 'Nick', 'Mike','Elena'] 
g['Wassim'] = ['Amine', 'Imran'] 
g['Nick'] = ['Amine'] 
g['Mike'] = ['Amine', 'Mary'] 
g['Elena'] = ['Amine'] 
g['Imran'] = ['Wassim', 'Steven'] 
g['Mary'] = ['Mike']
g['Steven'] = ['Imran']

#查找Amine
dfs(g,"Amine")