经典排序之 插入排序

Author: bakari  Date: 2012.7.21

排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为插入排序。

插入排序有三种形式:

一、最简单的直接插入排序,每个元素之间选取的间隔为1

见代码:

 1 /*****************************************************
 2  *     Author: bakari Date: 2012.7.21
 3  *     直接插入排序
 4  *     存储结构--vector
 5  *****************************************************/  
 6 void InsertSort::Insort()
 7 {
 8     for(int i = 1; i != len; ++i)
 9     {
10         int InsertPoint = insertList[i];
11         int iReplace = i;
12         while(iReplace > 0 && InsertPoint < insertList[iReplace - 1])
13         {
14             insertList[iReplace] = insertList[iReplace - 1];  //移动填补
15             iReplace --;
16         }
17         insertList[iReplace] = InsertPoint;         //插入
18     }
19 }

二 、shell排序:

shell排序其实本质是插入排序,只不过是分区间,然后在不同的区间去进行排序。

看代码:

 1 /***********************************************
 2  *  shell排序
 3  *  在直接插入排序的基础上增加间隔
 4  *  算法和直接插入一致
 5  ***********************************************/
 6 void ShellSort::Shell_Sort()
 7 {
 8     int gap = len / 2;   //确定间隔,初始间隔为序列长度的一半,而后继续缩小进行
 9     while(gap)
10     {
11         for (int i = gap;i < len; i += gap)
12         {
13             int ShellPoint = ShellList[i];
14             int j = i;
15             while(j > 0 && ShellPoint < ShellList[j - gap])
16             {
17                 ShellList[j] = ShellList[j - gap];
18                 j -= gap;
19             }
20             ShellList[j] = ShellPoint;
21         }
22         gap /= 2;         //继续缩小间隔,直到间隔为1;
23     }
24 }

三、二叉插入排序

这个和二叉查找类似,找不到元素之后就进行插入,直到排序完为止。

看代码:

 1 /****************************************************
 2  *  二叉插入排序
 3  *  原理与二叉查找相似,找不到元素则进行插入
 4  ****************************************************/
 5 
 6 //插入排序实现
 7 void BinaryInsertSort::Binary_Insert_Sort()
 8 {
 9     int mid;      //记录中点位置
10     for (int i = 0; i != len; ++i)
11     {
12         int BInsertPoint = BInsertList[i];
13         int left = 0;
14         int right = i - 1;
15         while(left <= right)
16         {
17             mid = (left + right) / 2;
18             if(BInsertPoint < BInsertList[mid])
19                 right = mid - 1;
20             else left = mid + 1;
21         }
22         for(int j = i; j > left ;j--)
23             BInsertList[j] = BInsertList[j - 1];
24         BInsertList[left] = BInsertPoint;
25     }
26 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小古哥的博客园

读书笔记《PHP与MySQL程序设计》一

第1章 PHP概述 1.1  历史(PHP4、PHP5、PHP5.3、PHP6[未发布]) 1.2 一般语言特性(实用性、强大功能、可选择性、成本[开源]) 第...

4046
来自专栏一枝花算不算浪漫

Arrays.asList中所遇到的坑

最近在项目上线的时候发现一个问题,从后台报错日志看:java.lang.UnsupportedOperationException异常 从代码定位来看,原来...

3572
来自专栏微信公众号:Java团长

Java遍历集合的几种方法分析(实现原理、算法性能、适用场合)

Java语言中,提供了一套数据集合框架,其中定义了一些诸如List、Set等抽象数据类型,每个抽象数据类型的各个具体实现,底层又采用了不同的实现...

1181
来自专栏LinkedBear的个人空间

唠唠SE的集合-00——概述 原

                        由于是数组实现,在增和删的时候会牵扯到数组增容、以及拷贝元素,所以慢。

902
来自专栏Golang语言社区

Go语言语法汇总

最近看了看GoLang,把Go语言的语法总结了一下,做个快速参考 数据类型 ---- var varName type,var var1,var2… type,...

4328
来自专栏编程

Python读书笔记5

上期分享了Python相关的字符串应用,重点分享了转义字符。今天和大家分享和字符串相关的函数和应用。 一、字符串的合并! Python用“+”号可以连接两个文本...

2117
来自专栏猿人谷

小瓜牛漫谈 — String

String 类在 Java 中代表字符串。Java 程序中的所有字符串字面值(如 "abc" )都作为此类的实例实现。 1 public static voi...

1889
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列4

Java面试系列4 一、一个".java"源文件中是否可以包括多个类(不是内部类)?有什么限制? 可以。必须只有一个类名与文件名相同。Public的类必须和文件...

3566
来自专栏企鹅号快讯

Python读书笔记7

上期和大家分享了列表的创建及列表的基本特性,本期和大家分享一下列表改增删操作。 一、列表的修改 ? 上期的这个图还记得吗? 这个图说明了字符串的不可变性及列表的...

2129
来自专栏算法channel

面试必备|单链表反转思路图形解析

01 — 单链表 链表玩的是指针操作,非常容易出错,尽管看似很简单。 先定义一种单链表,JAVA(或C#)描述的数据结构如下: public class...

5465

扫码关注云+社区

领取腾讯云代金券