`
BarryWei
  • 浏览: 66660 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

数据结构及算法学习----03----插入排序

阅读更多

前沿:

 

如果需要了解简单排序中的冒泡排序和选择排序,请查看一下连接:

冒泡排序 点击这里

选择排序 点击这里

 

介绍:

在大多数情况下,插入排序算法是基本排序算法中最好的一种。虽然插入排序算法仍然需要O(N*N)的时间,但是在一般情况下,要比冒泡排序快一倍,甚至比选择排序还快一些。然而,并不是什么情况下插入排序算法的效率都是最好的。比如一个极端的情况:对于逆序排列的数据,每次比较和移动都会执行,所以插入排序不必冒泡排序快。因此,在选择这些算法的时候,要根据实际情况酌情处理才是上策。

 

思路:
把N个待排序的数据项看成一个有序部分和一个无序部分。开始的时候有序部分只有一个数据项(亦即第一个数据项,数组中下标为0的位置),无序部分中有N-1个数据项(除开数组中第一个数据项之外的其他数据项)。排序过程中每次从无序部分取出第一个元素,在有序部分中找到合适的位置将这个新取出的数据项放在该处,使之成为有序部分的一个数据项。经过这一次之后,有序部分多了一个数据项而无序部分少了一个数据项,以此类推,就可以实现序列的有序性。

 

核心代码:

	public void insertSort() {
		int innerLoop,outterLoop;
		for(outterLoop=1;outterLoop<elementCount;outterLoop++) {
			double temp  = array[outterLoop];
			innerLoop = outterLoop;
			while(innerLoop>0 && array[innerLoop-1]>=temp) {
				array[innerLoop] = array[innerLoop-1];
				innerLoop--;
			}//end of while
			array[innerLoop] = temp;
		}//end of for
	}//end of method insertSort()

 

核心代码说明:

外层的for循环中,outterLoop变量从1开始,向右移动。这是因为已经假设第一个数组就是有序的部分了。内层的while循环中,innerLoop变量从outterLoop变量开始,向左移动,直到temp变量小于innerLoop所指的数据项,或者它已经不能再往左移动为止。while循环中的每一趟都向右移动了一个已排序的数据项。

 

完整代码:

package barry.sort.insertsort;

public class InsertSorter {
	
	private double[] array;
	private int elementCount;

	public InsertSorter(int size) {
		array = new double[size];
		elementCount = 0;
	}// end of constructor

	public void insert(double value) {
		array[elementCount++] = value;
	}// end of method insert()

	public void display() {
		for (int i = 0; i < elementCount; i++) {
			System.out.print(array[i] + "\t");
		}// end of for
	}// end of method display()

	public void insertSort() {
		int innerLoop,outterLoop;
		for(outterLoop=1;outterLoop<elementCount;outterLoop++) {
			double temp  = array[outterLoop];
			innerLoop = outterLoop;
			while(innerLoop>0 && array[innerLoop-1]>=temp) {
				array[innerLoop] = array[innerLoop-1];
				innerLoop--;
			}//end of while
			array[innerLoop] = temp;
		}//end of for
	}//end of method insertSort()

}// end of class

 

package barry.sort.insertsort;

public class InsertSorterApp {
	public static void main(String[] args) {
		
		InsertSorter sorter = new InsertSorter(10);
		sorter.insert(-10);sorter.insert(56);
		sorter.insert(23);sorter.insert(8723);
		sorter.insert(-90);sorter.insert(993);
		sorter.insert(33);sorter.insert(-373);
		
		//display them before sort
		System.out.println("\nBefore Sort:");
		sorter.display();
		
		//sort them
		sorter.insertSort();
		
		//display tem after sort
		System.out.println("\nAfter Sort:");
		sorter.display();	
	}//end of main
}//end of class

 

运行结果:

Before Sort:
-10.0	56.0	23.0	8723.0	-90.0	993.0	33.0	-373.0	
After Sort:
-373.0	-90.0	-10.0	23.0	33.0	56.0	993.0	8723.0	
 

总结:

以上的过程我们发现插入排序很简单,但是效率如何呢?首先从空间来看,它只需要一个元素的辅助空间,用于元素的位置交换。从时间分析,首先外层循环要进行n-1次插入,每次插入最少比较一次(正序),移动两次;最多比较i次,移动i+2次(逆序)(i=1,2,…,n-1)。因此,插入排序的时间复杂度为O(N*N)。目前为止我们看到的三种排序算法,时间复杂度都是一样的,但是由于需要的交换次数和空间大小不同,因此实际过程中我们应该有选择性的去使用。

 

 

 

1
1
分享到:
评论

相关推荐

    数据结构与算法分析--C语言描述_数据结构与算法_

    排序算法如冒泡排序、选择排序、插入排序、快速排序、归并排序等,解决如何将无序数据变为有序的问题;查找算法如线性查找、二分查找,用于定位数据;图算法如深度优先搜索(DFS)和广度优先搜索(BFS),用于遍历图...

    数据结构与算法-----PPT版本

    数据结构与算法是计算机科学的基础,对于任何编程学习者来说,理解和掌握它们至关重要。这个“数据结构与算法-----PPT版本”很可能包含了徐旭松教授或专家精心制作的一系列教学材料,旨在帮助学习者深入理解这些核心...

    数据结构与算法分析-------

    - **结构化章节安排**:全书分为六个部分,涵盖数据结构和算法的基本概念到高级主题,每个部分都精心设计以引导读者逐步深入学习。 #### 各部分知识点概述 1. **第1部分:概述** - **章节1:概述**(第11页):...

    数据结构算法与应用--C++语言描述(代码与习题答案)

    在《数据结构算法与应用--C++语言描述》这本书中,作者深入浅出地介绍了各种基本和高级的数据结构及其对应的算法,并提供了详细的C++实现。以下是基于这个主题的详细知识点讲解: 1. **数组**:数组是最基础的数据...

    数据结构与排序算法------通过代码示例,讲解:数据结构和9种排序算法。.zip

    逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    Java数据结构与算法概述-初级篇.docx

    本文档主要聚焦于初级水平的数据结构与算法的学习,适用于初学者掌握基础概念和技术要点。主要内容包括栈、队列、链表等基本数据结构以及递归的概念,并详细介绍了几种排序算法的实现方式。 #### 一、基本概念 **...

    C++数据结构与算法 (第4版)

    - 冒泡排序、选择排序和插入排序的基本思想及时间复杂度分析。 - 希尔排序(Shell Sort)的改进方法。 - 快速排序的分治策略及递归实现。 - **高级排序算法**: - 归并排序的合并策略及稳定性分析。 - 堆排序的...

    数据结构--排序--思维导图.pdf

    "数据结构--排序--思维导图" 数据结构中排序是指将一组无序的记录序列按照一定的规则排列成有序的序列,排序的目的是为了提高数据的存储和检索效率。排序算法的稳定性是指在排序过程中,如果待排序表中有两个元素Ri...

    数据结构与算法分析-C++描述

    - **排序算法**: 如冒泡排序、插入排序、快速排序等,这些算法的不同实现方式对于性能有着不同的影响。 - **查找算法**: 包括顺序查找、二分查找等,适用于不同类型的数据集。 - **递归与动态规划**: 这些高级算法...

    数据结构与算法-java

    以下是基于标题“数据结构与算法-java”及描述中提到的“数据结构与算法分析_Java语言描述高清版(第2版)1.pdf”所涵盖的一些关键知识点: 1. **数据结构**: - **数组**:最基础的数据结构,存储固定大小的同类型...

    数据结构,算法与应用 ---C++语言描述(代码与习题答案)

    常见的算法有排序(如冒泡排序、选择排序、插入排序、快速排序、归并排序)、搜索(如线性搜索、二分搜索)、图算法(如深度优先搜索DFS、广度优先搜索BFS、最短路径算法Dijkstra、Floyd-Warshall)等。理解和掌握...

    7.数据结构与算法--电子课件.zip

    - **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,它们用于将一组数据按照特定顺序排列。 - **查找算法**:如线性查找、二分查找、哈希查找,用于在数据集中寻找特定元素。 - *...

    java数据结构与算法.pdf

    - **八大排序算法**:包括冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序、希尔排序和计数排序。每种算法都有其特定的应用场景和效率特点。 4. **查找算法**: - **哈希表**:通过哈希函数快速定位...

    数据结构与算法分析-C语言描述-包含源码和每章节答案

    它的特性包括指针操作、内存管理、类型系统和预处理器宏,这些都使得C语言成为学习数据结构和算法的理想选择。 - 使用C语言实现数据结构,可以更好地理解内存布局和程序执行的底层细节,这对于优化和调试代码至关...

    算法-数据结构和算法-10-选择排序.rar

    在编程竞赛、数据结构与算法的学习中,选择排序是一个基础概念,有助于理解排序算法的基本原理。在实际编程中,尽管选择排序并不常用,但对于学习者来说,它是理解其他更高效排序算法(如快速排序和归并排序)的良好...

Global site tag (gtag.js) - Google Analytics