`

排序算法---插入排序

 
阅读更多

插入排序的算法原理比较简单,通过一点点构建有序序列来达到排序的目的。比如给出一个数组a,长度为5,那么首先会将第一个元素作为一个已经排序的序列,然后从第二个元素开始向已经排序的序列(就是第一个元素)从后向前扫描,如果比这个序列中的元素小的话,就插入到相应元素的前面,而插入后需要后移元素。然后第三个元素再从这两个元素组成的有序序列的后面扫描,找到比它小的位置后就插入,否则继续向前扫描,以此类推。

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置中
  6. 重复步骤2

如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序

 

 

算法复杂度

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

 

下面的是用JAVA实现的三种方式

 

package sort;

import java.util.Arrays;

public class InsertSort {
	public static void main(String args[])
	{
		int array[]={49,38,65,97,76,13,27};
		insertSort(array,0,array.length-1);
		System.out.println("----------最终结果----------");
		System.out.println(Arrays.toString(array));
	}
	
	public static void insertSort(int array[],int first,int last)
	{
		int i,j;
		int temp;
		for(i=first+1;i<=last;i++)
		{
			temp = array[i];
			j=i-1;
			//与已排序的数逐一比较,大于temp时,该数后移
			while((j>=first)&&(array[j]>temp))
			{
				array[j+1]=array[j];
				j--;
			}
			//被排序数放在正确的位置
			array[j+1]=temp;
			System.out.println(Arrays.toString(array));
		}
		
	}
}

 

 运行结果:

 

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 76, 97, 13, 27]

[13, 38, 49, 65, 76, 97, 27]

[13, 27, 38, 49, 65, 76, 97]

----------最终结果----------

[13, 27, 38, 49, 65, 76, 97]

 

 

结果分析:

int array[]={49,38,65,97,76,13,27};

1、在方法insertSort()中需要传递三个参数,第一个参数是要排序的数组,第二个参数是数组的第一个元素下表,

即0,第三个元素是数组的最后一个下表,即array.length-1

2、方法体中

第一次:首先将array[i]赋值给temp,其实也就是第2个元素array[1]=38.

此时array[0]=49(看做一个有序序列),然后while中判断如果array[0]>temp,即49>38.

则将array[0]赋给array[1],即array[1]=49,此时j--后j的值变成了-1,然后再array[j+1]=temp,即

array[0]=38,这样其实就是将要排序的数放到了正确的位置。

第二次:i=2,temp=array[2],即65是待排序的数组,其中38、49为有序序列。j=1,while循环里,

array[1]=49,temp=65,array[1]<temp,所以不执行while循环,直接将temp的值65放在array[2]的

位置。

依次类推,如果发现向前扫描的时候,元素比要插入的元素大,就继续向前找,直到找到一个

第一个比它小的数,然后插入。

 

程序2:

package sort;

import java.util.Arrays;

public class InsertSort2 {
	public static void main(String args[])
	{
		Comparable c[]={49,38,65,97,76,13,27};
		insertSort(c);
		System.out.println(Arrays.toString(c));
	}
	
	public static void insertSort(Comparable data[])
	{
		for(int i=1;i<data.length;i++)
		{
			Comparable key = data[i];
			int position = i;
			while(position>0&&data[position-1].compareTo(key)>0)
			{
				data[position]=data[position-1];
				position--;
			}
			data[position]=key;
		}
	}
}

 运行结果:

[13, 27, 38, 49, 65, 76, 97]

 

分析:这里用到了Comparable类,主要是在比较数值的时候用到了compareTo方法进行两个元素的比较

 

第三种实现方式:

package sort;

import java.util.Arrays;

public class InsertSort3 {
	public static void main(String args[])
	{
		int array[]={49,38,65,97,76,13,27};
		insertSort(array,array.length-1);
		System.out.println("------------排序后的结果------------");
		System.out.println(Arrays.toString(array));
	}
	public static void insertSort(int array[],int size)
	{
		int i,j,temp;
		for(i=1;i<size;i++)
		{
			//取出一个数字用来排序,第一个元素array[0]看成一个已经排序的序列
			temp=array[i];
			//在排序序列中查找位置
			for(j=i-1;j>=0&&temp<(array[j]);--j)
			{
				array[j+1]=array[j];//向后移动数据
			}
			array[j+1]=temp;//插入数据到序列
			System.out.println(Arrays.toString(array));
		}
	}
}

 运行结果:

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 76, 97, 13, 27]

[13, 38, 49, 65, 76, 97, 27]

------------排序后的结果------------

[13, 38, 49, 65, 76, 97, 27]

 

可以看到,运行结果比第一种方式要好一些,不过原理都是一样的

分享到:
评论

相关推荐

    排序算法 -- 插入排序

    **插入排序**是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。这种算法对大数据量的处理效率较低,但对于小规模数据或者部分有序的...

    详解Java常用排序算法-插入排序

    Java排序算法 - 插入排序 插入排序(Insertion Sort)是一种简单的排序算法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 1 的有序表。该算法的实现非常简单,但其时间复杂度...

    排序算法-插入排序

    插入排序是一种基础且直观的排序算法,它的工作原理可以类比于整理扑克牌。在实际应用中,插入排序对于小规模数据或者部分有序的数据表现优秀,但对于大规模无序数据,其效率相对较低。以下是关于插入排序的详细知识...

    最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构

    插入排序算法是一种简单的排序算法,它的工作原理是通过将每个元素插入到已经排序的序列中,以达到排序的目的。插入排序算法的时间复杂度为O(n^2),因此它适合小规模的数据排序。 4.快速排序算法 快速排序算法是一...

    理解插入排序算法-讲解

    理解插入排序算法-讲解

    经典算法的C#源码实现

    经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - ...

    排序算法-直接插入排序

    直接插入排序是一种基础且简单的排序算法,它的工作原理可以形象地比喻为扑克牌的洗牌过程。在实际应用中,虽然对于大规模数据的排序效率不如更高级的算法,如快速排序、归并排序等,但它的实现简单,适合小规模或...

    java排序算法-大全.rar

    在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。这个名为"java排序算法-大全.rar"的压缩包文件显然包含了多种Java实现的排序算法,这对于我们理解和掌握这些算法至关重要。 ...

    基于python的排序算法-插入排序Insertion Sort

    **插入排序(Insertion Sort)**是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到...

    C语言版的排序方法---插入排序.docx

    插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序...

    排序算法--免费

    本文将深入探讨标题和描述中提到的一些基本排序算法,包括选择排序、冒泡排序、插入排序、希尔排序、堆排序、快速排序以及归并排序,并结合C++编程语言进行讲解。 1. **选择排序(Selection Sort)** - 选择排序是一...

    排序算法 - Axb的自我修养1

    - 直接插入排序:是一种简单的排序算法,将每个元素插入到已排序的部分,保持有序。时间复杂度为O(N^2),适用于小规模数据和基本有序的数据。 - 希尔排序:是插入排序的一种改进版本,通过设定间隔序列(希尔增量...

    数据结构排序算法汇总包-直接插入排序 折半插入排序 2—路插入排序 表插入排序 希尔排序 起泡排序 快速排序 简单选择排序 树形选择排序 堆排序 归并排序链式基数排序

    实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...

    排序算法 - 直接插入排序(图文超详细)

    直接插入排序是一种基础且常用的排序算法,它的工作原理可以直观地理解为手动整理扑克牌的过程。在本篇文章中,我们将深入探讨直接插入排序的细节,包括它的基本思想、步骤、时间复杂度以及适用场景。 一、基本思想...

    各种查找与排序算法-笔试面试必备

    常见的内部排序算法有插入排序、Shell排序、堆排序、冒泡排序、快速排序、归并排序等。每种算法都有其特点和适用场景,如插入排序和冒泡排序适用于小规模数据集,而快速排序和归并排序则更适用于大规模数据集。 ###...

    简单排序算法--类的简单使用

    在这个例子中,可能会有一个类`SortAlgorithms`包含各种排序算法的成员函数,如冒泡排序、选择排序、插入排序、快速排序等。另一个类`UserInterface`则负责处理用户交互和控制执行哪种排序算法。 3. **排序算法的...

    Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法

    Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...

    算法设计与分析-1排序算法性能分析-冒泡/选择/插入/合并/快速排序-pre ppt

    本篇文章将详细讨论几种常见的排序算法:选择排序、冒泡排序、插入排序、合并排序以及快速排序,分析它们的算法原理、时间效率,并通过经验分析验证理论分析的准确性。 **1. 选择排序(Selection Sort)** 选择排序...

    数据结构--九种排序算法 --排序001.cpp

    此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!

    [Java算法-排序]-插入排序.java

    该资源提供了Java中实现插入排序的全面指南。文档中涵盖了插入排序的基本概念,包括如何对数组进行排序以及如何在Java中实现插入排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现插入排序,包括详细的...

Global site tag (gtag.js) - Google Analytics