关键词:
一、排序算法
1.1 冒泡排序
-
每次循环都比较前后两个元素的大小,如果前者大于后者,则将两者进行交换。这样做会将每次循环中最大的元素替换到末尾,逐渐形成有序集合。将每次循环中的最大元素逐渐由队首转移到队尾的过程形似“冒泡”过程,故因此得名。
-
时间复杂度 最好O(n),平均O( n 2 n^2 n2),最坏O( n 2 n^2 n2)
import random
import time
def bubble(li):
'''
:param li: 需要进行排序的数组
:return: 排好序的数组
''' n = len(li)
while n:
for i in range(n - 1):
if li[i] >= li[i + 1]:
li[i], li[i + 1] = li[i + 1], li[i]
n -= 1
return li
def main():
begin = time.time()
li = list(range(10000))
random.shuffle(li) # 打乱
print(bubble(li))
end = time.time()
print(end - begin)
if __name__ == '__main__':
main()
- 但是上述代码情况时间复杂度始终是不变的。为O( n 2 n^2 n2)。最好的情况下(也就是数组已经排好序了)此时,时间复杂度为O(n)。
import random
import time
# 装饰器函数
def get_time(fn):
def inner(*args, **kwargs):
begin = time.time()
result = fn(*args, **kwargs)
end = time.time()
print("函数执行花费%f秒" % (end - begin))
return result
return inner
@get_time
def bubble(li):
'''
:param li: 需要进行排序的数组
:return: 排好序的数组
''' for i in range(len(li) - 1): # i表示第n趟
is_exchange = False
for j in range(len(li)-i-1): # len(li)-i-1表示无序区
if li[j] >= li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
is_exchange = True
if not is_exchange: # 如果第一趟没有进行交换。则说明列表为顺序排序
break
return li
def main():
li = list(range(10000))
bubble(li) # 函数执行花费0.001997秒
random.shuffle(li) # 打乱
bubble(li) # 函数执行花费28.990895秒
if __name__ == '__main__':
main()
1.2 选择排序
- 一次遍历最小的数,放到第一个位置。再一次遍历记录无序区中最小的数,继续放置。
- 其核心就是找到最小值对应的索引,然后与无序区的第0个元素交换位置。
import time
import random
# 装饰器函数
def get_time(fn):
def inner(*args, **kwargs):
begin = time.time()
result = fn(*args, **kwargs)
end = time.time()
print("函数执行花费%f秒" % (end - begin))
return result
return inner
@get_time
def select_sort(li):
for i in range(len(li)-1): # n-1躺
min_pos = i # 无序区最小值对应的索引,
for j in range(i+1,len(li)): # 无序区
if li[j] < li[min_pos]:
min_pos = j
li[i], li[min_pos] = li[min_pos], li[i] # 交换位置
return li
def main():
li = list(range(10000))
select_sort(li) # 函数执行花费7.453225秒
if __name__ == '__main__':
main()
1.3 插入排序
- 插入排序的精髓在于每次都会在先前排好序的子集合中插入下一个待排序的元素,每次都会判断待排序元素的上一个元素是否大于待排序元素,如果大于,则将元素右移,然后判断再上一个元素与待排序元素…以此类推。直到小于等于比较元素时就是找到了该元素的插入位置。
def insert_sort(li):
for i in range(1, len(li)): # i相对无序区的下标
tem = li[i]
j = i - 1
while j >= 0 and li[j] > tem: # 相对无序区的值小于于相对有序区的值
li[j+1] = li[j] # 则有序区的值后移
j -= 1 # 直到最后
# j的位置在循环结束时要么是-1,要么比tem小
li[j+1] = tem
return li
def main():
li = [6, 3, 1, 7, 8, 0, 2, 4, 9, 5]
print(insert_sort(li))
if __name__ == '__main__':
main()
1.4 快速排序
- 快速排序核心是找到一个中心枢纽(一般为第零个元素),使用双指针法,
- i从左往右,j从右往左。根据中心枢纽进行分区,先从左往右找到第1个比中心枢纽大的数字,从右往左找到找到第一个比中心枢纽小的数字。这两个数字进行交换。
- 然后i继续从左往右,找到下一个比中心枢纽大的数字,j继续从右往左找比中心枢纽小的数字。再将这两个数字继续宁交换
- 直到i和j相交,最后把中心枢纽放进i和j中间。对于中心枢纽左边和右边,使用递归调用,得到最终结果。
def quick_sort(li):
if len(li) < 2:
return li
tmp = li[0]
left = [v for v in li[1:] if v <= tmp]
right = [v for v in li[1:] if v > tmp]
left = quick_sort(left)
right = quick_sort(right)
return left + [tmp] + right
排序算法(冒泡排序选择排序插入排序快速排序归并排序)(代码片段)
1、冒泡排序 (英语:BubbleSort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排... 查看详情
排序算法之冒泡选择插入排序(java)(代码片段)
文章目录通过Java实现冒泡、选择、插入排序算法冒泡排序冒泡排序介绍和实现具体代码的实现选择排序选择排序介绍和实现选择排序图解具体代码实现插入排序插入排序介绍和实现插入排序图解具体代码实现通过Java实现冒泡、... 查看详情
总结:大厂面试常考手撕代码——javascript排序算法(冒泡排序选择排序插入排序快速排序)(代码片段)
文章目录1.冒泡排序2.选择排序3.插入排序4.快速排序1.冒泡排序//冒泡排序letarr=[2,4,1,6,3]functionbubbled(arr)for(leti=0;i<arr.length-1;i++)//【!!注意】这里不是j=i,因为回回都必须重头遍历,才能不漏一个... 查看详情
javascript实现常见排序算法:冒泡,插入,选择,归并,快速,堆排序(代码片段)
1.冒泡排序转自百度百科:冒泡排序,这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名“冒泡排序”。冒泡排序算法的运作如下:(从后往前) 比较相邻的元素。如果第... 查看详情
四种排序算法实现(代码片段)
目录冒泡排序冒泡算法源代码(冒泡排序)选择排序选择算法源代码(选择排序)插入排序插入算法源代码(插入排序)快速排序快速排序算法源代码(快速排序)总结References冒泡排序冒泡算法比较相邻的元素。如果左边比右... 查看详情
[leetcode]排序算法(冒泡排序,选择排序,插入排序,快速排序,计数排序)(代码片段)
目录1.冒泡排序原理 代码(python&cpp)拓展:timeit()用法2.选择排序原理3.插入排序原理代码(python&cpp)4.归并排序原理代码 5.快速排序原理代码(python&cpp)6.计数排序原理 代码(python&c... 查看详情
数据结构c语言版八大算法(上)图文详解带你快速掌握——希尔排序,堆排序,插入排序,选择排序,冒泡排序!(代码片段)
数据结构之八大算法详解(1)——希尔排序,堆排序,插入排序,选择排序,冒泡排序!插入排序基本思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的... 查看详情
排序算法
...据结构》简单的把上面的算法总结一下:简单算法:冒泡排序,简单选择排序,直接插入排序改进算法:希尔排序,堆排序,归并排序,快速排序插入排序:直接插入排序和希尔排序交换排序:冒泡排序和快速排序选择排序:简... 查看详情
js冒泡排序法——选择排序(other)——计数排序(桶排序)——快速排序——插入排序-更新(代码片段)
JavaScript排序算法JavaScript——冒泡排序法JavaScript——选择排序JavaScript——计数排序(桶排序)JavaScript——快速排序(递归二分法)JavaScript——插入排序JavaScript——冒泡排序法时间复杂度:O(nlogn)冒泡排序的英文BubbleSort... 查看详情
面试考点:冒泡排序选择排序插入排序归并排序快速排序(代码片段)
深处开发岗,其实排序也是绕不开的环节,其中冒泡排序,选择排序,插入排序,归并排序,快速排序,堆排序也是我在秋招以来频繁问到的技术点排序算法有两块比较重要的知识点内存消耗:算... 查看详情
十大经典排序算法(代码片段)
十大经典排序算法主题:排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:... 查看详情
排序(上):冒泡排序插入排序和选择排序(代码片段)
如何分析一个排序算法?分析一个排序算法的三要素:排序算法的执行效率、排序算法的内存消耗以及排序算法的稳定性。排序算法的执行效率对于排序算法执行效率的分析,一般是从以下三个方面来衡量:最好情况、最坏情况... 查看详情
排序算法整理:冒泡排序堆排序插入排序归并操作快速排序希尔排序选择排序(代码片段)
...ortjava.util.Arrays;/***@ClassName:SortUtils*@Description:<p>排序算法工具类</p>*@authoredgar*@email【[email protected]】*@versionV1.0*@date2017-3-2815:35:12*/publicclassSortUtils/***@Title:SortUtils*@Description:私有化构造:类不能实例化*/privateS... 查看详情
学习数据结构笔记====>不同的排序算法(sortalgorithm)[冒泡,选择,插入,快速,希尔,基数,归并](代码片段)
...可视化在线网站地址===>数据结构可视化在线排序算法:把一组数据,依指定顺序进行排列的过程.ml1.时间复杂度概述时间频度时间复杂度平均&最差时间复杂度2.冒泡排序稍微优化一下3.简单选择排序稍微优化一下... 查看详情
图形化排序算法比较:快速排序插入排序选择排序冒泡排序
图形化排序算法比较:快速排序、插入排序、选择排序、冒泡排序 查看详情
java八股文面试题基础篇--二分查找算法冒泡排序选择排序插入排序希尔排序快速排序(代码片段)
1.二分查找算法要求能够用自己语言描述二分查找算法能够手写二分查找代码能够解答一些变化后的考法1.1二分查找算法介绍二分查找也是一种在数组中查找数据的算法。它只能查找已经排好序的数据。二分查找通过比较数组中... 查看详情
排序算法(冒泡,选择,插入,快速)查找算法(二分,快速)
... 四种排序算法1.冒泡排序 思路分析:从前往后相邻的两个数一次进行比较,大的往下沉,小的网上冒。当相邻的两个数的比较后发现他们的排序与排序要求相反,就互换。 ... 查看详情
python数据结构与算法之排序(冒泡,选择,插入)(代码片段)
目录数据结构与算法之排序(冒泡,选择,插入)为什么学习数据结构与算法:数据结构与算法:算法:数据结构冒泡排序法选择排序法插入排序法数据结构与算法之排序(冒泡,选择,插入)为什么学习数据结构与算法:计算机重要的几门课:1.... 查看详情