`

单链表插入排序

阅读更多

链表插入排序的基本思想是:

      在每个对象的结点中增加一个链域link。

        对于存放于数组中的一组对象V[1],V[2],…,V[n],若V[1],V[2],…,V[i-1]已经通过链接指针link,按其排序码的大小,从小到大链接起来

        现在要插入V[i],i=2,3,…,n,则必须在前面i-1个链接起来的对象当中,循链顺序检测比较,找到V[i]应插入(链入)的位置,把V[i]插入,并修改相应的链接指针

        这样就可得到V[1],V[2],…,V[i]的一个通过链接指针排列好的链表。如此重复执行,直到把V[n]也插入到链表中排好序为止。

      
      

public class ListInsertionSort {
	public static void sort(int[] v) {
		int n = v.length;

		// step 1: link[] creation
		int[] link = new int[n];//链表,存储对应数组每个元素所指向的下一个索引下标
		int head = 0;//记录数组中最小值的下标,即头元素
		int next = 0;//记录链表中链接指针,指向下一个索引下标
		int curr = 0;//记录循环中遍历的当前位置下标
		link[0] = -1;
		for (int i = 1; i < n; i++) {
			System.out.println("=============================");
			if (v[head] > v[i]) { // case: head is changed to i
				link[i] = head;
				head = i; // change head
			} else {
				// two stop cases:
				// curr == -1: when we reach the tail
				// v[curr] > v[i]: insert i before curr, next is the predecessor
				// of curr
				// note: this loop executes at least once so 'next' always have
				// valid value
				for (curr = head; curr != -1 && v[curr] <= v[i]; curr = link[curr])
				{
					next = curr;
				}
					
				// insert i between next and curr (also applicable to tail case
				// when curr=-1)
				link[next] = i;
				link[i] = curr;
				
			}
		}

		// step 2: arrange v[] by link[] information: find curr and swap it with
		// i
		curr = head; // to scan linked list, always start with head
		
		// note the difference:
		// in this step: between iterations, curr doesn't start with head at the
		// beginning
		// the link creation step: between iterations, we always scan from
		// curr=head to find the insert position
		for (int i = 0; i < n; i++) {
			while (curr < i)
				curr = link[curr]; // look only those elements on the right side
									// of current element

			next = link[curr]; // save for next iteration's start position
			if (curr != i) { // if curr==i, no need change since position i is
								// done.
				int swap = v[i]; // swap key
				v[i] = v[curr];
				v[curr] = swap;

				link[curr] = link[i]; // copy i's link
				link[i] = curr; // reset pointer link[i] for redirection
			}
			curr = next; // next iteration we start from 'next'
		}

		// link[] is now useless, let it be garbage collected.
	}

	public static void main(String[] args) {
		int[] v = { 49, 38, 65, 97, 76, 13, 27, 49 };
		ListInsertionSort.sort(v);

		for (int key : v) {
			System.out.format(" %d", key);
		}
	}
}

 
 

  • 大小: 8.8 KB
分享到:
评论

相关推荐

    用C写的单链表的值插入排序

    本篇文章将深入探讨如何使用C语言来实现单链表的值插入排序。 首先,我们需要定义链表节点的结构体。在C语言中,这通常通过以下方式完成: ```c typedef struct Node { int data; // 节点存储的数据 struct Node...

    直接插入排序的单链表的实现

    ### 数据结构知识点:直接插入排序的单链表实现 #### 一、单链表简介 在计算机科学领域,链表是一种常见的线性数据结构。它由一系列节点组成,每个节点包含一个数据元素以及指向下一个节点的引用(或指针)。...

    数据结构单链表插入、删除和修改实验报告

    数据结构单链表插入、删除和修改实验报告 一、实验目的 1.理解数据结构中带头结点单链表的定义和逻辑图表示方法。 2.掌握单链表中结点结构的JAVA描述。 3.熟练掌握单链表的插入、删除和查询算法的设计与JAVA实现...

    单链表的排序,c源代码

    本文将详细探讨一种基于插入排序思想的单链表排序方法,并提供相应的C语言源代码实现。 #### 二、基础知识回顾 ##### 2.1 链表结构定义 链表是由一系列节点组成的线性数据结构,其中每个节点包括两部分:存储数据...

    JAVA单链表(多项式)直接插入排序

    JAVA单链表(多项式)直接插入排序 JAVA单链表(多项式)直接插入排序

    用单链表实现插入排序

    作为数据结构的基础,单链表,它的基本练习就是排序了,本文详细地给出其代码,供参考。

    单链表排序和多项式分解

    根据给定的信息,本文将详细解析两个主要的IT知识点:单链表排序和多项式分解。 ### 单链表排序 #### 基本概念 单链表是一种基本的数据结构,其中每个元素由数据和指向下一个元素的指针组成。在单链表排序中,我们...

    单链表的创建和插入

    接下来,我们要实现将一个具有特定值`X`的新节点插入到单链表中,使得单链表保持递增排序。 **代码解析:** ```c LinkList InsX(LinkList L, int X) { LinkList p, q, temp; temp = (LinkNode*)malloc(sizeof...

    C++,单链表选择排序.rarC++,单链表选择排序.rar

    标题和描述中提到的是关于"C++实现单链表的选择排序"的主题,这涉及到计算机科学中的数据结构和算法知识。在C++编程语言中,单链表是一种基础的数据结构,用于存储一系列元素,每个元素(节点)包含数据和指向下一个...

    数据结构课程设计 图形界面 单链表和排序的应用

    排序是数据处理中的常见任务,有多种不同的排序算法,如冒泡排序、选择排序、插入排序、快速排序等。在这个项目中,你将学习如何在链表上实现这些排序算法。链表排序的一个挑战是其动态性,不像数组那样可以直接访问...

    Q1045564.zip 问题回答的代码 关于单链表排序插入

    单链表的排序插入通常有两种主要方法:直接插入排序和归并排序。这里我们将重点讨论直接插入排序,因为它是基于原链表的简单且直观的方法。 **直接插入排序**的基本思想是遍历链表,将新元素与当前链表中的元素进行...

    C语言 学生成绩管理(单链表,排序,节点增加删除等).rar

    《C语言实现学生成绩管理——基于单链表、排序与节点操作》 在计算机科学的学习过程中,C语言作为基础编程语言,常常被用于教授数据结构和算法。本项目旨在通过C语言实现一个简单的学生成绩管理系统,涵盖了单链表...

    简单的单链表排序 —— 学生管理程序

    这里我们将以简单的插入排序为例,介绍如何对单链表进行排序。 **插入排序**的基本思想是将未排序的元素逐个插入到已排序的部分,从而保持已排序部分的顺序。对于链表,这个过程比数组更容易实现,因为我们可以直接...

    单链表做存储结构的直接插入排序

    单链表做存储结构的直接插入排序

    班级考勤管理系统程序代码+实现GUI界面设计+JAVA实现+数据结构(顺序表、单链表、插入排序算法)+程序要求+程序说明书.rar

    该压缩包包含的是一个基于Java实现的班级考勤管理系统的完整源代码,涵盖了GUI界面设计、数据结构(顺序表、单链表)以及插入排序算法的应用。以下将详细阐述其中涉及的知识点: 1. **Java编程语言**:Java是一种跨...

    单链表的基本操作及实现

    - **二分查找**:适用于有序链表,但单链表通常不保持排序,所以不常用。 4. **反转链表**:通过改变节点间的指针方向,使得原本的后续节点变为前驱节点。 5. **合并链表**:将两个已排序的链表合并成一个有序...

    单链表的倒序以及排序

    单链表是计算机科学中一种基础的数据结构..."order_link.c"则演示了如何通过插入排序方法对单链表进行排序,涉及到了在链表中查找插入位置和插入节点的操作。这两个操作都是理解和掌握链表这一核心数据结构的关键实践。

    单向链表实现倒置,冒泡排序,插入排序,快速排序

    单向链表实现倒置,冒泡排序,插入排序,快速排序,在linux下的gcc实现

    数据结构单链表的排序与初始化、显示

    【数据结构单链表的排序与初始化、显示】 在计算机科学中,数据结构是组织和存储数据以便高效地访问和管理的重要方式。单链表是一种简单但非常实用的数据结构,它由一系列节点组成,每个节点包含一个数据元素和一个...

    单链表存储结构简单选择排序.pdf

    CreateFromTail函数用于尾插入法建立单链表,通过scanf函数读取数据,并将其存储在单链表中。print函数用于打印单链表中的元素。 sort函数是选择排序算法的实现,通过遍历单链表,找到未排序的最小元素,并将其与...

Global site tag (gtag.js) - Google Analytics