栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构初阶之排序(一)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构初阶之排序(一)

更新两个的排序:直接插入排序和希尔排序,两者的关联是很大的,所以放一起来说。

直接插入排序

直接插入排序:假设前n-1个数是有序的,将第n个数与前面的数进行比较,将它插入到合适的位置,通俗来讲,就是将一个数插入到已有的有序队列当中进行比较,然后按照规则把这个数插入到合适的位置。

比如有一堆数 1 2 3 5 9 现在想插入4,原数列是有序且升序,那么插入4就是从9开始比较,4比9小,9就需要向后挪一个位置,再与5比,4比5小,5也需要向后挪一个位置,再与3比,4比3大,4就插入5挪出来的位置,一次插入排序就完成了。

下面动图演示一个乱序的插入排序:

代码:

//插入排序
// 2 1 4 3 6
//时间复杂度:O(N^2) 逆序
//最好:O(N)  接近顺序有序
void InsertSort(int*a,int n)
{
    for(int i=0;i=0)
        {
            if(temp=0时继续比较
            }
            else
            {
                break;
            }
        }
        //循环结束有两种情况:1、end减为-1  放在end的后面一个位置
        //2、temp>a[end]  放在end的后一个位置
        a[end+1]=temp;
     } 
}

直接插入排序的时间复杂度是O(N^2) 

希尔排序

希尔排序:其实就是对直接插入排序的优化,希尔排序有两个阶段,第一个阶段是预排序,第二个阶段是对预排序排好的顺序再进行直接插入排序。

具体来说:希尔排序是基于插入排序的以下两点性质而提出改进方法的:

1.插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
2.插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

希尔排序的基本思想是:

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,

待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。

希尔排序实际上是直接插入排序的优化版本。

void ShellSort(int* a,int n)
{
    //gap>1 预排序--接近有序
    //gap==1 直接插入排序
    int gap = n;
    while(gap>1)//while循环的时间复杂度:log以3为底N的对数
    {
        gap=gap/3+1;//最后一次一定是1
        //gap = gap/2;//预排会多一些
       
        //间隔为gap的多组并排
        for(int i=0;i=0)
            {
                if(temp

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936159.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号