`

Java排序算法之直接插入排序

阅读更多
    直接插入排序算法的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。

把a[i]插入到a[0],a[1],...,a[i-1]之中的具体实施过程为:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1]。

    以下是直接插入排序算法的JAVA代码实现:
package com.fit.direct.insert;

public class DirectInsertSort {

	/**
	 * 直接插入排序算法的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,
	 * 排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。
	 * 
	 * 把a[i]插入到a[0],a[1],...,a[i-1]之中的具体实施过程为:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-2],
	 * ...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1]。
	 * 
	 * 此种方法用for循环处理
	 * 
	 * @param array
	 */
	public static void sort(int[] array) {
		int length = array.length;
		int temp = 0;
		int local_i = 0;
		for (int i = 0; i < length - 1; i++) {
			local_i = i;
			for (int j = i + 1; j > 0; j--) {
				if (array[j] < array[local_i]) {
					temp = array[local_i];
					array[local_i] = array[j];
					array[j] = temp;
				}

				local_i--;

			}

			print(array);

		}

	}

	/**
	 * 此种方法用while循环处理。
	 * 
	 * @param array
	 */
	public static void sort1(int[] array) {
		int length = array.length;
		int temp = 0;
		int j = 0;
		for (int i = 0; i < length - 1; i++) {
			j = i;
			while (j >= 1 && array[j] < array[j - 1]) {
				temp = array[j - 1];
				array[j - 1] = array[j];
				array[j] = temp;
				j--;
			}

			print(array);

		}

	}

	public static void print(int[] array) {
		StringBuffer sb = new StringBuffer("[");
		for (int i = 0; i < array.length; i++) {
			if (i < array.length - 1) {
				sb.append(array[i]).append(",");
			} else {
				sb.append(array[i]);
			}
		}

		sb.append("]");

		System.out.println(sb);
	}

	public static void main(String[] args) {
		int[] array = new int[] { 54, 3, 11, 34, 12, 8, 19 };

		print(array);
		System.out.println("=====================");
		// sort(array);
		sort1(array);

		print(array);
	}
}


运行结果如下:
[54,3,11,34,12,8,19]
=====================
[54,3,11,34,12,8,19]
[3,54,11,34,12,8,19]
[3,11,54,34,12,8,19]
[3,11,34,54,12,8,19]
[3,11,12,34,54,8,19]
[3,8,11,12,34,54,19]
[3,8,11,12,34,54,19]
分享到:
评论

相关推荐

    JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序

    1. **直接插入排序**:直接插入排序是最基础的排序算法之一。它的工作原理是将待排序的元素逐个与已排序的部分进行比较,找到合适的位置插入。这种算法对于小规模或部分有序的数据集表现较好,但对于大规模无序数据...

    Java直接插入排序算法源码

    直接插入排序是一种基础且简单的排序算法,它的工作原理类似于我们日常生活中的整理扑克牌。在Java中实现这个算法,我们可以从以下几个关键知识点入手: 1. **基本思想**:直接插入排序是通过构建有序序列,对于未...

    使用Java与Python十大排序算法之直接插入排序

    ### 使用Java与Python实现直接插入排序 #### 一、直接插入排序概述 直接插入排序是一种简单的排序算法,属于插入类排序。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应...

    JAVA排序算法集合

    以上介绍了Java排序算法中常见的几种方法及其变体。每种算法都有其特点和适用场景,例如当数据量较小时可以选择直接插入排序或直接选择排序;当数据量较大时,归并排序和快速排序则更为合适。理解这些算法的工作原理...

    Java排序算法代码

    希尔排序是通过将相隔某个增量的元素组成一个子序列进行直接插入排序,随着增量逐渐减少,每个子序列中的元素逐渐增多,直至增量减至1时,整个数组成为一个子序列,此时的希尔排序就变成了直接插入排序。 **特点:*...

    JAVA排序汇总 java应用中一些比较经典的排序算法

    直接插入排序是将每个元素逐个插入已排序部分,而折半插入排序则是利用二分查找减少比较次数。希尔排序是插入排序的改进版,通过设置间隔序列来优化插入过程。 2. **交换排序**: 包括冒泡排序和快速排序。冒泡...

    排序算法-直接插入排序

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

    Java各种排序算法_随机数

    希尔排序是一种改进的插入排序算法,通过将整个待排记录序列分割成若干个子序列分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。 交换排序是指通过交换记录的位置来实现...

    java 直接插入排序

    直接插入排序是一种简单直观的排序算法,它的工作原理是通过构造一个有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。这种算法在最坏的情况下,时间复杂度为O(n^2),但在最好情况下,如...

    排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht

    排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht

    Java排序算法详细整理

    【Java排序算法详细整理】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。在Java中,实现各种排序算法有助于理解数据结构和算法的原理,同时也能提高编程能力。以下是对Java中常见的几种排序算法的详细...

    Java排序算法 Java排序算法.rar

    Java排序算法涉及了多种方法,用于组织数组或集合中的元素,使其按照特定顺序排列。以下是对这些算法的详细解释: 1. **冒泡排序(Bubble Sort)** 冒泡排序是一种简单直观的排序算法,它重复地遍历待排序的数列,一...

    Java常见排序算法源码集.rar

    在编程领域,排序算法是计算机科学中的核心概念,尤其是在Java这样的高级编程语言中。这个名为"Java常见排序算法源码集.rar"的压缩文件显然包含了多种常用的排序算法的Java实现,对于初学者来说,这是一个非常宝贵的...

    java八大排序算法

    排序算法是计算机科学中基础且重要的算法之一,它们在处理大量数据时起到关键作用。在Java编程中,了解并掌握不同的排序算法有助于优化代码性能,提高程序效率。以下是对Java八大排序算法的详细介绍: 1. **直接...

    java实现常见排序算法

    它通过将待排序的序列按照一定的增量分组,对每组使用直接插入排序算法排序,然后逐渐减少增量,直至增量为1,整个序列基本有序,最后再进行一次直接插入排序。希尔排序的时间复杂度在最坏的情况下为O(n^2),但在...

    常用的排序算法(java实现),附带一个PPT动画演示、详解了其中三种

    这里我们主要关注Java实现的排序算法,并结合一个PPT的动画演示来探讨其中的插入排序、直接插入排序和希尔排序。 首先,让我们深入理解插入排序。插入排序是一种简单的排序算法,其基本思想是将未排序的元素逐个...

    java实现数据结构常见排序算法及详解

    排序算法是计算机科学中的基础概念之一,主要用于将一系列数据按照特定规则进行排列。根据数据处理方式的不同,排序算法大致分为两大类:比较排序与非比较排序。 #### 比较排序 比较排序是指通过比较两个元素的大小...

    面试笔试必用-必须掌握的Java排序算法

    Java排序算法是编程面试和笔试中常见的考察点,掌握这些算法对于提升编程能力和解决实际问题至关重要。本篇文章将深入探讨几种主要的Java排序算法及其特点。 1. **插入排序** - **直接插入排序**:将每个元素依次...

Global site tag (gtag.js) - Google Analytics