数据结构与算法Day5

数据结构与算法Day5 排序算法

是一种能将一串数字按照顺序（升序或者降序）排列的算法
排序算法的稳定性
指的是两个等值的数R、S在排序时会不会改变原来的顺序，不改变则证明该算法是稳定的，否则则不稳定。

冒泡排序

重复遍历需要排序的数列，但每次只比较两个数，将大的数排到后一个位置上，这样反复排序，最后会将整个数列最大的数字排到数列的最后一个位置。下一次排序时则不比较最后一个数，比较第一个数到倒数第二数，这样反复循环，直到排序到第一对数。
比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
最优情况下，其排序时间复杂度为O(n)
最坏情况下，其时间复杂度为O(n^2)

在Python中实现

def bubble_sort(alist):
    '''冒泡排序'''
    n = len(alist) #排序序列长
    for j in range(0,n-1): #每次排序完将会少一个数进行比较
    #最优化冒牌排序的设置 设置计数 在一次循环里 如果整个序列为顺序 则不计数 不计数直接跳出循环
        count = 0
        for i in range(0,len(alist)-1-j):
            # 从头遍历到尾部
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
                count += 1
        if 0 == count: #发现排序好了 无需进行排序 直接返回
            return

选择排序

在排序时，会将序列分成两部分，第一部分是已经排序的数列，第二部分是未排序的数列，在排序时，选择排序会在未排序的数列中跳出最小的数列放在已排序数列的尾部，这样反复循环直到最后一个数字被排序。
选择排序的优点在于数据移动，如果某个元素在正确位置上，则不会被移动。每次作一对数据的位置交换时，至少有一个数据是会被移到最终位置上的，因此，对n个元素的表进行排序总共进行至多n-1次排序
时间复杂度均为O(n^2)
不稳定，在降序排列时会改变同值数之间的顺序

在Python中实现

def select_sort(alist):
    '''选择排序'''
    n = len(alist)
    for j in range(0,n-1): #每次确定一个位置，下次确定的将会是这次的+1
        min_index= j
        for i in range(j+1,n): #将这次确定的位置提出，在未排序的数列中比较出最小的数
            if alist[min_index] > alist[i]:
                min_index = i #更新索引
        alist[j],alist[min_index] = alist[min_index],alist[j] # 更新数的位置

插入排序

与选择排序类似，但插入排序 *** 作的是未排序数列。在未排序的数列中抽出一个数，与排序的数列进行比较，从后往前进行寻找，找到其该插入的位置
时间复杂度：
在最优情况下，为O(n)
在最坏情况下，时间复杂度为O(n^2)
稳定
在Python中实现

def insert_sort(alist):
    '''插入排序'''
    n = len(alist)
    #从右边无序序列中取出多少个元素执行这样的过程 每次会缩减1个
    for j in range(1,n):
        #i代表内层循环起始值
        i = j
        #执行从右边的无序序列取出第一个元素 即i位置的元素 然后将其插入到前面正确的位置中 不断与有序序列进行比较
        while i > 0: #如果i在头部位置时 不再进行比较
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i]
                i -= 1 #不断往前比较
            else:#优化算法 在已经确定位置时，不再向前比较
                break