这篇文章主要介绍了java数据结构与算法之插入排序,结合实例形式分析了java插入排序的概念、分类、原理、实现方法与相关注意事项,需要的朋友可以参考下
本文实例讲述了java数据结构与算法之插入排序。分享给大家供大家参考，具体如下：
复习之余，就将数据结构中关于排序的这块知识点整理了一下，写下来是想与更多的人分享，最关键的是做一备份，为方便以后查阅。
排序
1、概念：
立即学习“Java免费学习笔记（深入）”；
有n个记录的序列{R1,R2,.......,Rn}（此处注意：1,2,n 是下表序列，以下是相同的作用），其相应关键字的序列是{K1,K2,.........,Kn}。通过排序，要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn，使得相应关键字满足如下的非递减（非递增）关系，即：Kp1
2、分类
根据排序时数据所占用存储器的不同，可将排序分为两类。
内部排序：整个排序过程完全在内存中进行，如下：
插入类排序（直接插入排序、折半插入排序、希尔排序）；
交换类排序（冒泡排序、快速排序）；
选择类排序（简单选择排序、树型选择排序、堆排序）；
归并排序；
分配类排序（多关键字排序、链式基数排序、基数排序的顺序表实现））；
外部排序：由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成（磁盘排序，磁带排序）。
3、稳定性
bee餐饮点餐外卖小程序是针对餐饮行业推出的一套完整的餐饮解决方案，实现了用户在线点餐下单、外卖、叫号排队、支付、配送等功能，完美的使餐饮行业更高效便捷！功能演示：1、桌号管理登录后台，左侧菜单 “桌号管理”，添加并管理你的桌号信息，添加以后在列表你将可以看到 ID 和 密钥，这两个数据用来生成桌子的二维码2、生成桌子二维码例如上面的ID为 308，密钥为 d3PiIY，那么现在去左侧菜单微信设置
假设在待排序的序列中存在多个具有相同关键字的记录。设Ki=Kj(1
插入排序：
思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
直接插入排序：
算法思想：假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。
用java实现的代码如下：
package exp_sort;
public class DirectInsertSort {
public static void DircstSort(int array[]) {
int j;
// 循环从第二个数开始，第一个数用做存放待插入的记录
for (int i = 1; i < array.length; i++) {
int temp = array[i];
// 寻找插入位置
for (j = i; j > 0 && temp < array[j - 1]; j--) {
array[j] = array[j - 1];
}
// 将待插入记录插入到已经排序的序列中
array[j] = temp;
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
DircstSort(array);
}
}算法分析：最好的情况是待排序记录本身已经按照关键字有序排列，最坏的情况是待排序记录是按照关键字逆序排列的；时间复杂度是O(N^2)，空间复杂度是O(1)；该算法是稳定的排序算法：比较适用于待排序记录数目较少且基本有序的情况。
折半插入排序：
算法思想：对于有序表进行折半查找，其性能优于顺序查找。
算法实现代码如下：
package exp_sort;
public class BinaryInsertSort {
public static void sort(int array[]) {
int temp, low, mid, high;
for (int i = 1; i < array.length; i++) {
temp = array[i];
low = 0;
high = i -1;
//确定插入位置
while (low <= high) {
mid = (low + high) / 2;
if (temp < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
//记录依次向后移动
for (int j = i; j >= low + 1; j--) {
array[j] = array[j-1];
}
//插入记录
array[low] = temp;
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = {38, 62, 35, 77, 55, 14, 35, 98};
sort(array);
}
}算法分析：是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1)。
【相关推荐】
1. 特别推荐：“php程序员工具箱”V0.1版本下载
2. Java免费视频教程
3. YMP在线手册
