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

直接插入排序——C语言描述

阅读更多

 

#include <stdio.h>
#define MAXSIZE 30

typedef int KeyType;
typedef int otherType;
typedef struct{
	KeyType key;
	otherType other;
}RecordType;

void straightInsertSort(RecordType R[],int n){
	int i,j;
	RecordType temp;
	//第一个元素是有序的
	i = 2;
	for(i=2;i<=n;i++){
		temp = R[i];
		for(j = i - 1;temp.key < R[j].key;j--)
			R[j+1] =R[j];
		R[j+1] = temp;
	}
}

int main(){
	RecordType R[MAXSIZE];
	int n = 5;
	int i;
	for(i=1;i<=n;i++){
		R[i].key = 22 - 2 * i;
	}
	straightInsertSort(R,5);
	for(i=1;i<=n;i++){
		printf("%d   ",R[i].key);
	}
	return 0;	
}

算法解析:

核心代码段:

 

RecordType temp;
	//第一个元素是有序的
	i = 2;
	for(i=2;i<=n;i++){
		temp = R[i];
		for(j = i - 1;temp.key < R[j].key;j--)
			R[j+1] =R[j];
		R[j+1] = temp;
	}

实例描述:

待排序数列:46 58 15 45 90 18 10 62

算法核心:取得数列的第a[i]个元素当成temp,已知有序的前i-1个元素的子数列,从后向前和子序列的值进行比较,若temp的key值不小于子序列的第j个元素的key值时,此趟插入结束,把temp放在子序列的第j+1个位置上。

 

直接插入的关键在于两步:

1 和有序子序列比较,而且是从后往前,若temp的key值小,则往前走,并将比较过的元素向后挪一个位置。

2 当temp的key值不小于当前比较的元素key值时,比较结束,把temp放在子序列的第j+1个位置上(因为j--仍在起作用)。

 

直接插入排序是稳定排序,时间复杂度为O(n^2),空间复杂度为O(1)

 

分享到:
评论

