每日一题之常见的排序算法

这篇具有很好参考价值的文章主要介绍了每日一题之常见的排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

常见的排序算法

排序是最常用的算法,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外,还有桶排序、堆排序、基数排序和计数排序。

1、冒泡排序

冒泡排序就是把小的元素往前放或大的元素往后放,比较的是相邻的两个元素。
时间复杂度: O ( n 2 ) O(n^2) O(n2),空间复杂度: O ( 1 ) O(1) O(1),稳定排序。
思想:
(1)比较相邻的两个元素,如果第一个比第二个大,就交换它俩的位置;
(2)对每一对相邻元素作同样的工作,从开始第一对到最后一对,一趟下来,最后的元素会是最大的数;
(3)针对所有的元素重复以上的步骤,除了最后一个;
(4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对元素需要比较。此时,该数组排好序。

def bubbleSort(list_1):
	len_1 = len(list_1)
	# 需要遍历的趟数
	for i in range(len_1):
		# 相邻元素的比较次数
		for j in range(len_1-i-1):
			# 如果第一个比第二个大,则交换两个元素的顺序
			if list_1[j]>list_1[j+1]:
				list_1[j], list_1[j+1] = list_1[j+1], list_1[j]
	return list_1				

改进后的排序算法,如果在一轮遍历中没有发生元素交换,就可以确定列表已经有序。可以修改冒泡排序函数,使其在遇到这种情况时提前终止。

def shortBubble(list_2):
	# 判断是否需要交换
	exchange = False
	len_2 = len(list_2)
	# 如果在一轮遍历中没有发生元素交换,则提前终止
	for i in range(len_2):
		exchange = False
		for j in range(len_2-i-1):
			if list_2[j] > list_2[j+1]:
				list_2[j], list_2[j+1] = list_2[j+1], list_2[j]
		if not exchange:	
			break
	return list_2

2、选择排序

选择排序给每个位置选择当前最小的元素。
算法思想:
(1)在所有数组中找到最小(大)元素,将其存放到数组的起始位置;
(2)在剩余元素中继续找最小(大)元素,然后依次放到已排序数组的末尾;
(3)重复操作,直到所有元素均排列好。
时间复杂度: O ( n 2 ) O(n^2) O(n2),空间复杂度: O ( 1 ) O(1) O(1),非稳定排序

def selectionSort(list_3):
	len_3 = len(list_3)
	for i in range(len_3):
		minIndex = i
		for j in range(i+1, len_3):
			if list_3[j] < list_3[minIndex]:
				minIndex = j
		list_3[i], list_3[minIndex] = list_3[minIndex], list_3[i]
	return list_3

3、插入排序

插入排序:在一个已经有序的小数组上,依次插入一个元素
算法思想:
(1)从第一个元素开始,该元素被认为是已经排好序的小数组;
(2)取出下一个元素,在已经排好序的小数组中从后向前遍历;
(3)如果排好序小数组的末尾元素大于待插入元素,将该末尾元素移动到下一个位置,并找小数组末尾元素的前面一个元素;
(4)重复步骤3,直到找到已排序的元素小于或等于待插入元素的位置;
(5)将待插入元素插入到该位置后,重复步骤2-5,直到该数组是有序的。
时间复杂度: O ( n 2 ) O(n^2) O(n2),空间复杂度: O ( 1 ) O(1) O(1),稳定排序

def insertionSort(list_4):
	len_4 = len(list_4)
	#遍历除第一个元素外的所有元素
	for i in range(1, len_4):
		# 若第i个元素大于i-1元素,直接插入
		if list_4[i] < list_4[i-1]:
			j = i - 1
			# 待插入元素
			value = list_4[i]
			while j >= 0 and value < list_4[j]:
				# 向后移动元素
				list_4[j+1] = list_4[j]
				j -= 1
			list_4[j+1] = value
	return list_4

4、快速排序

快速排序:选取一个基准值,分成两段,左边放小于基准值的所有数,右边放大于基准值的数。
思想:
(1)选取基准值;
(2)将比基准值小的元素交换到前面,比基准值大的元素交换到后面;
(3)对左右区间重复步骤2,直到各区间只有一个数。

# 分区操作
def partition(alist, first, last):
	# 基准
	pivotVal = alist[first]
	# 左右两个
	leftMark = first + 1
	rightMark = last
	flag = False
	while not flag:
		# 加大leftMark,直到遇到一个大于基准的元素
		while alist[leftMark] <= pivotVal and leftMark <= rightMark:
			leftMark += 1
		# 减少rightMark,直到遇到一个小于基准的元素
		while alist[rightMark] >= pivotVal and leftMark <= rightMark:
			rightMark -= 1
		# 当rightMark <leftMark时,过程终止
		if rightMark < leftMark:
			flag = True
		else:
		#将rightMark对应的元素与当前位于分割点的元素互换
			alist[leftMark], alist[rightMark] = alist[rightMark], alist[leftMark]
		alist[leftMark], alist[rightMark] = alist[rightMark], alist[leftMark]
	return rightMark

def quickSortHelper(alist, first, last):
	if first < last:
		mid = partition(alist, first, last)
		quickSortHelper(alist, first, mid)
		quickSortHelper(alist, mid+1, last)

def quickSort(alist):
	quickSortHelper(alist, 0, len(alist)-1)

5、希尔排序

希尔排序是插入排序的一种变种,为了加快速度改进的插入排序,交换不相邻的元素以对数组的局部进行排序。
思想:
(1)让数组中任意间隔为 h h h 的元素有序;
(2)刚开始 h = l e n g t h / 2 h = length / 2 h=length/2
(3)接着让 h = l e n g t h / 4 h = length / 4 h=length/4,让 h h h 一直缩小,直到 h = 1 h=1 h=1,此时数组中任意间隔为1的元素有序。

# 对每个子序列进行插入排序,需要得到子序列的起始点和长度
def gapInsertSort(list_6, start, gap):
	for i in range(start+gap, len(list_6), gap):
		# 当前待插入元素
		curValue = list_6[i]
		j = i - gap
		
		if list_6[i] < list_6[i-gap]:
			while j >= 0 and curValue < list_6[j]:
				list_6[j+gap] = list_6[j]
				j -= gap
			list_6[j+gap] = curValue
	return list_6

def shellSort(list_6):
	# 获取每个子序列的长度
	subListLen = len(list_6) // 2
	# 子序列的长度要始终大于0
	while subListLen > 0:
		# 起始位置的取值
		for startPos in range(subListLen):
			# 分段进行插入排序
			gapInsertSort(list_6, startPos, subListLen)
		# 每次都将子序列的长度减少一半
		subListLen = subListLen // 2
	return list_6

6、归并排序

思想:将一个无序数组有序,首先将这个数组分成两个,然后对这两个数组分别进行排序,之后再把这两个数组合并成一个有序的数组。此时该数组就有序了。文章来源地址https://www.toymoban.com/news/detail-646168.html

# 合并两个有序数组
def merge(list_7, list_8):
	# 分别获取两个子序列的下标
	index1 = 0
	index2 = 0
	# 分别获取两个子序列的长度
	len_7 = len(list_7)
	len_8 = len(list_8)
	list_sum = []
	while index1 < len_7 or index2 < len_8:
		if list_7[index1] > list8[index2]:
			list_sum.append(list_8[index2])
			index2 += 1
		else:
			list_sum.append(list_7[index1])
			index1 += 1
	list_sum += list_7[index1:]
	list_sum += list_8[index2:]
	return list_sum

def mergeSort(list_9):
 	# 原数组的长度不能少于2
	if len(list_9) < 2:
		return list_9
	# 进行二路归并
	mid = len(list_9) // 2
	# 左边进行归并排序
	left = merge(list_9[:mid])
	# 右边进行归并排序
	right = merge(list_9[mid:])
	return merge(left, right)

到了这里,关于每日一题之常见的排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每日一题之数值的整数次方

    描述: 实现函数 double Power(double base, int exponent),求 base 的 exponent 次方。 注意: 1.保证base和exponent不同时为0。 2.不得使用库函数,同时不需要考虑大数问题 3.有特殊判题,不用考虑小数点后面0的位数。 我的思路:直接使用递归,让它每次乘一个它自身。但这存在一个问题,

    2024年02月12日
    浏览(40)
  • 每日一题之打家劫舍

    题目链接 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算

    2024年02月08日
    浏览(44)
  • 每日一题之打家劫舍II

    题目链接 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报

    2024年02月08日
    浏览(42)
  • 【c语言】每日一题之汉诺塔类型

    大佬们,我又回来了,最近也在忙自己的学业,忙着生活对线,也参加了今年的蓝桥杯其他的组,发现今年太难了 ,摆烂了。但我想到了读者你们,从今天开始继续更新博客。通过写一篇我随便写的有趣的题,打开今年的博客之旅。 BC161 大吉大利,今晚吃鸡 糖和抖m在玩个游

    2023年04月16日
    浏览(34)
  • 每日一题之两个字符串的删除操作

    题目链接 给定两个单词  word1  和  word2  ,返回使得  word1  和   word2  ** 相同 所需的 最小步数 。 每步  可以删除任意一个字符串中的一个字符。 示例 1: 示例  2: 提示: 1 = word1.length, word2.length = 500 word1  和  word2  只包含小写英文字母 我们可以定义一个二维数组 dp ,

    2024年02月15日
    浏览(39)
  • C语言每日一题之旋转数求最小值

    hello,今天我们分享一道题目,是牛客网上的一道题 求旋转数组中的最小值https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13tqId=23269ru=/ta/coding-interviewsqru=/ta/coding-interviews/question-ranking 那我们先来看一下题目的意思,首先要读懂题目讲的是什么 题目说一个非降序数组,

    2024年02月13日
    浏览(36)
  • 算法每日一题: 删除排序列表中的重复元素2 | 循环 | 链表的删除 | 虚拟节点

    大家好,我是星恒 今天的题目是昨天题目的进化题,他对链表的删除加深了理解。最重要的是学会了对循环中的特殊部分的处理,还有设置虚拟节点的情况 好了,话不多说,我们直接开始 题目:leetcode 82 给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点

    2024年01月16日
    浏览(39)
  • C语言每日一题之整数求二进制1的个数

    今天分享一道题目,用三种方法来求解 二进制1的个数 方法1 我们的十进制除10和取余数就可以得到我们每一位的数字,那我们的二进制也可 以 这是一种方法,另外一种就是我们可以用移位操作符来算 这个方法是不是也是特别妙呢,当然还有更妙的方法,请看!!! 相信看

    2024年02月15日
    浏览(62)
  • 每日一道面试题之介绍一下常见的异常类有哪些?

    常见的异常类包括: NullPointerException(空指针异常): 例如: SQLException:(数据库相关的异常): 例如: IndexOutOfBoundsException(下标越界异常): 例如: IllegalArgumentException(非法参数异常): 例如: IllegalStateException(非法状态异常): 例如: ClassCastException(类型转换异常

    2024年02月08日
    浏览(48)
  • AcWing 5050. 排序 (每日一题)

    给定一个长度为 n 的由小写字母构成的字符串。 请你按照 a∼z 的顺序,对字符串内的字符进行重新排序,并输出重新排序后的字符串。 输入格式 第一行包含整数 T ,表示共有 T 组测试数据。 每组数据第一行包含整数 n 。 第二行包含一个长度为 n 的由小写字母构成的字符串

    2024年02月11日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包