数据结构排序算法代码,算法顺序结构
Yyds干货库存
一、排序算法概述排序算法(英文：Sorting algorithm)是一种可以将一串数据按照特定顺序排列的算法。
1.1排序算法的稳定性：稳定的排序算法会将键值相等的记录按相对顺序保存。也就是说，如果一个排序算法是稳定的，当有两个键值相等的记录R和S，并且R在原列表中排在S之前时，在排序后的列表中R也会排在S之前。
当相等的元素不可区分时，比如整数，稳定性不是问题。但是，假设下面的数字对将按它们的第一个数字排序。
(4，1) (3，1) (3，7) (5，6)在这种情况下，有可能产生两种不同的结果。一种是以相对顺序保存具有相同键值的记录，而另一种不是：
(3，1) (3，7) (4，1) (5，6)(秩序维护)
(3，7) (3，1) (4，1) (5，6)(顺序改变)不稳定排序算法可能会改变相等键值之间记录的相对顺序，但稳定排序算法从来不会。不稳定排序算法可以专门实现为稳定。一种方法是手动扩展键值的比较，这样其他方面键值相同的两个对象之间的比较(例如，增加第二个标准：上述比较中第二个键值的大小)将决定使用原始数据顺序中的项，作为最终得分。但是，请记住，这种顺序通常会带来额外的空间负担。
二。排序算法2.1冒泡排序(英文：Bubble Sort)是一种简单的排序算法。它反复遍历要排序的序列，一次比较两个元素，如果它们的顺序不对，就切换它们。重复遍历序列，直到不需要交换，也就是说，序列已经被排序。这种算法的名字来源于较小的元素会通过交换慢慢“浮”到序列的顶端。
冒泡排序算法的工作原理如下：
比较相邻的元素。如果第一个比第二个大(按升序)，就把两个都交换。对每一对相邻的元素做同样的工作，从开始的第一对到结束的最后一对。在这一步之后，最后一个元素将是最大的数字。对除最后一个元素之外的所有元素重复上述步骤。每次对越来越少的元素重复上述步骤，直到没有要比较的数字对。1.气泡分选分析交换过程图(首次):
然后我们需要进行n-1次冒泡过程，每次对应的比较时间如下图所示：
2.代码定义bubble_sort(列表):
对于范围内的j(len(list)-1，0，-1):
# j表示比较每次遍历的次数，该次数逐渐减少。
对于范围(j)中的I:
if list[I]list[I 1]:
列表[i]，列表[i 1]
李=[54，26，93，17，77，31，44，55，20
冒泡_排序(李)
打印(li)气泡排序-优化
def bubble_sort_1(li):
对于范围内的I(len(Li)-1):
交换=假
对于范围内的j(len(Li)-I-1):
如果李[j]李[j 1]:
李[j]，李[j 1]=李[j 1]，李[j
交换=真
如果不是交换：
3.时间复杂度。最优时间复杂度：O(n)(表示如果遍历一次，发现没有可交换元素，排序结束。)最差时间复杂度：O(n2)稳定性：稳定性2.2选择排序是一种简单直观的排序算法。它的工作原理如下。首先，在未排序的序列中找到最小(最大)的元素，并将其存储在已排序序列的开头。然后，继续从剩余的未排序元素中寻找最小(最大)的元素，并将其放在排序后的序列的末尾。依此类推，直到所有元素都被排序。
排序的主要优势与数据移动有关。如果元素处于正确的最终位置，它将不会被移动。每次选择交换一对元素，其中至少有一个会移动到最终位置。因此，对n个元素的表进行排序总共最多可以交换n-1次。在所有完全依靠交换来移动元素的排序方法中，选择性排序是非常好的一种。
1.选择排序分析和排序流程：
2.代码定义选择_排序(列表):
n=len(列表)
需要# n-1个选择操作。
对于范围内的I(n-1):
#记录最低位置
min_index=i
#选择从i 1位置到末端的最小数据
对于范围(I ^ 1，n)中的j:
if list[j]list[min _ index]:
min_index=j
#如果所选数据不在正确的位置，请更换它。
if min_index！=我：
列表[i]，列表[最小索引]=列表[最小索引]，列表[i]
list=[54，226，93，17，77，31，44，55，20]
选择_排序(列表)
打印(列表)3。时间复杂度最优时间复杂度：O(n2)最差时间复杂度：O(n2)稳定性：不稳定(考虑升序最大选择的情况)2.3插入排序(英文：Insertion Sort)是一种简单直观的排序算法。它的工作原理是构造一个有序序列，在有序序列中从后向前扫描未排序的数据，找到对应的位置并插入。在插入的实现中，从后向前扫描的过程中，需要将排序后的元素一步一步地反复向后移动，为最新的元素提供插入空间。
1.插入排序分析
2.代码定义insert_sort(列表):
#从第二个位置向前插入下标为1的元素
对于范围内的I(1，len(list)):
#从第I个元素向前比较，如果它小于前一个元素，则交换位置
对于范围(I，0，-1)中的j:
if list[j]list[j-1]:
列表[j]，列表[j-1]
list=[54，26，93，17，77，31，44，55，20]
插入排序(列表)
打印(列表)3。时间复杂度最佳时间复杂度：O(n)(升序，序列已经是升序)最差时间复杂度：O(n2)稳定性：稳定2.4快速排序(英文：Quicksort)，又称分区交换排序，通过一次排序将待排序的数据分成两个独立的部分，一部分的所有数据小于另一部分的所有数据。然后用这种方法对两部分数据进行快速排序，整个排序过程可以递归进行，使整个数据成为有序序列。
这些步骤是：
从序列中选择一个元素，称为“pivot ”,并对序列重新排序。小于基准值的元素全部放在基准前面，大于基准值的元素全部放在基准后面(同一个数可以在两边)。在这个分区结束后，基准位于系列的中间。这称为分区操作。递归排序小于参考值的元素子系列和大于参考值的元素子系列。在递归的最底层，序列的大小是零或一，也就是一直排序下去。虽然它一直在递归，但这个算法总会结束，因为在每次迭代中，它至少会将一个元素放到它的最后一个位置。
1.快速分类分析
2.代码定义分区(李，左，右):
tmp=李[左]
而左右：
而left right和Li [right]=tmp: #从右边找到比tmp小的数。
右-=1 #向左移动一步
Li[left]=li[right] #在左边空白处写右值。
而左右和li[left]=tmp:
左=1
Li[right]=li[left] #将左边的值写在右边的空白处。
李[左]=tmp #把tmp放回原位
向左返回
def quick_sort(李，左，右):
Leftright: #至少两个元素
mid=分区(李，左，右)
快速排序(李，左，中1)
Quick_sort(李，中1，右)3。时间复杂度：最佳时间复杂度：O(nlogn)最差时间复杂度：O(n2)稳定性：不稳定。从头开始快速排序平均需要O(n log n)时间。但是观察分区操作并不难。数组的元素将在每个循环中被访问一次，使用的时间为O(n)。在使用串联的版本中，这个操作也是O(n)。
在最好的情况下，每次运行分区时，我们都会将一个系列分成两个几乎相等的部分。这意味着每个递归调用处理一半大小的序列。因此，在到达大小为1的序列之前，我们只需要进行log n个嵌套调用。这意味着调用树的深度是O(log n)。但是，在两个相同层次结构的程序调用中，原始序列的相同部分不会被处理；所以每个层次的程序调用总共只需要O(n)次(每个调用都有一些共同的开销，但是因为每个层次只有O(n)次调用，所以这些都汇总在O(n)系数中)。结果是该算法只需要O(n log n)时间。
2.5希尔排序希尔排序是一种插入排序。也称为减少增量排序，它是直接插入排序算法的一个更有效和改进的版本。希尔排序是一种不稳定的排序算法。这种方法以DL命名。壳牌是在1959年提出的。Hill排序是将记录按一定的增量分组，用直接插入排序算法对每组进行排序。随着增量逐渐减小，每个组包含的关键词越来越多。当增量减少到1时，整个文件正好分成一组，算法终止。
1.希尔排序过程。Hill排序的基本思想是在一个表中列出数组，分别对列进行插入和排序，重复这个过程，但每次都是用更长的列(步长更长，列数更少)。最后，整个表只有一列。把数组转换成表格的目的是为了更好的理解这个算法，算法本身还是用数组来排序的。
比如，假设有这样一组数[13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]。如果我们以步长5开始排序，我们可以通过将这个列表放在一个有5列的表中来更好地描述算法，这样它们应该是这样的(垂直元素由步长组成):
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10然后我们对每一列进行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45当以上四行数依次连在一起，我们得到：[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]。这时，10已经被移动到正确的位置，然后以3:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45排序后，它变成：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94最后，按1步排序(此时，就是简单的插入排序)。
2.希尔排序分析
3.代码定义shell_sort(列表):
n=len(列表)
#初始步长
差距=n/2
而间隙0:
#插入按步长排序
对于范围内的I(间隙，n):
j=i
#插入排序
而j=gap和list[j-gap]list[j]:
列表[j-gap]，列表[j]=列表[j]，列表[j-gap]
间隙
#获取新的步长
差距=差距/2
list=[54，26，93，17，77，31，44，55，20]
shell_sort(列表)
打印(列表)4。时间复杂度最佳时间复杂度：根据步骤顺序而变化。最差时间复杂度：O(n2)稳定思路：不稳定2.6归并排序。归并排序是分治法的一个非常典型的应用。排序的思想是递归分解数组，然后合并它们。
将数组分解到最小值后，合并两个有序数组。基本思路是比较两个数组前面的数字，谁最小谁先取，取完之后对应的指针后移一位。然后比较，直到一个数组为空，最后复制另一个数组的剩余部分。
1.合并和排序分析
假设当前列表按顺序分为两段，如何合成一个有序列表？
这种操作称为二次合并。
2.代码定义merge_sort(列表):
如果len(alist)=1:
退货清单
#二元分解
num=len(list)/2
left=merge _ sort(list[:num])
right=merge _ sort(list[num:])
#合并
返回合并(左，右)
定义合并(左、右):
合并操作，将左[]和右[]两个有序数组合并成一个大有序数组
#左右#下标指针
l，r=0，0
结果=[]
而左镜头(左)和右镜头(右):
如果左[l]右[r]:
result.append(left[l])
l=1
否则：
result.append(右[r])
r=1
result=left[l:]
result=right[r:]
回送结果
list=[54，26，93，17，77，31，44，55，20]
sorted _ list=merge sort(list)
打印(排序列表)3。时间复杂度最优时间复杂度：O(nlogn)最差时间复杂度：O(nlogn)稳定性：稳定性2.7常用排序算法的效率比较2.8搜索搜索是在项目集合中寻找特定项目的算法过程。搜索的通常答案是对或错，因为项目存在或不存在。几种常见的搜索方法：顺序搜索、二分法搜索、二叉树搜索和哈希搜索。
1.二分搜索法。二分搜索法，又名二分搜索法，比较次数少，搜索速度快，平均性能好；它的缺点是要检查的列表是有序的，很难插入和删除。因此，半查找法适用于查找变化不频繁的频繁有序列表。首先，假设表格中的元素按升序排列，将表格中间记录的关键字与搜索关键字进行比较，如果相等，则搜索成功；否则，使用中间位置记录将表格分成前后子表；如果中间位置记录的关键字大于搜索关键字，则进一步搜索前一子表；否则，进一步搜索下一个子表。重复上述过程，直到找到满足条件的记录，这样搜索成功，或者直到子表不存在，那么搜索不成功。
2.二分搜索法实现1)非递归实现
def binary _ search(list，item):
first=0
last=len(list)-1
while first=last:
中点=(第一个最后一个)/2
if list[中点]==item:
返回True
elif项目列表[中点]:
最后=中点-1
否则：
第一个=中点1
返回False
测试列表=[0，1，2，8，13，17，19，32，42，]
print(binary_search(testlist，3))
Print (binary _ search (testlist，13)) 2)递归实现
def binary _ search(list，item):
如果len(alist)==0:
返回False
否则：
中点=len(list)//2
if list[中点]==item:
返回True
否则：
如果项目列表[中点]:
返回binary _ search(list[:midpoint]，item)
否则：
返回binary _ search(list[midpoint 1:]，item)
测试列表=[0，1，2，8，13，17，19，32，42，]
print(binary_search(testlist，3))
Print (binary _ search(测试列表，13)) 3 .时间复杂度：最佳时间复杂度：O(1)最差时间复杂度：O (logn)转载请联系作者取得授权，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。