汉扬编程 编程大纲 C/C++基础之插入排序

C/C++基础之插入排序

前两篇跟大家讲了C/C++基础数组排序的选择排序和冒泡排序,现在再给大家分享一下插入排序算法:

C/C++基础之插入排序

插入排序其实插入排序跟我们军训排队一样的,军训排队一般是按各人身高排的,个矮的站前面,个高的站后面:

C/C++基础之插入排序

他的操作是:将一个数插入到其他已经有序的数组中适当的位置(按一定规则)比如排队,他就需要站在一个比他矮的人后面但是比他高的人前面的位置,然后为了给他挪出来一个位置,他后面的人是不是都应该要挪开一个位置呢?

C/C++基础之插入排序

还是假设我们有一个数组{50,26,74,60,12,1,100},我们要怎么做呢?

C/C++基础之插入排序

如上图,我首先取数组第一个(50)组成一个现有队列,然后逐一再从原始序列中取出数据插入到现有队列中适当位置,这样只需要(数组长度-1)次循环就可以完成工作。

我们看下代码怎么实现:

看下运行结果,确认下有没有问题:

OK,没有问题。

其实插入排序的核心就是:将元素插入已有序列,逐一跟现有序列元素比较,然后满足比较条件的就换位置,知道找到自己合适的位置。

最后奉上源代码:

#include <stdio.h>

#include <iostream>

using namespace std;

int main()

{

int arr[7] = {50,26,74,60,12,1,100};\\

//從第二個元素開始去插入,所以從i=1開始

for (int i = 1; i < sizeof(arr)/sizeof(int); i++)

{

//这个循环就是我在图示中表示的过程,最大的从前往后滚

for (int j = i; j >0; j–)

{

if(arr[j]<arr[j-1])

{

int temp = arr[j];

arr[j] = arr[j-1];

arr[j-1] = temp ;

}

}

}

//我们来输出一下看看排序成功没

for (int i = 0; i < sizeof(arr)/sizeof(int); i++)

{

cout<<arr[i]<<\” \”;

}

system(\”pause\”);

return 0 ;

}

C语言:数据结构-直接插入排序

直接插入排序 (1)直接插入排序的基本思想

C/C++基础之插入排序

直接插入排序(Straight Insertion Sort)算法是一种常用且简单直观的方法。它的基本思想是:设有n个数据的待排序序列,假设前面1到i-1个数据已经有序,是长度为i-1的有序序列,将第i个数据逐次与第i-1个数据、第i-2个数据……进行比较,直到找到第i个数据的插入位置,并插入得到一个新的长度为i的有序数列。这一过程称为一趟插入,对第i个元素的插入称为第i趟插入。

(2)直接插入排序的步骤

首先令i=1,取第一个元素,得到长度为1的序列,再令i=2,完成对第二个数据的第二趟插入,得到长度为2的有序序列,以下逐次令i=3,4,…,直到完成对第n个元素的第n趟插入,得到长度为n的有序序列。

例如一组待排序的数据记录的关键字为:47,83,41,53,68,经5趟插入完成排序的过程如下:

取第一个元素 47 第二趟 47 83 第三趟 41 47 83 第四趟 41 47 53 83 第五趟 41 47 53 68 83 直接插入排序算法 void disort(NODE a[],int n) /*对存放在a[0],a[1],…a[n-1]中,长度为n的序列进行排序*/ { int i,j; NODE temp; for(i=1;i<n;i++) /*从a[1]开始到a[n-1]进行n-1趟插入*/ { temp=a[i]; /*把a[i]暂时保存*/ j=i-1; /*从a[i]前边的第一个元素开始比较*/ while(j>=0&&temp.key<a[j].key) { a[j+1]=a[j]; /*边比较边后移*/ j– ; /*向前边再取一个元素比较*/ } a[j+1]=temp; /*第i号元素插入到位*/ } } (4)直接插入排序的算法分析

最好情况:待排序记录已有序

例:1 2 3 4 5 … n,每个元素的插入进行一次比较,所以进行了(n-1)次比较。

最坏情况:待排序记录已反向有序,第 i 个元素的插入进行(i-1)次比较

例:5 4 3 2 1,

,时间复杂度为O(n 2 )。

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/6016.html

一种简单的优化C函数重复调用的方法

丹尼斯·里奇-c语言之父,Unix之父,我们是站在巨人肩膀上

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部