`
BradyZhu
  • 浏览: 245535 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

(数据结构与算法分析 八)------插入排序,希尔排序,归并排序的实现( Java语言描述)

 
阅读更多

首先是插入排序,原理没什么好说的

package com.bird.seven;
/**
 * 插入排序的实现
 * @author Bird
 *
 */
public class InsertSort {
	
	public static void insertSort(int[] a){
		int j;
		for(int i = 1; i < a.length; i++){
			int temp = a[i];
			
			for(j = i; j > 0 && temp < a[j-1]; j--)
				a[j] = a[j-1];
			a[j] = temp;
		}
	}
	
	public static void main(String[] args){
		int[] a = {34,8,64,51,32,21};
		insertSort(a);
		for(int t : a)
			System.out.print(t+" ");
	}
}

运行结果为

8 21 32 34 51 64 

然后是希尔排序

package com.bird.seven;
/**
 * 希尔排序的实现
 * @author Bird
 *
 */
public class ShellSort {
	
	public static void shellSort(int [] a){
		for(int gap = a.length/2; gap > 0; gap /= 2){
			for(int i = gap; i < a.length; i++){
				int temp = a[i];
				int j = i;
				
				for(; j >= gap&&temp < a[j-gap]; j -= gap)
					a[j] = a[j-gap];
				a[j] = temp;
			}
		}
	}
	
	
	public static void main(String [] args){
		int [] a = {81,94,11,96,12,35,178,95,28,58,41,75,15};
		shellSort(a);
		for(int t : a)
			System.out.print(t + " ");
	}
}

运行结果为

11 12 15 28 35 41 58 75 81 94 95 96 178 

归并排序为

package com.bird.seven;
/**
 * 归并排序的实现
 * @author Bird
 *
 */
public class MergeSort {
	
	public static void mergeSort(int[] a, int[] temp, int left, int right){
		if(left < right){
			int center = (left + right)/2;
			mergeSort(a,temp,left,center);
			mergeSort(a,temp,center+1,right);
			merge(a,temp,left,center+1,right);
		}
	}
	
	public  static void mergeSort(int [] a){
		int [] temp = new int [a.length];
		mergeSort(a,temp,0,a.length-1);
	}

	private static void merge(int[] a, int[] temp, int leftPos, int rightPos, int rightEnd) {
		int leftEnd = rightPos -1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;
		
		while(leftPos <= leftEnd && rightPos <= rightEnd){
			if(a[leftPos] <= a[rightPos])
				temp[tmpPos++] = a[leftPos++];
			else
				temp[tmpPos++] = a[rightPos++];
			
			while(leftPos <= leftEnd)
				temp[tmpPos++] = a[leftPos++];
			
			while(rightPos <= rightEnd)
				temp[tmpPos++] = a[rightPos++];
			
			for(int i = 0 ; i < numElements; i++, rightEnd--){
				a[rightEnd] = temp[rightEnd];
			}
		}
	}
	
	
	public static void main(String [] args){
		int [] a = {81,94,11,96,12,35,178,95,28,58,41,75,15};
		mergeSort(a);
		for(int t : a)
			System.out.print(t + " ");
	}
}

运行结果为

11 12 15 28 35 41 58 75 81 94 95 96 178 


分享到:
评论

相关推荐

    数据结构与算法分析_Java语言描述(第2版)]

    Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。随着计算机速度的不断增加和功能...

    数据结构与算法分析_Java语言描述(第2版)

    《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...

    数据结构与算法分析Java语言描述(第二版)

    堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1...

    常用数据结构及其算法的Java实现

    八大排序算法及其实现,具体包括直接插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序,归并排序,基数排序在内的八种排序算法,同时对各种算法的基本特征做出了详细分析: - 算法基本思想 - 算法的...

    数据结构与算法分析-Java语言描述(第2版)_2_2

    练习 参考文献第7章 排序 7.1 预备知识 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 ...

    数据结构与算法分析-Java语言描述(第2版)_1_2

    练习 参考文献第7章 排序 7.1 预备知识 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 ...

    Java数据结构与算法-笔记-代码-课件-资料

    稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...

    数据结构与算法分析 Java语言描述第2版

    内容简介《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...

    随手笔记--数据结构与算法(Java)排序

    六个基础排序算法,分别是冒泡排序,选择排序,插入排序,希尔排序,归并排序和快速排序;2.了解这六种算法的时间复杂度和稳定性; 阅读建议:建议在阅读过程中,可以尽量自己手动敲一遍,让印象更深刻,不要Ctrl+C...

    java数据结构与算法第二版

    数据结构和算法能起到什么作用? 数据结构的概述 算法的概述 一些定义 面向对象编程 软件工程 对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将...

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

    7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 ...

    各种排序算法的详细分析

    此为一个利用Java语言编写的排序分析程序,程序中统计了各种排序算法(冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序、归并排序、基数排序)的分析,ppt中包含各种排序算法的分析,附上动画演示(来自...

    Data-Structure:《数据结构与算法分析》上的代码实现

    《数据结构与算法分析》上的代码实现, 按照该书的章节顺序,主要实现书上给出的例子。 ##已经实现: ###第三章 - 链表 - 栈 - 队列 ###第四章 - 排序二叉树 - 平衡二叉树 - 伸展树(自底向上) - 伸展树(自顶往下)...

    Java数据结构和算法

    (1)数据结构与算法概念解析 (2)数据结构之数组 (3)数据结构之栈 (4)数据结构之队列 (5)数据结构之链表 (6)数据结构之二叉树 (7)数据结构之霍夫曼树 (8)数据结构之红黑树(一)——基础分析 ...

    Java数据结构与算法视频教程

    课程内容第一章: 数据结构与算法概述; 算法分析; 冒泡排序; 选择排序; 插入排序; 希尔排序; 归并排序;第二章: 快速排序; 排序稳定性分析; 顺序表; 链表;第三章: 栈; 队列; 符号表; 二叉查找树;第...

    【超全!】图解Java数据结构和算法(共195集)【资料+视频+课件+代码+笔记】

    稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...

    数据结构与算法.xmind

    数据结构与算法 排序算法 内排序 八大基础排序 选择排序 简单选择排序 思想 每次选择最大的数插入到末尾中 做法 外层for循环控制次数 内层for循环找出最大的值的角...

    算法 第4版-谢路云译-带完整书签

    1.4 算法分析 108 1.4.1 科学方法 108 1.4.2 观察 108 1.4.3 数学模型 112 1.4.4 增长数量级的分类 117 1.4.5 设计更快的算法 118 1.4.6 倍率实验 121 1.4.7 注意事项 123 1.4.8 处理对于输入的...

Global site tag (gtag.js) - Google Analytics