插入排序
package sort;
public class InsertSort {
static void insertSort(int[] array) {
int j = 0;
// Staright insertion Sort
for(int i = 1; i < array.length; ++i)
if(array[i] < array[i - 1]) {
int temp = array[i]; //复制为哨兵
array[i] = array[i - 1];
for( j = i - 2; j >=0 && temp < array[j]; --j) {
array[j + 1] = array[j]; //记录后移
}
array[j + 1] = temp; //插入到正确位置
}
}
}
二分插入排序
package sort;
public class BInsertSort {
public static void binsertSort(int[] array) {
int i = 0;
for(i = 1; i < array.length; ++i) {
int temp = array[i];
int low = 0; int high = i -1;
//折半插入有序插入的位置
while(low <= high) {
int m = (low + high)/2;
if(temp < array[m]) //插入点在低半区
high = m -1;
else //插入点在高半区
low = m + 1;
}
for(int j = i - 1; j >= high + 1; --j)
array[j + 1] = array[j]; //记录后移
array[high + 1] = temp; //插入
}
}
}
分享到:
相关推荐
在本系统中,我们主要实现了五种常用的排序算法:冒泡排序法、快速排序法、直接插入排序法、折半插入排序法和树形选择排序法。这些算法都是在计算机科学中最基本和最重要的排序算法,广泛应用于各种数据处理和分析...
常见的经典排序算法有希尔排序、二分插入法、直接插入法、带哨兵的直接排序法、冒泡排序、选择排序、快速排序、堆排序等。 一、希尔排序(Shell 排序法) 希尔排序法,又称宿小增量排序,是 1959 年由 D.L.Shell ...
常见的排序算法有插入排序、快速排序、选择堆积排序法等。 插入排序算法是一种简单的排序算法,适用于小规模的数据结构。该算法将数据结构分成已排序部分和未排序部分,并将未排序部分的元素插入到已排序部分中。...
在计算机科学领域,排序算法是数据处理中的核心部分,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序排列。本资源"总结了各种排序算法,并用C++代码实现,并有演示",提供了丰富的学习材料,包括不同类型...
希尔排序是一种基于插入排序的算法,通过将待排序的数组元素按某个增量分组,然后对每组使用直接插入排序算法排序。随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止...
本篇文章将介绍一种经典的排序算法——**合并排序法**(Merge Sort),并通过C语言实现该算法。合并排序是一种非常有效的排序方法,其核心思想是分治法:将数据分为若干个子集,对这些子集分别进行排序,最后将排序...