会打扑克的人对于插入算法就很好了解啦,每次扎入一张牌我是会对它排序的。
插入排序包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。属于稳定排序的一种(通俗地讲,就是两个相等的数不会交换位置)。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
⒈ 从第一个元素开始,该元素可以认为已经被排序
⒉ 取出下一个元素,在已经排序的元素序列中从前往后(从后向前)扫描
⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置
⒋ 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序
Java实现代码如下:
从前向后查找的插入排序:
/********************************************************
*函数名称:InsertSort
*参数说明:dataArray 无序数组;
*说明: 插入排序
*********************************************************/
public void InsertSort(int[] dataArray)
{
for (int i = 1; i < dataArray.length; i++) //从第2个数据开始插入
{
int j = 0;
while (j < i && dataArray[j] <= dataArray[i]) //寻找插入的位置
j++;
if (j < i) //i位置之前,有比dataArray[i]大的数,则进行挪动和插入
{
int k = i;
int temp = dataArray[i];
while (k > j) //挪动位置
{
dataArray[k] = dataArray[k-1];
k--;
}
dataArray[k] = temp; //插入
}
}
}
从后向前查找的插入排序:
/********************************************************
*函数名称:InsertSort
*参数说明:dataArray 无序数组
*说明: 插入排序
*********************************************************/
void InsertSort(int[] dataArray)
{
for (int i = 1; i < dataArray.length; i++) //从第2个数据开始插入
{
int j = i - 1;
int temp = dataArray[i]; //记录要插入的数据
while (j >= 0 && dataArray[j] > temp) //从后向前,找到比其小的数的位置
{
dataArray[j+1] = dataArray[j]; //向后挪动
j--;
}
if (j != i - 1) //存在比其小的数
dataArray[j+1] = temp;
}
}
分享到:
相关推荐
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
希尔排序,直接插入排序,折半插入排序算法的实现,c语言实现希尔排序
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
各种排序算法(插入 希尔 归并 快速 堆排序 基数排序 选择 冒泡等等)
1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组不同的输入数据作比较;比较...
# sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() #计数排序 # sort.quickSort() #快速排序 该排序算法把每次的排序结果都列出来,可供初学...
数据结构排序算法中的折半插入排序,又称二分法,是对基本插入排序的一种改进,比普通的插入排序要快
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
插入类排序算法 包括直接插入排序,希尔排序,折半插入排序
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
冒泡排序算法选择排序算法插入排序c语言实现
C++排序算法之插入排序源码
文档包含:排序算法:选择排序排序算法,插入排序排序算法,对半插入排序排序算法,冒泡排序排序算法,堆排序排序算法。
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
C++排序算法之插入排序
自己看书时写的排序算法:插入排序 CPP文件
详解Java常用排序算法-插入排序
从排序的基本概念讲起,详细讲解了插入排序、交换排序、选择排序、归并排序等排序算法的原理以及实现代码