Java实现直接插入排序和折半插入排序算法示例

直接插入排序​
1 排序思想：

将待排序的记录Ri插入到已经排好序的记录R1，R2，……，R（N-1）中。

对于一个随机序列而言，就是从第二个元素开始，依次将这个元素插入到它之前的元素中的相应位置。它之前的元素已经排好序。

第1次排序：将第2个元素插入到前边的有序列表（此时前边只有一个元素，当然是有序的），之后，这个序列的前2个元素就是有序的了。
第2次排序：将第3个元素插入到前边长度为2的有序列表，使得前2个元素是有序的。
以此类推，直到将第N个元素插入到前面长度为（N-1）的有序列表中。

2 算法实现：

// 直接插入排序
void straight_insert_sort(int num[], int len){
 int i,j,key;
 for(j=1;j<len;j++){
  key=num[j];
  i=j-1;
  while(i>=0&&num[i]>key){
   num[i+1]=num[i];
   i--;
  }
  num[i+1]=key;
 }
}

3 性能分析：

3.1 空间复杂度：如上代码，使用了一个辅助单元key，空间复杂度为O(1)

3.2 时间复杂度：

3.2.1 最好情况：待排序记录已经是有序的，则一趟排序，关键字比较1次，记录移动2次。则整个过程

比较次数为

记录移动次数为

时间复杂度O(n)

3.2.2 最坏情况：待排序记录已经是逆序的，则一趟排序，关键字比较次数i次（从i-1到0），记录移动（i+2）次。整个过程

比较次数为

记录移动次数为

时间复杂度O(n^2)

3.2.3 平均时间复杂度：O(n^2)

3.3 稳定性：稳定

折半插入排序
1 排序思想：

直接排序的基础上，将待排序的记录Ri插入到已经排好序的记录R1，R2，……，R（N-1）中，由于记录R1，R2，……，R（N-1）已经排好序，所以在查找插入位置时可采用“折半查找”。

2 算法实现：

// 折半插入排序
void binary_insert_sort(int num[], int len){
 int i,j,key,low,high,mid;
 for(i=1;i<len;i++){
  key=num[i];
  low=0;
  high=i-1;
  mid=(low+high)/2;
  // 寻找插入点，最终插入点在low
  while(low<=high){
   if(key<num[mid])
    high=mid-1;
   else
    low=mid+1;
   mid=(low+high)/2;
  }
  // 移动记录
  for(j=i;j>low;j--){
   num[j]=num[j-1];
  }
  // 插入记录
  num[low]=key;
 }
}

3 性能分析：

3.1 空间复杂度：如上代码，使用了一个辅助单元key，空间复杂度为O(1)

3.2 时间复杂度：虽然折半查找减少了记录比较次数，但没有减少移动次数，因此时间复杂度同直接查找算法。

3.2.1 最好情况：时间复杂度O(n)

3.2.2 最坏情况：时间复杂度O(n^2)

3.2.3 平均时间复杂度：O(n^2)

3.3 稳定性：稳定

赞 (0)

相关推荐

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • java数据结构与算法之插入排序详解

    本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

  • Java数据结构及算法实例：插入排序 Insertion Sort

    /** * 选择排序的思想: * 每次循环前,数组左边都是部分有序的序列, * 然后选择右边待排元素,将其值保存下来 * 依次和左边已经排好的元素比较 * 如果小于左边的元素,就将左边的元素右移一位 * 直到和最左边的比较完成,或者待排元素不比左边元素小 */ package al; public class InsertionSort { public static void main(String[] args) { InsertionSort insertSort = new Insert

  • java数据结构与算法之桶排序实现方法详解

    java数据结构与算法之桶排序实现方法详解

    本文实例讲述了java数据结构与算法之桶排序实现方法.分享给大家供大家参考,具体如下: 基本思想: 假定输入是由一个随机过程产生的[0, M)区间上均匀分布的实数.将区间[0, M)划分为n个大小相等的子区间(桶),将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <M辅助数组B[0..n-1]是一指针数组,指向桶(链表).将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. [桶-

  • Java数据结构与算法之选择排序(动力节点java学院整理)

    Java数据结构与算法之选择排序(动力节点java学院整理)

    每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完. 代码 public class ChoseSort { //constructor without parameters public ChoseSort(){}; //constructor with parameters public int[] ChoseSort(int[] intArr){ for(int i=0;i<intArr.length-1;i++){ int

  • Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是EightAlgorithms.java文件,代码如下: import java.util.Arrays; /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ public class EightAlgorithms { //插入排序:时间复杂度o(n^2) p

  • Java直接插入排序算法实现

    序:一个爱上Java最初的想法一直没有磨灭:"分享我的学习成果,不管后期技术有多深,打好基础很重要". 工具类Swapper,后期算法会使用这个工具类: 复制代码 代码如下: package com.meritit.sortord.util; /** * One util to swap tow element of Array *  * @author ysjian * @version 1.0 * @email ysjian_pingcx@126.com * @QQ 6466337

  • Java排序算法总结之插入排序

    本文实例讲述了Java插入排序方法.分享给大家供大家参考.具体分析如下: 有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到插入排序法.本文主要介绍的是插入排序的java实现.   插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据.比较和交换的时间复杂度为O(n^2),算法自适应,对于数据已基本有序的情况,时间复杂度为O(n),算法稳定,开销很低.算法适合于数据已基本有序或者数据量

  • Java经典排序算法之二分插入排序详解

    Java经典排序算法之二分插入排序详解

    一.折半插入排序(二分插入排序) 将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法.在处理A[i]时,A[0]--A[i-1]已经按关键码值排好序.所谓折半比较,就是在插入A[i]时,取A[i-1/2]的关键码值与A[i]的关键码值进行比较,如果A[i]的关键码值小于A[i-1/2]的关键码值,则说明A[i]只能插入A[0]到A[i-1/2]之间,故可以在A[0]到A[i-1/2-1]之间继续使用折半比较:否则只能插入A[i-1/2]到A[i-1]之间,故可

  • Java实现的各种排序算法(插入排序、选择排序算法、冒泡排序算法)

    一.插入排序算法实现java版本 public static int[] insert_sort(int[] a) { for (int i = 0; i < a.length; i++) { for(int j=i+1;j>0&&j<a.length;j--) { if(a[j]<a[j-1]) { int tmp = a[j]; //这样定义初始化逻辑上是可以的,j变量,每次tmp的值变化的 a[j] = a[j-1]; a[j-1] = tmp; } } }

  • java数据结构与算法之奇偶排序算法完整示例

    本文实例讲述了java数据结构与算法之奇偶排序算法.分享给大家供大家参考,具体如下: 算法思想: 基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序 举例吧, 待排数组[6 2 4 1 5 9] 第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比 [6 2 4 1 5 9] 交换后变成 [2 6 1 4 5 9] 第二次比较偶数列,即6和1比,5和5比 [2 6 1 4 5 9] 交换后变成 [2 1 6 4 5 9] 第三趟又是奇数列,选择的是

随机推荐