Python学习——排序算法实现

文章目录

  • 时间复杂度
  • 空间复杂度
  • 二分查找
  • 冒泡排序
  • 选择排序
  • 插入排序
  • 快速排序
  • 归并排序
  • 堆排序
  • 希尔排序
  • 计数排序

一直以来，我只是在大学学过C语言的数据结构中关于冒泡排序的算法，到现在这么多年也没有学习过其它算法，现在借着学习python的机会研究一下其它几种排序算法。听说现在面试的时候冒泡排序算法是最基本的。想想也是，几年前我面试的时候还当场写过C语言的冒泡排序，可惜当时只会这一种，现在总不能过了几年还是只会一种吧，说来惭愧。下面就好好写写这几种排序算法。

时间复杂度

时间复杂度是用来估算算法运行效率的描述，不可精确定量计算，一般用O(n)表示。

#代码片1print('Hello World!')#时间复杂度O(1)#代码片2for i in range(n):#时间复杂度O(n)print('Hello World!')#代码片3for i in range(n):#时间复杂度O(n*n)for j in range(n):print('Hello World!')#代码片4for i in range(n):#时间复杂度O(n*n*n)for j in range(n):for j in range(n):print('Hello World!')#代码片5while n > 1:print(n)n = n // 2

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 代码片1时间复杂度O(1)
  • 代码片2时间复杂度O(n)
  • 代码片3时间复杂度O(n2)
  • 代码片4时间复杂度O(n3)
  • 代码片4时间复杂度O(log2n)可以简写为O(logn)
    小结：
  • 时间复杂度是用来估算算法运行时间的一个单位
  • 一般来说，时间复杂度越高的算法比复杂度低的算法慢，效率低
  • 常见的时间复杂度安效率排序：O(1) > O(logn) > O(n) > O(nlogn) > O(n2) > O(n2logn) > O(n3)

空间复杂度

空间复杂度用来评估算法对内存占用的估算单位。为了提高算法的运行效率，降低时间复杂度，经常使用一空间换时间的算法。
未使用额外空间的算法空间复杂度为O(1)；
使用额外空间的算法空间复杂度为O(n)

二分查找

# 此算法的前提是data_list是一个按升序排列的列表# 循环版本的二分查找def bin_search(data_list, value):low = 0high = len(data_list) - 1while low <= high :mid = (low + high) // 2if data_list[mid] == value:return midelif data_list[mid] > value:high = mid -1else:low = mid + 1# 递归版本的二分查找def bin_search_rec(data_list, vaule, low, high):if low <= high:mid = (low + high) // 2if data_list[mid] == value:return midelif data_list[mid] > value:return bin_search_rec(data_list, vaule, low, mid -1)else:return bin_search_rec(data_list, vaule, mid + 1, high)else:return None
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

冒泡排序

时间复杂度: O(n2)
空间复杂度:O(1)

def bubble_sort(data_list):for i in range(len(data_list) - 1):for j in range(len(li) - i - 1):if data_list[j] > data_list[j + 1]:data_list[j], data_list[j+1] = data_list[j+1], data_list[j]# 冒泡排序优化， 如果执行一趟比较，没有发生交换，则列表已经是有序状态，可以直接结束算法def bubble_sort_2(data_list):for i in range(len(data_list) - 1):exchange = Falsefor j in range(len(li) - i - 1):if data_list[j] > data_list[j + 1]:data_list[j], data_list[j+1] = data_list[j+1], data_list[j]exchange = Trueif not exchange:return

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

选择排序

思路：初始时认为最小的元素位于0，然后遍历列表与元素0比较，找出最小元素的位置，然后交换，然后依次比较剩余区的最小元素，进行交换。
时间复杂度: O(n2)
空间复杂度:O(1)

def select_sort(data_list):for i in range(len(data_list) - 1):min_location = ifor j in range(i+1, len(data_list)):if data_list[j] < data_list[min_location]:min_location = jif min_location != i:data_list[i], data_list[min_location ] = data_list[min_location ], data_list[i]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

插入排序

思路：列表被分为有序区与无序区，最初有序区只有一个元素，即为第0个元素，依次从无序区拿出一个元素，与有序区比较，将元素插入到有序区相应的位置，直到无序区没有元素，排序完成
时间复杂度: O(n2)
空间复杂度:O(1)

def insert_sort(data_list):for i in range(1, len(data_list)):tmp = data_list[i]#从无序区拿出的第一个元素j = i - 1while j >= 0 and tmp < data_list[j]:data_list[j + 1] = data_list[j]j = j - 1data_list[j + 1] = tmp

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

快速排序

快速排序思路：

  • 取第一个元素p， 使p元素归位
  • 所谓归位，是指将p元素移动到一个位置，此位置的右边元素都比p大，左边都比p小
  • 归位后的返回值为p元素归位后的位置
  • 然后根据此位置递归完成左边与右边的元素的归位
    • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)
