你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

超详细讲解-十大经典排序算法-未完

2021-11-1 17:56:02

文章目录

  • 0. 排序算法介绍
    • 0.1 内部排序和外部排序
    • 0.2 比较排序和非比较排序
    • 0.3 稳定排序和非稳定排序
  • 1. 冒泡排序
    • 1.1 冒泡排序的思想
    • 1.2 冒泡排序的算法步骤
    • 1.3 冒泡排序的代码
    • 1.4 冒泡排序的复杂度分析
    • 1.5 冒泡排序的稳定性分析
  • 2. 选择排序
  • 3. 插入排序
  • 4. 希尔排序
  • 5. 归并排序
  • 6. 快速排序
  • 7. 堆排序
  • 8. 计数排序
  • 9. 桶排序
  • 10. 基数排序

今日份鸡汤:你战胜了苦难,它就是你的财富;
      苦难战胜了你,它就是你的屈辱。

0. 排序算法介绍

  排序算法是数据结构中最基本的算法,也是最经典的算法之一。
  排序算法有多种分类方法,如:内部排序和外部排序、比较排序和非比较排序、稳定排序和非稳定排序等。

0.1 内部排序和外部排序

  • 内部排序和外部排序:
    (1)内部排序:内部排序是数据记录在内存中进行排序。
    (2)外部排序:外部排序因为排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
  • 按照内部排序和外部排序进行分类:
    (1)内部排序:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序。
    (2)外部排序

0.2 比较排序和非比较排序

  • 比较排序和非比较排序:
    (1)比较排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。
    (2)非比较排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。
  • 按比较排序和非比较排序进行分类:
    (1)比较排序:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。
    (2)非比较排序:计数排序,基数排序,桶排序等。

0.3 稳定排序和非稳定排序

  • 稳定排序和非稳定排序
      排序算法的稳定性是:当元素列表中出现相等的元素时,相等元素的相对次序是否固定不变。如果相对次序固定不变,则排序算法是稳定的,反之就是不稳定的。
  • 按照稳定排序和非稳定排序进行分类:
    (1)稳定排序:冒泡排序,
    (2)非稳定排序

1. 冒泡排序

1.1 冒泡排序的思想

  冒泡排序的思想就是:从第一个数开始,两两进行比较,逆序时交换。经过一趟比较之后,最大的数会被交换到最后,即最大的数会沉底,类似于最大的水泡在池子最底层(反之,从大到小排序也是一样的原理)。然后接着对前n-1个记录重复上述过程,直到排序完毕,类似于冒泡过程。
  注意:在某趟排序的比较中,如果发现两两比较无一交换,则说明数组已经有序。

1.2 冒泡排序的算法步骤

(1)以从小到大排序为例:从第1个元素和第二个元素开始,比较相邻的两个元素,如果前一个比后一个大,就互相调换位置,否则保持原状。
(2)第2个元素与第3个元素比较,如果第2个元素比第3个元素大,就互相调换位置,否则保持原状。
(3)对每一对相邻的元素,重复上述“比较”与“交换”的过程,直到最后一对元素。此时最大的数字已经被交换到了最后,也就是说,最大的泡泡已经冒出来啦。
(注意哦,此时最大的泡泡已经冒出来了,就不需要参与下一步的比较与交换的排序过程了,下一步的任务是:让次大的泡泡冒出来。)
(4)同理,针对所有的元素(除了最大的数字不参与)开始进行第二轮的比较与交换的排序过程,找出次大的泡泡。
(5)持续每次对越来越少的元素重复上面的步骤,直到排序完成(没有任何一对数字需要比较)。
(6)注意:在某趟排序的过程中,如果发现两两比较没有一个需要交换的元素,这说明整个排列已经有序,不必进行到最后一轮剩下两个元素进行比较。

在这里插入图片描述
     从上图中就可以看出:冒泡排序属于稳定排序。

1.3 冒泡排序的代码

# coding:utf-8
'''
# @Method:冒泡排序
# @Author: wlhr62
'''
import os
import sys


class Solution:
    def BubbleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        for i in range(n):
            for j in range(0, n-i-1):
                if nums[j] > nums[j+1]:
                    # temp = nums[j]
                    # nums[j] = nums[j+1]
                    # nums[j+1] = temp
                    nums[j], nums[j+1] = nums[j+1], nums[j]
            print("第", i+1, "轮的排序结果:", nums)
        return nums
        

