美文网首页
排序算法总结

排序算法总结

作者: IreneWu | 来源:发表于2018-03-01 20:22 被阅读12次

    冒泡排序(Bubble sort)

    是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    冒泡排序算法的运作如下:
    • 比较相邻的元素。如果第一个比第二个大(升序),就交换他们。
    • 对每一个相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
    • 针对所有的元素重复以上的步骤,除了最后一个。
    • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
    时间复杂度
    • 最优:O(n)(表示遍历一次发现没有任何可以交换的元素,排序结束。)
    • 最坏:O(n²)
    • 稳定性:稳定
    def bubble_sort(alist):
        """冒泡排序"""
        n = len(alist)
        #for j in range(n-1,0,-1):
        #    for i in range(j):
        for j in range(n-1):
            # 记录是否交换过
            count = 0
            for i in range(0, n - 1 - j):
                # 班长从头走到尾
                if alist[i] > alist[i+1]:
                    alist[i],alist[i+1] = alist[i+1],alist[i]
                    count += 1
            if count == 0:
                return 
    

    选择排序(Selection sort)

    是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
    选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

    时间复杂度
    • 最优:O(n²)
    • 最坏:O(n²)
    • 稳定性:不稳定(考虑升序每次选择最大的情况)
    def select_sort(alist):
        """选择排序"""
        n = len(alist)
        for j in range(n-1): # j: 0 ~ n-2
            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]
    

    插入排序(Insertion sort)

    是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

    时间复杂度
    • 最优:O(n)(升序排列,序列已经处于升序状态)
    • 最坏:O(n²)
    • 稳定性:稳定
    def insert_sort(alist):
        """插入排序"""
        n = len(alist)
        # 从右边的无序序列中取出多少个元素执行这样的过程
        for j in range(1, n): # j : 1 ~ n-1
            # i 代表内层循环的起始值
            i = j
            # 执行从右边的无序序列中取出第一个元素,即i位置的元素,然后将其插入到前面的正确位置中
            while i > 0:
                if alist[i] < alist[i-1]:
                    alist[i], alist[i-1] = alist[i-1], alist[i]
                    i -= 1
                else:
                    break
    

    希尔排序(Shell sort)

    是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    时间复杂度
    • 最优:O(n1.3)
    • 最坏:O(n²)
    • 稳定性:不稳定
    def shell_sort(alist):
        # n = 9
        n = len(alist)
        # gap = 4
        gap = n // 2
        # gap变化到0之前,插入算法执行的次数
        while gap > 0:
            # 插入算法,与普通的插入算法的区别就是gap步长
            for j in range(gap, n):
                # j = [gap, gap+1, gap+2, ..., n-1]
                i = j
                while i > 0:
                    if alist[i] < alist[i - gap]:
                        alist[i], alist[i - gap] = alist[i - gap], alist[i]
                        i -= gap
                    else:
                        break
    
            gap //= 2
    

    快速排序(Quick sort)

    是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    快速排序的基本思想是:
    1. 先从数列中取出一个数作为基准数
    2. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
    3. 再对左右区间重复第二步,直到各区间只有一个数
    时间复杂度
    • 最优:O(nlogn)
    • 最坏:O(n²)
    • 稳定性:不稳定
    def quick_sort(alist, first, last):
        """快速排序"""
        # 递归退出条件
        if first >= last:
            return
        mid_value = alist[first]
        low = first
        high = last
    
        while low < high:
            # high 左移
            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]
        # 从循环退出时,low == high
        alist[low] = mid_value
    
        # 对low左边的列表执行快速排序
        quick_sort(alist, first, low - 1)
    
        #  对low右边的列表执行快速排序
        quick_sort(alist, low + 1, last)
    

    归并排序(Merge sort)

    是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。
    将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

    时间复杂度
    • 最优:O(nlogn)
    • 最坏:O(nlogn)
    • 稳定性:稳定
    def merge_sort(alist):
        """归并排序"""
        n = len(alist)
        if n<= 1:
            return alist
        mid = n//2
    
        # left 采用归并排序后形成的有序的新的列表
        left_li = merge_sort(alist[:mid])
    
        # right 采用归并排序后形成的有序的新的列表
        right_li = merge_sort(alist[mid:])
    
        # 将两个有序的子序列合并为一个新的整体
        left_pointer, right_pointer = 0, 0
        result = []
    
        while left_pointer < len(left_li) and right_pointer < len(right_li):
            if left_li[left_pointer] <= right_li[right_pointer]:
                result.append(left_li[left_pointer])
                left_pointer += 1
            else:
                result.append(right_li[right_pointer])
                right_pointer += 1
    
        result += left_li[left_pointer:]
        result += right_li[right_pointer:]
        return result
    

    相关文章

      网友评论

          本文标题:排序算法总结

          本文链接:https://www.haomeiwen.com/subject/zswwxftx.html