[数据结构与算法]数据结构5-排序与选择

5 排序与选择

• 排序算法的稳定性

  相等的值不该改变记录次序

5-1 冒泡排序

Bubble Sort

一次比较两个元素，如果他们的顺序错误就把他们交换过来。

遍历数列 直到没有再需要交换。

步骤

1. 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

实现

def bubble_sort(alist):
    '''冒泡排序'''

    for j in range(len(alist)-1,0,-1):
    # 产生了(n-1)个数：0~(n-2)
    # j表示每次遍历需要比较的次数，是逐渐减小的
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)

最优版

def bubble_sort(alist):
    '''冒泡排序'''
    n = len(alist)
    for j in range(n-1,0,-1):
        count = 0
    # 产生了(n-1)个数：0~(n-2)
    # j表示每次遍历需要比较的次数，是逐渐减小的
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count += 1
        if count == 0:
        # 如果有序 就不用再走了
            return

li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)

时间复杂度

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n^2)
• 稳定性：稳定

5-2 选择排序

Selection sort

步骤

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾（前一个排好的元素的后面）。
3. 以此类推，直到所有元素均排序完毕。

实现

def selection_sort(alist):
    n = len(alist)
    # 需要进行n-1次选择操作
    for i in range(n-1):
        # 记录最小位置
        min_index = i
        
        
        # 从i+1位置到末尾选择出最小数据
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
                
        # 如果选择出的数据不在正确位置，进行交换
        if min_index != i:
            alist[i], alist[min_index] = alist[min_index], alist[i]

alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)

时间复杂度

• 最优时间复杂度：O(n2)
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定

eg. li = [(26,2),16,7,5,15,(26,1),11,9]

若从0开始，(26,2)被排到了最大值的位置（即9的位置）
而原先是(26,1)的index大于(26,2)

破坏了原来的次序，所以不稳定

5.3 插入排序

Insertion Sort

1. 认为前面的序列是有序的，让后面序列的第一个和前面有序序列的元素比较。
2. 直到把这个元素插入到前面序列的正确位置上。
3. 循环到所有元素排完。

实现

def insert_sort(alist):
    # 从第二个位置，即下标为1的元素开始向前插入
    n = len(alist)
    for i in range(1, n):
        # 从第i个元素开始向前比较，如果小于前一个元素，交换位置
        for j in range(i, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]
            else:
                # 本来就是有序序列 就不用循环了
                break

alist = [54,26,93,17,77,31,44,55,20]
insert_sort(alist)
print(alist)

时间复杂度

• 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
• 最坏时间复杂度：O(n2)
• 稳定性：稳定

5.4 希尔排序

Shell sort

改良版插入排序

gap = 1,相当与插入排序；由gap影响时间复杂度

步骤

1. 以步长开始打断（换行）
2. 按列（纵向）进行排序
3. 重复以上两步 到步长为1 成为了插入排序

实现

def Shellsort(alist):
    '''希尔排序'''
    gap = len(alist)//2 # 取一半，舍去小数部分

    # gap变化到0之前，插入算法执行的次数
    while gap >= 1:

        # 起始值改为gap（与插入相比）
        for j in range(gap,n):
            # j=[gap,gap+1,...,n-1]
            i = j

            while i>0:
                # 步长为gap 非1（与插入相比）
                if alist[i] < alist[i-gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                else:
                    break

        # 缩短gap步长
        gap //= 2

时间复杂度

• 最优时间复杂度：根据步长序列的不同而不同
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定

5.5 快速排序

quick sort

步骤

1. 两个指针 high low
2. 两边只能有一个指针在走，走到不符合要求的停下来；另一个指针走
3. 另一个也不符合了停下来；两个指针交换位置
4. 然后数列被分成了两个部分
5. 再对两部分 分别重复以上操作

实现

# coding utf-8
# v1_easy

def quick_sort(alist,first,last):
    ''''快速排序'''
    if first >= last:
        return
    mid_value = alist[first]
    low = first
    high = last

    ''' 找到正确的 mid_value '''
    # low和high没有相遇，下面两个循环交替进行
    while low < high:
        # high 左移
        # 等于mid_value的情况 放到一边来处理（符合分割线的思想）
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]

        # low右移
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
        # 推出循环时 high=low
        alist[low] = mid_value

    ''' 递归，完成排序 '''
    # 对low左边的列表快排
    quick_sort(alist,first,low-1) # 不能用切片 因为[:]传的是一个新列表
    # 对low右边的列表快排
    quick_sort(alist,low+1,last)

'''测试'''
if __name__ == "__main__":
    li = [54,26,93,17,77,31,55,20]
    print(li)
    n = len(li)
    quick_sort(li,0,n-1)
    print(li)

RecursionError: maximum recursion depth exceeded in comparison
超过最大递归深度，没有循环的结束条件

时间复杂度

• 最优时间复杂度：O(nlogn)

纵向是logn 横向是n，不懂！

• 最坏时间复杂度：O(n2)
• 稳定性：不稳定

5.6 归并排序

merge sort

实现

def merge_sort(alist):
    ''''归并排序'''

    n = len(alist)
    if n <= 1:
        return alist
    mid = n//2
    # 采用归并排序后新的有序的子列表
    left_l = merge_sort(alist[:mid]) # 传入的是新的列表（子序列）
    right_l = merge_sort(alist[mid:])

    # 将两个有序的子序列 合并成一个新的整体
    left_pointer = 0
    right_pointer = 0
    result = [] # 存放结果

    while left_pointer < len(left_l) and right_pointer < len(right_l):
        if left_l[left_pointer] < right_l[right_pointer]:
            result.append(left_l[left_pointer])
            left_pointer += 1
        else:
            result.append(right_l[right_pointer])
            right_pointer += 1

    # 合并排序后的结果
    result += left_l[left_pointer:]
    result += right_l[right_pointer:]

    return result

时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 稳定性：稳定

5.7 二分查找

二分查找又称折半查找。

处理的要求是排序后的结果。

• 优点：比较次数少，查找速度快，平均性能好
• 缺点：要求待查表为有序顺序表，且插入删除困难。
• 适用：不经常变动而查找频繁的有序列表。

# ''''递归实现'''
# def binary_search(alist,item):
#     '''二分查找法'''
#     n = len(alist)
#     if n>0:
#         mid = n//2
#         if alist[mid] == item:
#             return True
#         elif item < alist[mid]:
#             return binary_search(alist[:mid], item)
#         else:
#             return binary_search(alist[mid+1:], item)
#     return False


''''非递归实现'''
def binary_search(alist,item):
     '''二分查找法'''
     n = len(alist)
     first = 0
     last = n-1
     while first <= last:
         mid = (first+last)//2
         if alist[mid] == item:
                 return True
         elif item < alist[mid]:
             last = mid - 1
         else:
             first = mid + 1
     return False

'''测试'''
if __name__ == "__main__":
     li = [54,26,93,17,77,31,55,20]

     print(binary_search(li, 55))
     print(binary_search(li, 100))
     
'''结果'''    
# True
# False
     
     

时间复杂度

• 最优时间复杂度：O(1)
• 最坏时间复杂度：O(logn)