文档章节

算法学习笔记(三)-----各种基础排序问题

夏尘安
 夏尘安
发布于 2014/04/13 13:51
字数 859
阅读 16
收藏 0

一、直接插入排序:是最简单的排序方法,算法简单来说就是可以把第一个数a[0]看做有序数组,那么a[1]要插入进来,对比,插入合适位置;然后a[0],a[1]是有序数组,插入a[2]就依次和a[0],a[1]比较并插入,若a[2]需插在最前面,那a[0],a[1]都要依次后移。。。以此类推。所以插入排序有很多比较及交换的过程。时间复杂度为O(n2)。下面是自己编的插入排序的代码,很简单嗯:

void InsertSort(int *a,int length)

{

int temp=0;

for(int i=1;i<length;i++)

{

for(int j=0;j<i;j++)

{

if(a[i]<a[j])

{

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

}

二、希尔排序:也是一种插入排序,但是用简单的算法有了大的复杂度改进。简单来说就是设置了一个增量表K[]。比如有一个10个数字的数组需要排序的话,可以把增量表设置成K[3]={5,3,1}。先以增量5排序,就是把10个数字数组分区成为{R1,R6};{R2,R7};{R3,R8};{R4,R9};{R5,R10}.区域内各自使用插入排序,然后再以增量3排序,最后一定要用增量1排序,确认整体的顺序正确。这样可以因为小区域内的简单排序,确保整个数组”基本有序“,最后再进行一次校验,校验的时候就不需要过多的交换而浪费时间。但是希尔排序的复杂度很难分析,和增量序列也有关系。姑且记住当增量序列dlta[k]=2t-k+1-1时,其复杂度为On3/2)。

void ShellSort(int *array,int *dk,int length)

{

for(int i=0;i<sizeof(dk);i++)

{

       ShellFastSort(array,dk[i],length);

}

}

void ShellFastSort(int *a,int k, int len)

{

int temp;

for(int i=0;i<k;i++)

{

for(int j=i+k;j<len;j+=k)

{

for(int m=i;m<j;m+=k)

if(a[m]>a[j])

{

temp=a[j];

a[j]=a[m];

a[m]=temp;

}

}

}

}

三、冒泡排序:经典排序算法,交换的思想。数与数依次比较,大的就往后移,第一趟排序能把最大的数交换到最后一个位置,第二趟把第二大的数字交换到倒数第二的位置。。。时间复杂度还是On2.

    for(int j=n;j>0;j--)

         {

                   for(int i=1;i<j;i++)

                   {

                            if(array[i-1]>array[i]){

                     temp=array[i];

                    array[i]=array[i-1];

                     array[i-1]=temp;

                            }

                   }

         }

四、快速排序:是对冒泡排序的改进,思想简单来说,一趟排序把数字分成大数字区域和小数字区域,间隔点也就是所谓的“枢轴(pivot)“可任意选。通常把第一个数字作为枢轴,划分成两个区域后,再各自划分,不断递归,最后就剩两个或三个数字的区域,就很简单就能排列出来了。(不过代码还是稍微纠结了一下才写出来啊。。。)栈的最大深度可降为Ologn

void FastSort(int *a,int low,int high)

{

         int pivotloc=0;

         if(low<high){

             pivotloc=partition(a,low,high);

                   FastSort(a,low,pivotloc-1);

                   FastSort(a,pivotloc+1,high);

         }

}

int partition(int *a,int low,int high)

{

         int pivotkey=a[low],temp;

         while(low<high){

                   while(low<high&&a[high]>=pivotkey){high--;}

             if(low<high)

                            a[low++]=a[high];

                   while(low<high&&a[low]<=pivotkey){low++;}

        if(low<high)

                            a[high--]=a[low];

         }

         return low;

}


© 著作权归作者所有

夏尘安
粉丝 0
博文 7
码字总数 3091
作品 0
海淀
私信 提问

hjimce算法类博文目录 个人博客:http://blog.csdn.net/hjimce 个人qq:1393852684 知乎:https://www.zhihu.com/people/huang-jin-chi-28/activities 一、深度学习 深度学习(七十)darknet...

hjimce
2016/01/24
0
0
从基础概念到数学公式,这是一份520页的机器学习笔记(图文并茂)

  机器之心整理   笔记作者:Jim Liang      近日,来自SAP(全球第一大商业软件公司)的梁劲(Jim Liang)公开了自己所写的一份 520 页的学习教程(英文版),详细、明了地介绍了机...

机器之心
2018/04/30
0
0
go语言文件汇总

归并排序及go语言实现 堆排序算法及go语言实现 Go语言基础学习(一)变量 【Leetcode】:Counting Bits问题 in Go语言 基于go语言的心跳响应 【Leetcode】:Single Number III问题 in Go语言 ...

d_watson
2016/04/15
137
2
你不能错过的“推荐系统”资料合集

推荐系统的搭建是个复杂工程,涉及到实时计算、离线计算,以及各种数据采集、流转等,对自建推荐系统来说,更是很有困难。云栖社区将在6月16日晚20点组织一场在线分享《21天搭建推荐系统》,...

小云栖
2016/06/15
1
0
《Knowledge Base Completion By Learning...》阅读笔记

Knowledge Base Completion by Learning to Rank Model 基于模型排序学习的知识库推理 摘要 1. 知识库推理(Knowledge Base Completion)就是从KB中已有的事实预测新的事实; 2. 目前的方法是...

大不了敲一辈子代码
2018/07/03
121
0

没有更多内容

加载失败,请刷新页面

加载更多

最简单的获取相机拍照的图片

  import android.content.Intent;import android.graphics.Bitmap;import android.os.Bundle;import android.os.Environment;import android.provider.MediaStore;import andr......

MrLins
42分钟前
4
0
说好不哭!数据可视化深度干货,前端开发下一个涨薪点在这里~

随着互联网在各行各业的影响不断深入,数据规模越来越大,各企业也越来越重视数据的价值。作为一家专业的数据智能公司,个推从消息推送服务起家,经过多年的持续耕耘,积累沉淀了海量数据,在...

个推
44分钟前
7
0
第三方支付-返回与回调注意事项

不管是支付宝,微信,还是其它第三方支付,第四方支付,支付机构服务商只要涉及到钱的交易都要进行如下校验,全部成功了才视为成功订单 1.http请求是否成功 2.校验商户号 3.校验订单号及状态...

Shingfi
46分钟前
4
0
简述Java内存分配和回收策略以及Minor GC 和 Major GC(Full GC)

内存分配: 1. 栈区:栈可分为Java虚拟机和本地方法栈 2. 堆区:堆被所有线程共享,在虚拟机启动时创建,是唯一的目的是存放对象实例,是gc的主要区域。通常可分为两个区块年轻代和年老代。更...

DustinChan
52分钟前
6
0
Excel插入批注:可在批注插入文字、形状、图片

1.批注一直显示:审阅选项卡-------->勾选显示批注选项: 2.插入批注快捷键:Shift+F2 组合键 3.在批注中插入图片:鼠标右键点击批注框的小圆点【重点不可以在批注文本框内点击】----->调出批...

东方墨天
今天
6
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部