if __name__ == "__main__":
    nums = [50, 36, 66, 76, 95, 12, 25, 36]
    A = Solution()
    res = A.BubbleSort(nums)
    print("最后的排序结果:", res)
    

代码运行结果如下:

1 轮的排序结果: [36, 50, 66, 76, 12, 25, 36, 95]2 轮的排序结果: [36, 50, 66, 12, 25, 36, 76, 95]3 轮的排序结果: [36, 50, 12, 25, 36, 66, 76, 95]4 轮的排序结果: [36, 12, 25, 36, 50, 66, 76, 95]5 轮的排序结果: [12, 25, 36, 36, 50, 66, 76, 95]6 轮的排序结果: [12, 25, 36, 36, 50, 66, 76, 95]7 轮的排序结果: [12, 25, 36, 36, 50, 66, 76, 95]8 轮的排序结果: [12, 25, 36, 36, 50, 66, 76, 95]
最后的排序结果: [12, 25, 36, 36, 50, 66, 76, 95]

存在的问题:
  到这里大家就已经看出问题了,从第6轮开始就已经没有需要交换的元素了,后面又多比较了两轮。
  不要忘记上面一开始就说过的注意事项:在某趟排序的比较中,如果发现两两比较无一交换,则说明数组已经有序。

修改代码如下:
  增加一个标记变量,用来判断本轮排序过程中有无交换。如果没有,则直接结束排序过程。

# coding:utf-8
'''
# @Method:冒泡排序
# @Author: wlhr62
'''
import os
import sys


class Solution:
    def BubbleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        for i in range(n):
            changeNum = 0  # 加入一个变量,用于判断本轮排序过程中有无交换
            for j in range(0, n-i-1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
                    changeNum += 1
            print("第", i+1, "轮的排序结果:", nums)
            # 如果发现两两比较无一交换,则说明数组已经有序
            if changeNum == 0:
                break
        return nums
        

if __name__ == "__main__":
    nums = [50, 36, 66, 76, 95, 12, 25, 36]
    A = Solution()
    res = A.BubbleSort(nums)
    print("最后的排序结果:", res)
    

修改代码后的运行结果如下:

1 轮的排序结果: [36, 50, 66, 76, 12, 25, 36, 95]2 轮的排序结果: [36, 50, 66, 12, 25, 36, 76, 95]3 轮的排序结果: [36, 50, 12, 25, 36, 66, 76, 95]4 轮的排序结果: [36, 12, 25, 36, 50, 66, 76, 95]5 轮的排序结果: [12, 25, 36, 36, 50, 66, 76, 95]6 轮的排序结果: [12, 25, 36, 36, 50, 66, 76, 95]
最后的排序结果: [12, 25, 36, 36, 50, 66, 76, 95]

思考:第6轮的重复是否可以省去?

1.4 冒泡排序的复杂度分析

  • 最坏时间复杂度:O(n^2)
  • 没有特殊说明时,一般都是计算最坏时间复杂度。
  • 冒泡排序中,最坏的情况是:列表的初始状态完全逆序排列。这种情况下,需要进行 n-1 轮冒泡,每一轮冒泡都需要进行 n-i-1 次比较和交换的操作。i 的平均值为 n/2 ,时间复杂度为 n(n-1)/2。
  • 最坏情况下,冒泡排序的时间复杂度为 O(n^2) 。
  • 最优时间复杂度:O(n)
  • 冒泡排序中,最好的情况是:列表的初始状态完全符合预期排列。这种情况下,只需要进行 1 轮冒泡,此过程中没有进行比较和交换的操作。要用一个标记变量来判断本轮排序过程中有无交换。如果没有,则直接结束排序过程。
  • 最好情况下,冒泡排序的时间复杂度为 O(n) 。
  • 平均时间复杂度:O(n^2)
  • 冒泡排序中,平均时间复杂度为 O(n^2) 。
  • 空间复杂度:O(1)

1.5 冒泡排序的稳定性分析

  • 冒泡排序属于稳定排序。
  • 分析:在冒泡排序中,每次比较两个元素,当元素的大小顺序错误时才会进行交换。如果元素列表中有两个相等的元素,它们最后肯定会相邻在一起,但在进行比较时,并不是顺序错误的情况,所以对它们比较时不会进行交换,相对次序是保持不变的。因此,冒泡排序是一种稳定的排序算法。




2. 选择排序

3. 插入排序

4. 希尔排序

5. 归并排序

6. 快速排序

7. 堆排序

8. 计数排序

9. 桶排序

10. 基数排序