# partition函数首先从left位置取出一个元素p，暂存到tmp，# 然后从right位置开始比较，当right元素比tmp小时，将此right元素移动到left位置，否则right-1；# 然后再从left位置开始与tmp比较，当left元素比tmp大时，将left元素移动到right位置，否则left+1# 最后当left与right相等时，使tmp元素归位，即可保证元素右边比p大，左边比p小def partition(data, left, right):tmp = data[left]while left < right:while left < right and data[right] >= tmp:right -= 1data[left] = data[right]while left < right and data[left] <= tmp:left += 1data[right] = data[left]data[left] = tmpreturn leftdef quick_sort(data, left, right):if left < right:mid = partition(data, left, right)quick_sort(data, left, mid-1)quick_sort(data, mid+1, right)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

归并排序

归并排序思路：

  • 分解，首先将列表分解，直至分解成单个元素
  • 单个元素永远是有序的
  • 合并，将两个有序的列表合并，
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n)
def merge(data, low, mid, high):i = lowj = mid + 1Ltmp = []while i <= mid and j <= high:if data[i] <= data[j]:Ltmp.append(data[i])i += 1else:Ltmp.append(data[j])j += 1while i <= mid:Ltmp.append(data[i])i += 1while j <= high:Ltmp.append(data[j])j += 1data[low:high+1 ] = Ltmpdef merge_sort(data, low, high):if low < high:mid = (low + high) // 2merge_sort(data, low, mid)merge_sort(data, mid+1, high)merge(data, low, mid, high)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

堆排序

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)
    堆排序需要用到完全二叉树的概念，如下图所示。a、b是完全二叉树

    堆排序需要使用a、b类型的完全二叉树。

    将一个完全二叉树，按照层次的遍历的方式进行顺序存储。
    任意父节点 i 的左右子节点寻址关系如下：

  • 左子节点位置：2 * i + 1
  • 右子节点位置：2 * i + 2
  • 任意子节点 i 的父节点位置：i // 2 - 1
    使用堆排序，需要先将二叉树表示的堆调整为大根堆或者小根堆
  • 大根堆：一个完全二叉树，满足任意父节点比其左右子节点大
  • 小根堆：一个完全二叉树，满足任意父节点比其左右子节点小

所以将一个无序数据按照堆的方式进行排序时，需要先建立一个完全二叉树表示的堆，排序步骤如下：

  • 1、建立堆
  • 2、将堆顶元素与最后的无序区的子节点对调，堆顶元素为排好序的元素
  • 3、调整，重新获得一个大根堆
  • 4、回到步骤2 ，直到堆为空
    建立堆的过程：从一个堆的最底层，最右边的子树开始，比较父子节点，将大的子节点与父节点对调，此过程称为一个调整步骤，然后切换到下一个子树，同一层的子树调整完毕之后，讲层次提升一层，然后再次对子树进行调整，直到根节点树调整完毕。
    根据以上步骤，我们首先需要根据一个数组的最后一个元素，确定其父节点的位置：任意子节点 i 的父节点位置：len(List) // 2 - 1，这个元素就是一个完全二叉树的最后一个子树，然后向左依次调整一个子树，直到元素0（即根节点）对应树调整完毕。
def sift(data, low, high)i = lowj = 2 * i + 1tmp = data[i]while i < = high:if i < high and data[j] < data[j + 1]:j += 1if tmp < data[j]:data[i], data[j] = data[j], data[i]i = jj = 2 * i + 1else:breakdata[i] = tmpdef heap_sort(data)n = len(data)for i in range(n // 2 - 1, -1, -1)sift(i, i, n-1)for i in range(n-1, -1 , -1)data[0], data[i] = data[i], data[0]sift(data, 0, i-1)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

希尔排序

希尔排序比较奇葩！

  • 希尔排序是一种分组插入算法
  • 首选取一个数值d=n/2(n为元素的个数)，为间距，将元素按照此间距分组，组内元素进行比较，将较小的元素对调到靠前的位置
  • 将d值减半，重复步骤2，直到d=1，完成对调过程，排序完成
def shell_sort(data)gap = len(data)//2while gap > 0:for i in range(gap, len(data))tmp = data[i]j = i - gapwhile j >= 0 and tmp < data[j]data[j + gap] = data[j]j -= gapdata[j + gap] = tmpgap = gap // 2

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

计数排序

计数排序思路：

  • 首先创建一个以待排序列表中最大值为元素个数的计数列表，
  • 列表每个元素的初始值均为0
  • 然后统计待排序列表中的元素， 以元素的值为下标，每出现一次；在计数列表中次数加1
  • 然后根据计数列表中不为0的元素，按照下标顺序以及次数，将下标放置到新的排序列表，排序完成
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
def count_sort(data_list, max_value):count = [0 for i in range(max_value + 1)]for data in data_list:count[data] += 1i = 0for num, v in enumerate(count):for j in range(v):data_list[i] = numi += 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

我是头一次见到计数排序这种思路，让我大开眼界。
好了，关于排序的算法节写这么多，以后还要总结一下关于数据结构方面的知识。

赞 (0)

相关推荐