C#插入排序
C#插入排序
C#插入排序一、插入排序的种类
包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。属于稳定排序的一种(通俗地讲,就是两个相等的数不会交换位置) 。
二、插入排序算法原理
插入即表示将一个新的数据插入到一个有序数组中,并继续保持有序。例如有一个长度为N的无序数组,进行N-1次的插入即能完成排序
第一次,数组第1个数认为是有序的数组,将数组第二个元素插入仅有1个有序的数组中;
第二次,数组前两个元素组成有序的数组,将数组第三个元素插入由两个元素构成的有序数组中.....
第N-1次,数组前N-1个元素组成有序的数组,将数组的第N个元素插入由N-1个元素构成的有序数组中,则完成了整个插入排序。
三、算法分析
平均时间复杂度:O(n2)
空间复杂度:O(1) (用于记录需要插入的数据)
四、插入排序稳定性
插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素
比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。
所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
五、C#插入排序算法
/// <summary>
/// 插入排序(升序)
/// </summary>
public static int[] InsertionSort(int[] needSortArray)
{
for (int i = 1; i < needSortArray.Length; i++)
{
int key = needSortArray[i];// 相当于[当前牌],这里赋给key起临时保存的作用
// 将当前牌与手中的牌依次比较
int j = i - 1;
while (j >= 0 && key < needSortArray[j])
{
// 将元素后移
needSortArray[j + 1] = needSortArray[j];
j--;
}
// j+1(因为上边的while循环多做了一次判断)即为当前牌插入的位置
needSortArray[j + 1] = key;
}
return needSortArray;
}
六、插入排序算法实例
以下面5个无序的数据为例:
65 27 59 64 58
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
七、算法优化
插入排序中,总是先寻找插入位置,然后在实行挪动和插入过程;寻找插入位置采用顺序查找的方式(从前向后或者从后向前),既然需要插入的数组已经是有序的,那么可以采用二分查找方法来寻找插入位置,提高算法效率,但算法的时间复杂度仍为O(n2)。
//查找数值iData在长度为iLen的pDataArray数组中的插入位置
int FindInsertIndex(int *pDataArray, int iLen, int iData)
{
int iBegin = 0;
int iEnd = iLen - 1;
int index = -1; //记录插入位置
while (iBegin <= iEnd)
{
index = (iBegin + iEnd) / 2;
if (pDataArray[index] > iData)
iEnd = index - 1;
else
iBegin = index + 1;
}
if (pDataArray[index] <= iData)
index++;
return index;
}
/********************************************************
*函数名称:BinaryInsertSort
*参数说明:pDataArray 无序数组;
* iDataNum为无序数据个数
*说明: 二分查找插入排序
*********************************************************/
void BinaryInsertSort(int* pDataArray, int iDataNum)
{
for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
{
int index = FindInsertIndex(pDataArray, i, pDataArray[i]); //二分寻找插入的位置
if (i != index) //插入位置不为i,才挪动、插入
{
int j = i;
int temp = pDataArray[i];
while (j > index) //挪动位置
{
pDataArray[j] = pDataArray[j-1];
j--;
}
pDataArray[j] = temp; //插入
}
}
}
- laravel时间日期字段比较(Laravel find in set排序实例)
- list使用linq排序
- php大量数据计算有什么技巧(PHP各种常见经典算法总结排序、查找、翻转等)
- linq 排序
- C#选择排序
- python列表反转的方法(Python实现的列表排序、反转操作示例)
- 怎么对python中列表进行排序(Python列表常见操作详解获取,增加,删除,修改,排序等)
- js数组排序有哪些(js将多维数组转为一维数组后去重排序)
- python数据分析删除重复值(Python3实现从排序数组中删除重复项算法分析)
- python队列快速排序(python按照多个条件排序的方法)
- C#快速排序
- dedecms标签怎么调用(DedeCMS织梦后台模板列表如何按字母排序方法代码)
- dedecms新字段(DEDECMSv5.6 tags.php标签不能按照时间排序的问题)
- python对列表排序(Python实现对特定列表进行从小到大排序操作示例)
- dedecms频道封面不能修改内容(dedecms按栏目名首字母/数字排序输出的实现方法)
- python教程列表排序(Python一行代码实现快速排序的方法)
- 三千年第一美女鞠婧祎出演白素贞pk杨紫,颜值胜赵雅芝王祖贤(三千年第一美女鞠婧祎出演白素贞pk杨紫)
- 成都轨道交通13号线一期工程最新进展(成都轨道交通13号线一期工程最新进展)
- 越南没事(越南没事情做)
- 重庆旅游攻略(重庆旅游3-4天攻略最佳线路)
- 周杰伦演唱会门票(周杰伦演唱会门票多少钱一张2023)
- 焕然一新 成都轨道集团官方网站改版上线(成都轨道集团官方网站改版上线)
热门推荐
- python 导入指定文件夹的模块(Python实现的在特定目录下导入模块功能分析)
- devc报错信息找不到(dede5.7验证码错误不显示的解决方法)
- python读取文件的正确方法(强悍的Python读取大文件的解决方案)
- sql server go语句
- js中parent和opener的区别
- windows7mysql服务无法启动(Windows系统下MySQL无法启动的万能解决方法)
- python下载后依然打不开文件(解决python打不开文件文件不存在的问题)
- python多线程和多进程应用场景(Python多线程处理实例详解单进程/多进程)
- mysql主从复制时突然来了一批数据(MySQL主从复制断开的常用修复方法)
- python多进程创建细节(Python实现多进程的四种方式)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9