相关推荐

    插入排序 减治法——C语言代码

    总的来说,"插入排序 减治法——C语言代码"是一个学习和实践C语言基础排序算法的好例子,通过阅读和理解这段代码,你可以深入理解插入排序的工作原理,以及如何用C语言来实现它。同时,也可以探讨如何将问题解决策略...

    简单插入排序 递归法——C语言代码

    在"简单插入排序 递归法——C语言代码"这个项目中,我们将看到如何使用C语言实现一个递归版本的插入排序。C语言是一种强大的、低级别的编程语言,常用于系统编程、嵌入式开发和高性能计算等领域。它的语法简洁明了,...

    数据结构——C语言描述——耿国华版

    耿国华版的《数据结构——C语言描述》可能是一本详细讲解数据结构理论与C语言实现的教材。 本书可能会涵盖以下几个关键知识点: 1. **数组**:这是最基础的数据结构,允许我们存储和访问同类型元素的集合。书中会...

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

    《数据结构与算法分析——C语言描述》是一本在IT领域深受推崇的经典教材,尤其适合对数据结构、算法分析以及C语言感兴趣的读者。本书详细介绍了如何用C语言来实现和理解各种重要的数据结构和算法,旨在提升读者在...

    数据结构——C语言描述 第二版

    《数据结构——C语言描述(第二版)》是王路群教授编著的一本深入讲解数据结构的教材,特别强调了使用C语言实现各种数据结构的方法。这本书涵盖了数据结构的基础理论与实践应用,旨在帮助读者理解和掌握数据结构的...

    《数据结构——C语言描述(第二版)》

    《数据结构——C语言描述(第二版)》是王路群教授编著的一本经典教材,专注于通过C语言来阐述数据结构的理论与实践。在IT领域,数据结构是计算机科学的基础,它研究如何在内存中组织和管理数据,以便高效地进行存储...

    《数据结构——C语言描述(第二版)》-王路群-电子教案-4398.rar

    《数据结构——C语言描述(第二版)》是王路群教授编著的一本经典教材,专注于通过C语言来阐述数据结构的理论与实践。这本教材深入浅出地介绍了数据结构这一计算机科学中的核心概念,是计算机专业学生以及编程爱好者...

    《数据结构与算法分析——C语言描述》随书练习.zip

    《数据结构与算法分析——C语言描述》是计算机科学领域一本经典的教材,主要涵盖了数据结构和算法的基础理论以及实现方法,特别强调了C语言作为实现工具。这本书的随书练习通常包括一系列的问题和编程任务,旨在帮助...

    数据结构ppt《数据结构——C语言描述(第二版)》-王路群-电子教案-4398

    本教程《数据结构——C语言描述(第二版)》由王路群编写,是学习数据结构的理想教材。通过C语言描述,它深入浅出地解释了各种数据结构的实现细节,使学生能够更好地理解和掌握这些概念。 在数据结构的世界里,我们...

    算法与数据结构——C语言描述(第2版)

    《算法与数据结构——C语言描述(第2版)》是由张乃孝编著的一本经典教材,专注于通过C语言来阐述计算机科学中的核心概念——算法与数据结构。该书内容丰富,涵盖了从基础到高级的数据组织形式以及解决计算问题的...

    合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现

    本文将详细讲解六种经典的排序算法——合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合提供的文件名(sort.c、set.c、main.c、set.h、sort.h)推测出每个文件可能包含的代码实现。 1. **合并...

    算法与数据结构——c语言版+张乃孝

    书中可能涵盖了排序算法(如冒泡排序、插入排序、快速排序、归并排序)、查找算法(如线性搜索、二分查找)以及图算法(如深度优先搜索、广度优先搜索)等。这些基本算法的理解和熟练运用是每个程序员必备的技能。 ...

    《数据结构——用C语言描述》+课后题答案

    《数据结构——用C语言描述》是一本深入探讨数据结构理论和实现的教材,通过C语言来阐述各种数据结构的概念。书中的习题涵盖了顺序存储、链式存储、栈和队列等多种基本数据结构,旨在帮助读者理解并掌握数据结构的...

    数据结构 直接插入排序

    本篇文章将详细介绍如何通过编写C语言程序实现直接插入排序,并输出每次排序后的结果,以便观察排序过程中的变化。 #### 二、直接插入排序的基本原理 直接插入排序的基本思想是:将待排序的序列看作是由一个已排序...

    《数据结构——C语言版》本书范例+源码

    《数据结构——C语言版》是一本经典的计算机科学教材,主要涵盖了数据结构的基本概念、设计与实现,以及相关的算法分析。这本书使用C语言作为编程工具,使得读者能够深入理解数据结构的底层工作原理。源码部分是作者...

    数据结构(含实训)——C语言版(习题案例库).pdf

    5. **排序算法**:常见的排序算法有选择排序、堆排序、快速排序和直接插入排序。其中,直接插入排序是稳定的,而快速排序在最坏情况下时间复杂度是O(n^2)。 6. **循环队列**:循环队列利用数组存储,元素个数的计算...

    用C语言实现常用排序算法

    本项目旨在实现并比较六种经典的排序算法——直接插入排序、折半插入排序、起泡排序、简单选择排序、堆排序以及2-路归并排序,使用C语言编程。为了全面评估这些算法,我们将在一组随机生成的30000个整数上运行它们,...

    算法精解-C语言描述源代码

    《算法精解——C语言描述源代码》这本书深入浅出地介绍了如何使用C语言来实现各种重要的算法。这本书由Kyle Loudon撰写,旨在帮助读者掌握从排序到加密等一系列实用的算法技术。 首先,我们来看看“C语言”这个知识...

    数据结构课后题解答(C语言描述)

    4. **排序与查找**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序等经典的排序算法,以及二分查找、哈希查找等高效查找方法。 5. **递归与回溯**:在解决树和图问题时,递归和回溯是常用的技术,如深度...

    数据结构(含实训)——C语言版(习题案例库).docx

    12. **排序算法**:在选择排序、堆排序、快速排序和直接插入排序中,直接插入排序是稳定的排序方法,意味着相等的元素不会改变原有的相对顺序。 13. **双链表操作的时间复杂度**:在具有n个结点的双链表中进行插入...

Global site tag (gtag.js) - Google Analytics