关键词:
算法是一种与语言无关的东西,更确切地说就算解决问题的思路,就是一个通用的思想的问题。代码本身不重要,算法思想才是重中之重
我们在面试的时候总会被问到一下算法,虽然算法是一些基础知识,但是难起来也会让人非常头疼。
排序算法应该算是一些简单且基础的算法,但是我们可以从简单的算法排序锻炼我们的算法思维。这里我就介绍经典十大算法用python是怎么实现的。
十大经典算法可以分为两大类:
比较排序: 通过对数组中的元素进行比较来实现排序。
非比较排序: 不通过比较来决定元素间的相对次序。
算法复杂度
一、冒泡排序
冒泡排序比较简单,几乎所有语言算法都会涉及的冒泡算法。
基本原理是两两比较待排序数据的大小 ,当两个数据的次序不满足顺序条件时即进行交换,反之,则保持不变。
1、动图演示
2、代码实现
def bubbleSort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
二、选择排序
每次选择一个最小(大)的,直到所有元素都被输出。
1、动图演示
2、代码实现
def selectionSort(arr):
for i in range(len(arr) - 1):
# 记录最小数的索引
minIndex = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# i 不是最小数时,将 i 和最小数进行交换
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
三、插入排序
将第一个元素逐个插入到前面的有序数中,直到插完所有元素为止。
1、动图演示
2、代码实现
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
四、希尔排序
从大范围到小范围进行比较-交换,是插入排序的一种,它是针对直接插入排序算法的改进。先对数据进行预处理,使其基本有序,然后再用直接插入的排序算法排序。
1、动图演示
2、代码实现
def shellSort(arr):
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr
五、归并排序
该算法是采用分治法对集合进行排序。
把长度为n的输入序列分成两个长度为n/2的子序列,对这两个子序列分别采用归并排序,最终合并成序列。
1、动图演示
2、代码实现
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0));
return result
六、快速排序
选取一个基准值,小数在左大数在在右。
1、动图演示
2、代码实现
def quickSort(arr, left=None, right=None):
left = 0 if not isinstance(left,(int, float)) else left
right = len(arr)-1 if not isinstance(right,(int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot+1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index+=1
i+=1
swap(arr,pivot,index-1)
return index-1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
七、堆排序
利用堆这种数据结构所设计的一种排序算法。
堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。利用最大堆和最小堆的特性。
1、动图演示
2、代码实现
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)
def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr
八、计数排序
采用字典计数-还原的方法,找出待排序的数组中最大和最小的元素,统计数组中每个值为i的元素出现的次数,对所有的计数累加,将每个元素放在新数组依次排序。
1、动图演示
2、代码实现
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr
九、桶排序
设置一个定量的数组当作空桶;遍历输入数据,并且把数据一个一个放到对应的桶里去;对每个不是空的桶进行排序;从不是空的桶里把排好序的数据拼接起来。
1、示意图
元素分布在桶中:
然后,元素在每个桶中排序:
2、代码实现
def bucket_sort_simplify(arr, max_num):
buf = i: [] for i in range(int(max_num)+1) # 不能使用[[]]*(max+1),这样新建的空间中各个[]是共享内存的
arr_len = len(arr)
for i in range(arr_len):
num = arr[i]
buf[int(num)].append(num) # 将相应范围内的数据加入到[]中
arr = []
for i in range(len(buf)):
if buf[i]:
arr.extend(sorted(buf[i])) # 这里还需要对一个范围内的数据进行排序,然后再进行输出
return arr
十、基数排序
取得数组中的最大数,并取得位数;从最低位开始取每个位组成新的数组;然后进行计数排序。
1、动图演示
2、代码实现
def radix_sort(data):
if not data:
return []
max_num = max(data) # 获取当前数列中最大值
max_digit = len(str(abs(max_num))) # 获取最大的位数
dev = 1 # 第几位数,个位数为1,十位数为10···
mod = 10 # 求余数的除法
for i in range(max_digit):
radix_queue = [list() for k in range(mod * 2)] # 考虑到负数,我们用两倍队列
for j in range(len(data)):
radix = int(((data[j] % mod) / dev) + mod)
radix_queue[radix].append(data[j])
pos = 0
for queue in radix_queue:
for val in queue:
data[pos] = val
pos += 1
dev *= 10
mod *= 10
return data
上面就是我整理的十大排序算法,希望能帮助大家在算法方面知识的提升。看懂之后可以去试着自己到电脑上运行一遍。最后说一下每个排序是没有调用数据的,大家记得实操的时候要调用。↓↓↓
参考地址:https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
感谢每一位愿意读完我文章的人,对于新媒体创作我也在不断学习中。创作是一件非常值得持续投入的事情,因为你们每一次的支持都是对我极大的肯定!
再次感谢大家的支持,在此我整理了一些适合大多数人学习的资料,免费给大家下载领取!
看!干货在这里↓ ↓ ↓
有需要的读者可以直接拿走,在我的QQ学习交流群。有学习上的疑问、或者代码问题需要解决的,想找到志同道合的伙伴也可以进群,记住哦仅限学习交流!!!
裙号是:298154825。
面试官常问的十大算法排序,你学会了吗?(代码片段)
...题。代码本身不重要,算法思想才是重中之重我们在面试的时候总会被问到一下算法,虽然算法是一些基础知识,但是难起来也会让人非常头疼。排序算法应该算是一些简单且基础的算法,但是我们可以从简单的... 查看详情
阿里面试官常问的tcp和udp,你真的弄懂了吗?
...道一些常用的网络协议是我们必须要了解和掌握的,面试的时候面试官也非常喜欢问一些协议相关的问题,其中有两个协议因为非常基础,出现的频率非常之高,分别是”TCP协议“和”UDP协议“。因为它们两个协... 查看详情
面试官常问十大经典算法排序(用python实现)
...的问题。代码本身不重要,算法思想才是重中之重我们在面试的时候总会被问到一下算法,虽然算法是一些基础知识,但是难起来也会让人非常头疼。排序算法应该算是一些简单且基础的算法,但是我们可以从简单的算法排序锻... 查看详情
面试官常问的垃圾回收器,这次全搞懂(代码片段)
...的垃圾回收器有哪些以及每个垃圾回收器的特点,这也是面试的时候经常被问的内容JVM堆内存概览在聊垃圾回收器之前,我们先来看看JVM堆内存的区域划 查看详情
阿里面试官常问的tcp和udp,你真的弄懂了吗?
...道一些常用的网络协议是我们必须要了解和掌握的,面试的时候面试官也非常喜欢问一些协议相关的问题,其中有两个协议因为非常基础,出现的频率非常之高,分别是”TCP协议“和”UDP协议“。因为它们两个协... 查看详情
java岗大厂面试官常问的那些问题,面试突击版!
并发编程共享模型篇并发编程概览进程与线程Java线程共享模型之管程共享模型之内存共享模型之无锁共享模型之不可变共享模型之工具共享模型之管程原理之Monitor(锁)原理之伪共享模式篇—正确姿势同步模式之保护性智停同步... 查看详情
面试官常问的设计模式及常用框架中设计模式的使用
文章目录单例模式1、静态常量2、双重检查机制疑问讲解双重检查机制在dubbo中的应用建造者模式1、在Spring中的运用2、在Guava中的运用工厂模式简单工厂模式工厂方法模式抽象工厂模式1、工厂模式在Mybatis的运用2、工厂模式在Spri... 查看详情
深度分析:面试腾讯,阿里面试官都喜欢问的string源码,看完你学会了吗?(代码片段)
...余的未整理的方法更新到这篇文章中。方便以后的复习和面试使用。如果文章中有地方有问题还请指出。简述字符串广泛应用在Java编程中,在Java中字符串属于对象,Java提供了String类来创建和操作字符串。字符串缓冲区支持可变... 查看详情
信安面试官常问的50个问题,你能答上几个?
先简单介绍一下你的技术情况。如果让你渗透一个网站,你的思路是什么。说一些近段时间你了解的漏洞。以前挖过哪些网站的漏洞。说几个你比较常用的工具。25、23、22、3306、1433、7001、445、139端口都是哪些服务的端口。S... 查看详情
最常问的mysql面试题集合(代码片段)
问题1:char、varchar的区别是什么?varchar是变长而char的长度是固定的。如果你的内容是固定大小的,你会得到更好的性能。 问题2:TRUNCATE和DELETE的区别是什么?DELETE命令从一个表中删除某一行,或多行,TRUNCATE命令永久地从表... 查看详情
面试官常问tcp的可靠传输和提高网络利用率?拿下!(代码片段)
前面讲到的TCP和UDP,在TCP的特性里面知道,他是有连接的,连接管理也是和可靠性是有一定关系的,那么他是如何建立连接,又是如何断开连接的呢?1.确认应答(ACK)机制因为我TCP是面向字节流的,一次... 查看详情
大厂面试常问的前端工程师面试手册,面试必备!(代码片段)
前言相对于传统的软件工程师面试而言,前端工程师面试对算法以及计算机底层考察程度较低。面试的时候一般会着重考察错综复杂的前端基础知识,比如HTML,CSS,JS等。同时会根据各个面试公司的技术栈去侧重... 查看详情
10个python面试常问的问题(代码片段)
...发展,Python的职位需求越来越高。下面我收集了10个Python面试官经常问的问题,供大家参考学习。类继承有如下的一段代码:classA(object):defshow(self):print'baseshow'classB(A):defshow(self):print'derivedshow& 查看详情
面试必问的volatile,你真的会了吗(代码片段)
谈谈你对volatile的理解?你知道volatile底层的实现机制吗?volatile变量和atomic变量有什么不同?volatile的使用场景,你能举两个例子吗?文章收录在GitHubJavaKeeper,包含N线互联网开发必备技能兵器谱之前算是... 查看详情
面试软件测试常问的4个问题,你get了吗?
一般在面试开始时,面试官会让我们先自我介绍一下,自我介绍主要介绍自己的教育经历、项目经历、主要工作内容、优缺点等等。自我介绍完之后,面试官会根据我们的自我介绍及简历上的信息进行提问,那么... 查看详情
悄悄告诉你,这些是我常问的面试题
可能你未来的面试官也在看哦,因为圈子小 年底被裁员了、或者想跳槽,最近不少人找我要面试题,想突击一下,那就把自己面试时常问的部分题拿出来分享给大家,希望能对大家有所帮助,,但是,还是要自己平时多... 查看详情
面试常问的c/c++问题,你能答上来几个?(代码片段)
...f01;最近不少小伙伴在找工作,这里我给大家分享一下面试中经常会遇到的一些嵌入式C语言问题,你看看能答上来几个呢?1用预处理指令#define声明一个常数,用以表明1年中有多少秒(忽略闰年问题)#define... 查看详情
java-android-常用十大排序算法-面试必备(代码片段)
...三大实际意义IT从业人员必备技能,也是互联网公司面试的必考点其中包含的技术和思想也能有效解决其他类型的问题排序算法常常是我们解决其他问题的第一步图片来源于网络十 查看详情