链表插入排序的基本思想是:
在每个对象的结点中增加一个链域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); } } }
相关推荐
本篇文章将深入探讨如何使用C语言来实现单链表的值插入排序。 首先,我们需要定义链表节点的结构体。在C语言中,这通常通过以下方式完成: ```c typedef struct Node { int data; // 节点存储的数据 struct Node...
### 数据结构知识点:直接插入排序的单链表实现 #### 一、单链表简介 在计算机科学领域,链表是一种常见的线性数据结构。它由一系列节点组成,每个节点包含一个数据元素以及指向下一个节点的引用(或指针)。...
数据结构单链表插入、删除和修改实验报告 一、实验目的 1.理解数据结构中带头结点单链表的定义和逻辑图表示方法。 2.掌握单链表中结点结构的JAVA描述。 3.熟练掌握单链表的插入、删除和查询算法的设计与JAVA实现...
本文将详细探讨一种基于插入排序思想的单链表排序方法,并提供相应的C语言源代码实现。 #### 二、基础知识回顾 ##### 2.1 链表结构定义 链表是由一系列节点组成的线性数据结构,其中每个节点包括两部分:存储数据...
JAVA单链表(多项式)直接插入排序 JAVA单链表(多项式)直接插入排序
作为数据结构的基础,单链表,它的基本练习就是排序了,本文详细地给出其代码,供参考。
根据给定的信息,本文将详细解析两个主要的IT知识点:单链表排序和多项式分解。 ### 单链表排序 #### 基本概念 单链表是一种基本的数据结构,其中每个元素由数据和指向下一个元素的指针组成。在单链表排序中,我们...
接下来,我们要实现将一个具有特定值`X`的新节点插入到单链表中,使得单链表保持递增排序。 **代码解析:** ```c LinkList InsX(LinkList L, int X) { LinkList p, q, temp; temp = (LinkNode*)malloc(sizeof...
标题和描述中提到的是关于"C++实现单链表的选择排序"的主题,这涉及到计算机科学中的数据结构和算法知识。在C++编程语言中,单链表是一种基础的数据结构,用于存储一系列元素,每个元素(节点)包含数据和指向下一个...
排序是数据处理中的常见任务,有多种不同的排序算法,如冒泡排序、选择排序、插入排序、快速排序等。在这个项目中,你将学习如何在链表上实现这些排序算法。链表排序的一个挑战是其动态性,不像数组那样可以直接访问...
单链表的排序插入通常有两种主要方法:直接插入排序和归并排序。这里我们将重点讨论直接插入排序,因为它是基于原链表的简单且直观的方法。 **直接插入排序**的基本思想是遍历链表,将新元素与当前链表中的元素进行...
《C语言实现学生成绩管理——基于单链表、排序与节点操作》 在计算机科学的学习过程中,C语言作为基础编程语言,常常被用于教授数据结构和算法。本项目旨在通过C语言实现一个简单的学生成绩管理系统,涵盖了单链表...
这里我们将以简单的插入排序为例,介绍如何对单链表进行排序。 **插入排序**的基本思想是将未排序的元素逐个插入到已排序的部分,从而保持已排序部分的顺序。对于链表,这个过程比数组更容易实现,因为我们可以直接...
单链表做存储结构的直接插入排序
该压缩包包含的是一个基于Java实现的班级考勤管理系统的完整源代码,涵盖了GUI界面设计、数据结构(顺序表、单链表)以及插入排序算法的应用。以下将详细阐述其中涉及的知识点: 1. **Java编程语言**:Java是一种跨...
- **二分查找**:适用于有序链表,但单链表通常不保持排序,所以不常用。 4. **反转链表**:通过改变节点间的指针方向,使得原本的后续节点变为前驱节点。 5. **合并链表**:将两个已排序的链表合并成一个有序...
单链表是计算机科学中一种基础的数据结构..."order_link.c"则演示了如何通过插入排序方法对单链表进行排序,涉及到了在链表中查找插入位置和插入节点的操作。这两个操作都是理解和掌握链表这一核心数据结构的关键实践。
单向链表实现倒置,冒泡排序,插入排序,快速排序,在linux下的gcc实现
【数据结构单链表的排序与初始化、显示】 在计算机科学中,数据结构是组织和存储数据以便高效地访问和管理的重要方式。单链表是一种简单但非常实用的数据结构,它由一系列节点组成,每个节点包含一个数据元素和一个...
CreateFromTail函数用于尾插入法建立单链表,通过scanf函数读取数据,并将其存储在单链表中。print函数用于打印单链表中的元素。 sort函数是选择排序算法的实现,通过遍历单链表,找到未排序的最小元素,并将其与...