直接插入排序与希尔排序

代码是何其的相似啊!!

/*
	Name: InsertSort
	Copyright:
	Author: huowolf
	Date: 05/07/15 16:18
	Description: 直接插入排序的实现
*/

#include <iostream>
using namespace std;

int arr[]={-1,48,62,35,77,55,14,35,98};

void InsertSort(int a[],int length);
void Output(int a[],int length);

int main()
{
	InsertSort(arr,8);
	Output(arr,8);
	return 0;
}

void InsertSort(int a[],int length)
{
	int i,j;
	for(i=2;i<=length;i++)
	{
		if(a[i]<a[i-1])
		{
			a[0] = a[i];				//拷贝为哨兵
			for(j=i-1;a[0]<a[j];j--)
				a[j+1]=a[j];			//记录后移,寻找插入位置
			a[j+1] = a[0];				//插入
		}
	}
}

void Output(int a[],int length)
{
	for(int i=1;i<=length;i++)
		cout<<a[i]<<"  ";
}
/*
	Name: ShellSort
	Copyright:
	Author: huowolf
	Date: 05/07/15 16:18
	Description: 希尔排序的实现
*/

#include <iostream>
using namespace std;

int arr[]={-1,48,62,35,77,55,14,35,98};

void ShellSort(int a[],int length);
void Output(int a[],int length);

int main()
{
	ShellSort(arr,8);
	Output(arr,8);
	return 0;
}

void ShellSort(int a[],int length)
{
	int i,j;
	int d = length;				//将增量初始化为表长
	do{
		d = d/3+1;				//增量序列	(一种比较经典的增量取法,但并没有给出最优性证明)
		for(i=d+1;i<=length;i++)
		{
			if(a[i]<a[i-d])							//在同一子序列中相邻的前后元素
			{
				a[0] = a[i];
				for(j=i-d;j>0 && a[0]<a[j];j-=d)	//记录后移,寻找插入位置
					a[j+d] = a[j];
				a[j+d] = a[0];
			}
		}
	}while(d>1);//增量为1,停止循环
}

void Output(int a[],int length)
{
	for(int i=1;i<=length;i++)
		cout<<a[i]<<"  ";
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 07-03

直接插入排序与希尔排序的相关文章

数据结构精要------直接插入排序和希尔排序算法

上篇总结中主要实践了算法的内排序的选择排序,那么接下来我们继续实践插入排序排序的两种:直接插入排序和希尔排序算法. -----直接插入排序 package com.sort; /** * 直接插入排序 * * @author weixing-yang * * 算法思路: * 每步将一个待排序的元素,插入到前面已排序好的一组元素中的适当位置, * 直到所有元素全部出入完成为止. */ public class InsertionSort { public void insertionSort(in

插入排序 | 冒泡排序 | 希尔排序 | 堆排序 | 快速排序 | 选择排序 | 归并排序

以下是最近学习各种算法的代码实现: #include <stdlib.h> #include <stdio.h> #include <time.h> #include <limits.h> typedef int EleType; typedef int (*CompFunc)(void *,void *); int IntComp(void * a,void *b) { if(*(int *)a > *(int *)b) return 1; if(*

java排序之插入排序(直接插入排序和希尔排序)

上面一片博文探讨了关于的java选择排序(冒泡排序和快速排序)本章将继续探讨java排序之插入排序,插入排序分为直接插入排序和希尔排序两种. 1.直接插入排序思想:在需要排序的一组数据中假设前该数组的前n-1(n >= 2)个数是已经排好序的,现在要把第n个数插入到前面的n-1个数中,使得这n个数也是排好顺序的.如此反复进行,知道n等于需要排序的数组的长度时.就实现了该数组的直接插入排序. 代码如下: /** * * @param a 需要排序的数组 */ public static void

数据结构例程——插入排序之希尔排序

本文是[数据结构基础系列(9):排序]中第3课时[插入排序之希尔排序]的例程. 1.希尔排序 #include <stdio.h> #define MaxSize 20 typedef int KeyType; //定义关键字类型 typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; //排序的记录类型定义 void

#排序算法#【2】直接插入排序、希尔排序

直接插入排序法 插入排序的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后移动,为最新元素提供插入空间. 核心代码: //直接插入排序法 void InsertSort(int a[],int n){ int i,j,k,t; for(i = 1 ; i<n;i++){ k = a[i]; /* 第一次比较粗糙的写法 j = i-1; while(

插入排序,希尔排序,堆排序详解

本文将介绍三种排序算法--插入排序,希尔排序,堆排序.本文所有例子都是使用升序 一.插入排序 算法思想 维护一个有序数组,将要插入的数据与有序数组自最后一个元素直到合适位置的数一一比较. eg: 有序数组:1,3,5,6,7   现在待插入数据为2,那么他将会和7,6,5,3,依次作比较,当带插入数据小于有序数组最后的元素大小,则将该元素后移,直到待插入元素找到合适位置为止. 代码实现 void InsertSort(int* a, int size) 02 { 03     assert(a)

插入排序,希尔排序,堆排序

本文将介绍三种排序算法--插入排序,希尔排序,堆排序.本文所有例子都是使用升序 一.插入排序 算法思想 维护一个有序数组,将要插入的数据与有序数组自最后一个元素直到合适位置的数一一比较. eg: 有序数组:1,3,5,6,7   现在待插入数据为2,那么他将会和7,6,5,3,依次作比较,当带插入数据小于有序数组最后的元素大小,则将该元素后移,直到待插入元素找到合适位置为止. 代码实现 void InsertSort(int* a, int size) { assert(a); for (int

数据结构之插入排序与希尔排序

1.直接插入排序 直接插入排序是一种最简单的排序算法,它的基本操作是将一个记录插入到已经排序好的序列中,从而得到一个新的有序表.直接插入排序算法原理如下图所示: 直接插入排序算法如下: void InsertSort(int arr[],int length) { int key,j; for(int i=1;i<length;++i) { key=arr[i]; //记录标志; j=i-1; //循环比较并且交换相邻的两个数; while (j>=0&&arr[j]>k

直接插入排序&&冒泡排序&&希尔排序(缩小增量排序)源码

public class DirectRank { public static void main(String[] args) { DirectRank aa=new DirectRank(); try { aa.judge(args); } catch (TestDefinException e2) { e2.printStackTrace(); } Integer[] a=new Integer[args.length]; try{for(int i=0;i<args.length;i++

优化的直接插入排序(二分查找插入排序,希尔排序)

直接插入排序 (一)概念及实现 直接插入排序的原理:先将原序列分为有序区和无序区,然后再经过比较和后移操作将无序区元素插入到有序区中. 具体如下(实现为升序): 设数组为a[0…n]. 1.        将原序列分成有序区和无序区.a[0…i-1]为有序区,a[i…n] 为无序区.(i从1开始) 2.        从无序区中取出第一个元素,即a[i],在有序区序列中从后向前扫描. 3.        如果有序元素大于a[i],将有序元素后移到下一位置. 4.        重复步骤3,直到找