[数据结构与算法]python数据结构——（5）查找与排序

查找

• 顺序查找
  顺序查找，就是从列表List[0]开始，逐个比对item与List[n]的大小，直到找到item。找不到则返回False。

无序表实现代码：

# 无序表查找
def seqentialSearch(alist, item):
    pos = 0
    found = False
    
    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos += 1
            
    return found

有序表实现代码：

# 有序表查找
def orderSeqentialSearch(alist, item):
    pos = 0
    found = False
    stop = False
    
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos += 1
    return found

• 二分查找
  二分法利用的是有序表的特性。从数据的中间一项分为左、右两个部分,如果item比中间的值大，则在右边的列表；反之，则在左边的列表中。再按相同的方式一直执行程序，知道找到，返回True，否则返回False。

实现代码:

def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    
    while first < last and not found:
        midpoint = (first + last) //2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint-1
            if item > alist[midpoint]:
                first = midpoint+1
                
    return found

从上面的算法规则可以看出，二分法也适合用递归的方式实现：

def binarySearch_re(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch_re(alist[: midpoint], item)
            if item > alist[midpoint]:
                return binarySearch_re(alist[midpoint+1:], item)
    

testlist = [1, 34, 54, 32, 54, 78]
print(binarySearch_re(testlist, 54))
print(binarySearch_re(testlist, 22))

排序

经过查找资料，大概可能有八大排序算法，在这里我介绍几种常见的排序算法。

为了方便大家理解，这里为大家找到各类排序算法的动画各类算法动画演示。

• 冒泡排序
  冒泡排序作为最经典的排序方式之一，实现原理如下：

从列表的第一个元素开始，向右与相邻的元素比较，将大的放在右侧，依次进行，这样在长度为N的列表中，比较N-1次，最大的元素就放在了列表的最右侧，将其左侧的N-1个元素按照相同的方式操作，直到最后比较一次，完成排序算法。

实现代码如下:

def bubbleSort(alist):
    # n-1 趟  n-1~1
    for passnum in range(len(alist)-1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp
                # 一行直接替换
                # alist[i], alist[i+1] = alist[i+1], alist[i]

• 选择排序
  选择排序是在冒泡排序的基础上进行修改的，特点是：每一趟将最大项的位置记录下来，与最后一项进行交换，这样就实现了每趟只作一次交换。

实现代码：

def selectSort(alist):
    for fillsolt in range(len(alist)-1, 0, -1):
        positionOfMax = 0
        for location in range(0, fillsolt+1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        alist[fillsolt], alist[positionOfMax] = alist[positionOfMax], alist[fillsolt]

• 插入排序
  将数据分成左右两部分，左边永远是排好序的，右边是未排好序的。

算法思路：
第一趟：子列表仅包含第一个数据项，然后插入第二个data;
第二趟：再继续将第三个数据项跟前两个数据项比对，并移动比data_3大的数据项空出位置，将data_3插入空位；
最后经过n-1趟对比和插入，子列表扩展到全表，排序完成。

实现代码：

def insertionSort(alist):
    for index in range(1, len(alist)):
        # 新项/插入项
        currentvalue = alist[index]
        position = index
        
        # 比对、移动
        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            position = position -1
            
        # 插入新项    
        alist[position] = currentvalue

• 归并排序
  归并排序属于递归算法，它将无序表分裂成两半，两半又分别再分成两半，一直进行下去，最后比较剩下的单个元素。

实现代码：

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        
        mergeSort(lefthalf)
        mergeSort(righthalf)
        
        i= j = k= 0
        # 拉链式交错把左右半部从小到大归并到列表中
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1
            
        # 归并左半部剩余项
        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i += 1
            k += 1
            
        # 归并右半部剩余项
        while j < len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1

上述代码可以在c/c++、java等语言直接改写，下面编写python风格的归并排序算法：

# python 风格的归并排序
def merge_sort(lst):
    if len(lst) < 1:
        return lst
    # 分解问题，并递归调用
    middle = len(lst) // 2
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    
    # 合并左右半部，完成排序
    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    
    # 有剩下的放在后边
    merged.extend(right if right else left)
    return merged

• 快速排序
  实现原理：依据一个“中值”，将列表分成两半：小于中值的一半和大于中值的一半。

在这里注意，需要设置左/右标：

• 左标：向右走，当比中值大的时候，stop；
• 右标：向左走，比中值小的时候，stop。此时要交换左右标的data。
• 当左标移动到右标的右端时，stop。此时右标的位置就是中值。

实现代码：

# 快速排序
def quickSort(alist):
    quickSortHelper(alist, 0, len(alist)-1)
    
def quickSortHelper(alist, first, last):
    if first < last:
        # 分裂
        splitpoint = partition(alist, first, last)
        quickSortHelper(alist, first, splitpoint-1)
        quickSortHelper(alist, splitpoint+1, last)
        
def partition(alist, first, last):
    # 选定“中值”
    pivotvalue = alist[first]
    
    leftmark = first + 1
    rightmark = last
    
    done = False
    while not done:
        # 左标右移
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1
            
        # 右标左移
        while alist[rightmark] >= pivotvalue and rightmark > leftmark:
            rightmark -= 1
            
        # 两标相错就移动结束
        if rightmark < leftmark:
            done = True
        else:
            # 左右标的值互换
            alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]
            
    # 中值就位
    alist[first], alist[rightmark] = alist[rightmark], alist[first]
    
    # 中值点，也是分裂点
    return rightmark