各主流排序算法详细介绍
2021-01-14 18:14
标签：one close cli sed show view image display 排序算法 在一个已经有序的序列里插入新的元素，直到有序序列包含所有被排序元素。 时间复杂度为O（N^2） 空间复杂度为O（1） 插入排序在小规模数据时或者基本有序时比较高效。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。本质上是分组插入排序。 在取增量d的时候一般有以下要求： ①最后一次排序d = 1； ②每次取的d并不包含处1以外的公因子； ③采用缩小增量法，d的取值逐步缩小。 希尔排序delta开始会很大，所以该排序不稳定。 希尔排序的复杂度与delta相关： {1,2,4,8,...}使用这个增量序列的时间复杂度（最坏情形）是O(N^2) 代码中所给序列的时间复杂度时O（N^1.5） 空间复杂度为O（1） 希尔排序为插入排序的一种优化，其适用范围为：大规模且无序的数据。 未完待续！ 各主流排序算法详细介绍 标签：one close cli sed show view image display 排序算法 原文地址：https://www.cnblogs.com/csuchenzc/p/12940416.html一，插入排序
插入排序基本思想：
例子：
代码实现：
void InsertSort(vectorint> &v)
{
for(int i = 1;i //i表示有序集合里的元素数目和待插入元素下标
{
for(int j = i; j > 0 && v[j-1] > v[j]; --j)
{
int temp = v[j-1];
v[j-1] = v[j];
v[j] = temp;
}
}
}
二，希尔排序
希尔排序基本思想：
例子：
代码实现：
void ShellSort(vectorint> &v)
{
int k = 0;
int t = v.size() - 1;
int delta = 2*t - k - 1;//有研究表明，delta取2*t-k-1时时间复杂度可达O（N^1.5）
for(k = 0;k k)
{
delta = (2*t-k-1) == t?(2*t-k-1):1;//最后一次delta要取1
for(int i = 0; i i)
{
if(v[i] > v[i+delta])
{
int temp = v[i];
v[i] = v[i+delta];
v[i+delta] = temp;
}
}
}
}