当前位置:网站首页>插入排序与希尔排序
插入排序与希尔排序
2022-07-06 13:56:00 【侯稼澍】
插入排序
将一元素插入到已排序完毕的数组中
可以将无序数组的第一个元素看作 只有一个元素的有序数组
后将数组中的元素一一插入到有序数组中的合适位置
所有元素被插入到有序数组中时,便已将此数组置为有序
动图演示
代码逻辑如下:
以升序为例
将插入的元素通过 tmp保存
假设 此时有序数组中有 i+1 个元素
将有序数组的最后元素(最大的元素)的下标,记为end
通过end遍历数组,寻出元素插入的合适位置
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
将 tmp 与 a[end]进行比较,
当 a[end] > tmp 时,将 a[end]后移一位,后 end--
接着与tmp进行比较 ,直至找到合适位置
合适位置的两种情况
1. tmp > end
2.tmp小于数组中所有元素
找到合适位置后,循环便结束,将数据存入合适位置 (end + 1)
此为一个元素插入到有序数组中的步骤
对 n 个元素的数组进行插入排序可以理解为
含有一个元素的有序数组中插入 n-1个元素
转化成代码即为
// 插入排序
void InsertSort(int* a, int n)
{
int i = 0;
for(i=0;i<n-1;i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
时间复杂度为 O(N^2)
希尔排序
希尔排序是插入排序的进阶排序,大大优化了插入排序的算法效率
基本思想与代码分析实现
假设数组中共有N个元素
取一小于N的正整数gap
将数组中相距为gap的元素分为一组
注意:各组间元素并不重合,在取元素时,第一组以下标为0的元素为第一个元素
第二种以下标为1的元素为第二个元素
......
将各组元素进行插入排序
int j = 0;
//对每组元素进行排序
for (j = 0; j < gap; j++)
{
int i = 0;
//对一组元素进行排序
for (i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
后将 gap减小重复上述步骤
以升序为例子
当 gap > 1时
此过程称之为预排序,为了方便更好更快的进行插入排序
gap越大,大的元素就更快到后方,小的元素就更快到前方
gap越小,数据便越接近有序
当gap == 1时
便为插入排序
综上所述
void ShellSort(int* a, int n)
{
//按照gap 进行插排
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
int j = 0;
for (j = 0; j < gap; j++)
{
int i = j;
for (i = 0; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
}
边栏推荐
- 经纪xx系统节点VIP案例介绍和深入分析异常
- Problems in the process of opencv300 cmake generating project
- Is it important to build the SEO foundation of the new website
- GPS from entry to abandonment (XVII), tropospheric delay
- Set status bar style demo
- Uni app app half screen continuous code scanning
- Five wars of Chinese Baijiu
- HDU 2008 digital statistics
- [Digital IC manual tearing code] Verilog automatic beverage machine | topic | principle | design | simulation
- 新入职一家公司需要去实践和注意的内容
猜你喜欢
[asp.net core] set the format of Web API response data -- formatfilter feature
GPS從入門到放弃(十三)、接收機自主完好性監測(RAIM)
Shell product written examination related
50 commonly used numpy function explanations, parameters and usage examples
LeetCode学习记录(从新手村出发之杀不出新手村)----1
Leetcode topic [array] -118 Yang Hui triangle
Basic introduction of figure
【MySQL】Online DDL详解
Aggregate function with key in spark
Reptile practice (V): climbing watercress top250
随机推荐
功能强大的国产Api管理工具
Digital transformation takes the lead to resume production and work, and online and offline full integration rebuilds business logic
GPS从入门到放弃(十五)、DCB差分码偏差
guava:Collections. The collection created by unmodifiablexxx is not immutable
QT | UDP broadcast communication, simple use case
Bat script learning (I)
Explain ESM module and commonjs module in simple terms
Xiaoman network model & http1-http2 & browser cache
20 large visual screens that are highly praised by the boss, with source code templates!
Broadcast variables and accumulators in spark
PostgreSQL install GIS plug-in create extension PostGIS_ topology
美国科技行业结束黄金时代,芯片求售、裁员3万等哀声不断
LeetCode:1189. The maximum number of "balloons" -- simple
PostgreSQL 安装gis插件 CREATE EXTENSION postgis_topology
How does the uni admin basic framework close the creation of super administrator entries?
What is the difference between animators and animators- What is the difference between an Animator and an Animation?
GPS from entry to abandonment (XVII), tropospheric delay
C how to set two columns comboboxcolumn in DataGridView to bind a secondary linkage effect of cascading events
Depth first traversal (DFS) and breadth first traversal (BFS)
Sql: stored procedures and triggers - Notes