数据结构各种排序总结,数据结构简单选择排序图解

　　Yyds干货库存

　　一、前言学习目标是了解排序的基本概念和稳定性，时间和空间的复杂性，以及适用的场景。熟悉三种常见的排序算法：直接插入排序、半插入排序和冒泡排序。了解希尔排序和快速排序的执行过程和算法。第二，基本概念。1.定义将一组无序的数据元素调整为有序的数据元素，排序分为从小到大和从大到小两种。

　　2.排序方法的稳定性0 1 2 3 4 5 6 7 8 5 4 10 11 22 8 10 76 1 2释义：一个像上表一样的无序数组，我想从小到大排序。上图中下标2和6对应的数字都是10。排序后，如果加引号的10仍然在未加引号的10前面，那么这个排序方法是稳定的，否则这个排序方法是不稳定的。

　　3.内部和外部排序内部排序：整个排序过程在内存中排序。外部排序：排序数量太大，内存和外部存储之间需要多次数据交换。3.插入类排序插入类：在一个有序序列中插入一条新记录，使其保持有序。

　　1.直接插入排序动态演示：

　　算法解释：

　　上面的动态图可以很好的表达直接插入的过程，但是动态图有点长。首先，用指针从前到后寻找比前面数字小的后面数字。当你找到指向0的指针，你就开始前进了。如果指向的值大于观察柱中的值，则数字向后移动。如果指向的值小于观察哨中的值，则将观察哨中的值存储在该元素后面的排序数字中，依此类推：

　　Void ins sort(记录类型r []，int length)/*直接插入并排序记录数组r，长度为数组中要排序的记录数*/{ int i，j；for(I=2；I=长度；I){ r[0]=r[I]；/*存储要插入到监视哨r[0] */j=i-1中的记录；While (r[0]。键r[j]。key) /*找到插入位置*/{ r[j 1]=r[j]；j=j-1；} r[j 1]=r[0]；/*插入要插入排序序列的记录*/} }/* in sort */特性：

　　稳定排序时间复杂度O(n*n)，空间复杂度O(1)2。半插入排序

　　算法解释：

　　没有得到动态演示，只能用上图。我将只看半插入和二分搜索法的想法。对于有序数组，插入一个数后，仍然有顺序。k代表要插入的值，low=1，high=length，mid=(低高)1。如果mid的对应值大于k，则high=low-1，否则low=mid 1插在low之后。

　　Voidbinsort(记录类型r []，int length)/*将记录数组r对半排序，长度为数组的长度*/{ int i，j；记录类型x；int低、高、中；for(I=2；I=长度；I){ x=r[I]；低=1；高=I-1；While(低=高)/*确定插入位置*/{mid=(低高)/2；if ( x.key r[mid]。key)高=中1；else低=mid 1；} for(j=I-1；j=低；-j)r[j 1]=r[j]；/*记录依次向后移动*/r[low]=x；/*插入记录*/}}/*BinSort*/功能：

　　时间复杂度为O(n*n)，空间复杂度为O(1)3。希尔分拣的动态演示：

　　算法解释：

　　对于Hill排序，取增量d (d一般为奇数，逐渐递减)。上图中，第一个排序D等于5，第一个作为起点，下一个取下标5的值。直到最后，将达到的值从小到大排序，然后以第二个为起点，依次以3 4 5为起点。第二个是D等于3，第三个是D等于1。代码：

　　Void shell insert(记录类型r []，int length，int delta)/*对记录数组r进行希尔插入排序，其中length是数组的长度，delta是增量*/{ int i，j；for(I=1；i=长度；I) /* 1 delta是第一个子序列的第二个元素的下标*/if (r [i]。键r [i-delta]。key){ r[0]=r[I]；/* Back up r[i](不要当哨兵)*/for(j=I-delta；j 0 r[0]。键r[j]。关键；j-=delta)r[j delta]=r[j]；r[j delta]=r[0]；}}/*ShellInsert*/功能：

　　不稳定排序增量序列的d值中没有1以外的公因数，最后一个增量值必须是1时间复杂度O(n*logn)空间复杂度O(1) IV。交换排序1。冒泡排序的动态演示：

　　算法解释：

　　设置两个指针，I，J，每次排序都把最大的数放在后面，以此类推。假设经过两次执行，那么最后两个数就不需要比较了。进行n-1次排序，结果完成代码：

　　Void bubble sort(记录类型r []，int length)/* bubble sort记录数组r，长度为数组的长度*/{ int n，I，j；nt变化；记录类型x；n=长度；变=真；for(I=1；i=n-1变化；I){ change=FALSE；for(j=1；j=n-ij) if (r[j]。键r[j 1]。key){ x=r[j]；r[j]=r[j 1]；r[j ^ 1]=x；变=真；} }} /*气泡排序功能：

　　稳定排序时间复杂度O(n*n)，空间复杂度O(1)2。快速排序动态演示：

　　算法解释：

　　快速排序有点复杂。其实就是设置两个指针，low high，分别指向第一个和第二个元素，把第一个元素的值赋给X变量，high，向前移动。如果高指向的值小于X，高指向的值会随X后移，如果低指向的值大于X，低指向的值会与X互换3/4两步，要知道高==低。第一次后，指向低到第二个元素，并把第一个

　　Voidqksort(记录类型r []，int low，int high)/*对记录数组r[low.high]按快速排序*/{ int pos；if(低高){ pos=qpass(r，低，高)；/*调用快速排序将pivot元素分成两个子表*/QKSort(r，low，pos-1)；/*快速排序左子表*/QKSort(r，pos 1，high)；/*快速排序右子表*/}}2。非递归算法：

　　Int qkpass(记录类型r []，int left，int right)/*对记录数组r的r[left]到r[right]部分排序一次，得到基准的位置，使排序结果满足其后(前)记录的关键字不小于(大于)基准记录*/{ record type x；int低，高；x=r[左]；/*选择基准记录*/low=左；高=右；While(低高){while(低高r[高])。key=x.key)/* high从右向左查找小于x.key的记录*/high-；if(低高){ r[低]=r[高]；低；}/*如果找到小于x.key的记录，就交换*/while (low high r [low])。key x.key)/* low从左到右查找大于x.key的记录*/low；if(低高){ r[高]=r[低]；高-；}/*如果找到大于x.key的记录，exchange */} r[low]=x；/*保存基准记录到low=high */return low位置；/*返回基准记录的位置*/}/* qpass */特性：

　　不稳定排序，然而时间复杂度O(nlogn)空间复杂度O(logn)是公认的内部排序中效率最高的一种。五、总结比较排序算法的平均时间复杂度和空间复杂度的稳定性特征。插入稳定简单的O(n*n)O(1)，效率一般减半。插入O(n*n)O(1)一般稳定高效。Hill O(n*logn)O(1)毫不费力的冒泡O(n*n)O(1)稳定的双指针，比较一次，减少一个需要比较的元素。Fast O(nlogn)O(logn)不稳定比较复杂，但高效先进的双指针和交换算法评论0发表评论

　　mb6221e63cdf332

　　2022-04-01 16:15

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。