`

数据结构

算法 
阅读更多

1.插入排序

 

基本思想:

 

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

 

要点：设立哨兵，作为临时存储和判断数组边界之用。

 

直接插入排序示例：

 

 

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法的实现：

 

Java代码 复制代码 收藏代码
  1. public class ArraySort {   
  2.   
  3.     public static void main(String[] args) {   
  4.         ArraySort sort = new ArraySort();   
  5.   
  6.       // 插入排序排序后的数组   
  7.         int[] charu = sort.SortChaRu(arraysort);   
  8.         for (int n = 0; n < charu.length; n++) {   
  9.             //System.out.println(charu[n]);   
  10.         }   
  11.   
  12.   
  13. /**  
  14.      * 插入排序的方法  
  15.      *   
  16.      * @param ChaRuSort  
  17.      *            传入的原始数据  
  18.      * @return 返回排序后的数组  
  19.      */  
  20.     public int[] SortChaRu(int[] ChaRuSort) {   
  21.         for (int i = 0; i < ChaRuSort.length; i++) {   
  22.             for (int j = i; j > 0; j--) {   
  23.                 if (ChaRuSort[j] < ChaRuSort[j - 1]) {   
  24.                     int temp = ChaRuSort[j];   
  25.                     ChaRuSort[j] = ChaRuSort[j - 1];   
  26.                     ChaRuSort[j - 1] = temp;   
  27.                 }   
  28.             }   
  29.         }   
  30.   
  31.         return ChaRuSort;   
  32.   
  33.     }  
public class ArraySort {

	public static void main(String[] args) {
		ArraySort sort = new ArraySort();

      // 插入排序排序后的数组
		int[] charu = sort.SortChaRu(arraysort);
		for (int n = 0; n < charu.length; n++) {
			//System.out.println(charu[n]);
		}


/**
	 * 插入排序的方法
	 * 
	 * @param ChaRuSort
	 *            传入的原始数据
	 * @return 返回排序后的数组
	 */
	public int[] SortChaRu(int[] ChaRuSort) {
		for (int i = 0; i < ChaRuSort.length; i++) {
			for (int j = i; j > 0; j--) {
				if (ChaRuSort[j] < ChaRuSort[j - 1]) {
					int temp = ChaRuSort[j];
					ChaRuSort[j] = ChaRuSort[j - 1];
					ChaRuSort[j - 1] = temp;
				}
			}
		}

		return ChaRuSort;

	}

 

运算结果:

Java代码 复制代码 收藏代码
  1. 原始数据11  
  2. 原始数据22  
  3. 原始数据332  
  4. 原始数据223  
  5. 原始数据20  
  6. 原始数据234  
  7. 11  
  8. 20  
  9. 22  
  10. 223  
  11. 234  
  12. 332   
原始数据11
原始数据22
原始数据332
原始数据223
原始数据20
原始数据234
11
20
22
223
234
332

 

 

 

 

 

 2. 插入排序—希尔排序

 

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：

  1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  2. 按增量序列个数k，对序列进行k 趟排序；
  3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序的示例：

 

算法实现：

 

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

 

算法的实现：

Java代码 复制代码 收藏代码
  1. public class ArraySort {   
  2.   
  3.     public static void main(String[] args) {   
  4.         ArraySort sort = new ArraySort();   
  5.   
  6.         // 排序的原始数组   
  7.         int[] arraysort = { 11, 22, 332, 223, 20, 234 };   
  8.         // 遍历出原始数据   
  9.         for (int i = 0; i < arraysort.length; i++) {   
  10.             System.out.println("原始数据" + arraysort[i]);   
  11.         }   
  12.        
  13.         //希尔排序   
  14.         int[] xier = sort.SortXiEr(arraysort);   
  15.         for(int x = 0;x<xier.length;x++){   
  16.             //System.out.println(xier[x]);   
  17.         }   
  18.   
  19.     }   
  20.   
  21. /**  
  22.      * 希尔排序的方法  
  23.      *   
  24.      * @param XiErSort  
  25.      *            数组的原始数据  
  26.      * @return 返回排序后的数据  
  27.      */  
  28.     public int[] SortXiEr(int[] XiErSort) {   
  29.         // 分组   
  30.         for (int increment = XiErSort.length / 2; increment > 0; increment /= 2) {   
  31.             //每组内部排序   
  32.             for (int i = increment; i < XiErSort.length; i++) {   
  33.                 int temp = XiErSort[i];   
  34.                 int j = 0;   
  35.                 for (j = i; j >= increment; j -= increment) {   
  36.                     if (temp < XiErSort[j - increment]) {   
  37.                         XiErSort[j] = XiErSort[j - increment];   
  38.                     } else {   
  39.                         break;   
  40.                     }   
  41.                 }   
  42.                 XiErSort[j] = temp;   
  43.             }   
  44.         }   
  45.         return XiErSort;   
  46.   
  47.     }   
  48.   
  49. }  
public class ArraySort {

	public static void main(String[] args) {
		ArraySort sort = new ArraySort();

		// 排序的原始数组
		int[] arraysort = { 11, 22, 332, 223, 20, 234 };
		// 遍历出原始数据
		for (int i = 0; i < arraysort.length; i++) {
			System.out.println("原始数据" + arraysort[i]);
		}
	
		//希尔排序
		int[] xier = sort.SortXiEr(arraysort);
		for(int x = 0;x<xier.length;x++){
			//System.out.println(xier[x]);
		}

	}

/**
	 * 希尔排序的方法
	 * 
	 * @param XiErSort
	 *            数组的原始数据
	 * @return 返回排序后的数据
	 */
	public int[] SortXiEr(int[] XiErSort) {
		// 分组
		for (int increment = XiErSort.length / 2; increment > 0; increment /= 2) {
			//每组内部排序
			for (int i = increment; i < XiErSort.length; i++) {
				int temp = XiErSort[i];
				int j = 0;
				for (j = i; j >= increment; j -= increment) {
					if (temp < XiErSort[j - increment]) {
						XiErSort[j] = XiErSort[j - increment];
					} else {
						break;
					}
				}
				XiErSort[j] = temp;
			}
		}
		return XiErSort;

	}

}

 

 

 

 

 

3. 选择排序

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例：

 

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推.....

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

算法实现：

Java代码 复制代码 收藏代码
  1. public class ArraySort {   
  2.   
  3.     public static void main(String[] args) {   
  4.         ArraySort sort = new ArraySort();   
  5.   
  6.         // 排序的原始数组   
  7.         int[] arraysort = { 11, 22, 332, 223, 20, 234 };   
  8.         // 遍历出原始数据   
  9.         for (int i = 0; i < arraysort.length; i++) {   
  10.             System.out.println("原始数据" + arraysort[i]);   
  11.         }   
  12. // 选择排序排序后的数组   
  13.         int[] xuanze = sort.SortXuanZe(arraysort);   
  14.         for (int j = 0; j < xuanze.length; j++) {   
  15.             // System.out.println(xuanze[j]);   
  16.         }   
  17.       }   
  18.   
  19. /**  
  20.      * 选择排序排序数组  
  21.      *   
  22.      * @param XuanZesort  
  23.      *            传入的数组  
  24.      * @return 返回排序后的数组  
  25.      *   
  26.      *         思路:在遍历数组时先把第一个当作最小的,然后与后面的比较  
  27.      */  
  28.     public int[] SortXuanZe(int[] XuanZesort) {   
  29.   
  30.         for (int i = 0; i < XuanZesort.length; i++) {   
  31.             // 假设i是最小的数   
  32.             int lowerIndex = i;   
  33.   
  34.             for (int j = i + 1; j < XuanZesort.length; j++) {   
  35.                 if (XuanZesort[j] < XuanZesort[lowerIndex]) {   
  36.                     // 此时j是最小的   
  37.                     lowerIndex = j;   
  38.                 }   
  39.             }   
  40.             // 交换   
  41.             int temp = XuanZesort[i];   
  42.             XuanZesort[i] = XuanZesort[lowerIndex];   
  43.             XuanZesort[lowerIndex] = temp;   
  44.         }   
  45.         // 将数组返回   
  46.         return XuanZesort;   
  47.   
  48.     }  
public class ArraySort {

	public static void main(String[] args) {
		ArraySort sort = new ArraySort();

		// 排序的原始数组
		int[] arraysort = { 11, 22, 332, 223, 20, 234 };
		// 遍历出原始数据
		for (int i = 0; i < arraysort.length; i++) {
			System.out.println("原始数据" + arraysort[i]);
		}
// 选择排序排序后的数组
		int[] xuanze = sort.SortXuanZe(arraysort);
		for (int j = 0; j < xuanze.length; j++) {
			// System.out.println(xuanze[j]);
		}
      }

/**
	 * 选择排序排序数组
	 * 
	 * @param XuanZesort
	 *            传入的数组
	 * @return 返回排序后的数组
	 * 
	 *         思路:在遍历数组时先把第一个当作最小的,然后与后面的比较
	 */
	public int[] SortXuanZe(int[] XuanZesort) {

		for (int i = 0; i < XuanZesort.length; i++) {
			// 假设i是最小的数
			int lowerIndex = i;

			for (int j = i + 1; j < XuanZesort.length; j++) {
				if (XuanZesort[j] < XuanZesort[lowerIndex]) {
					// 此时j是最小的
					lowerIndex = j;
				}
			}
			// 交换
			int temp = XuanZesort[i];
			XuanZesort[i] = XuanZesort[lowerIndex];
			XuanZesort[lowerIndex] = temp;
		}
		// 将数组返回
		return XuanZesort;

	}

 

 

 

 

4. 交换排序—冒泡排序（Bubble Sort）

冒泡排序;http://baihe747.iteye.com/blog/2067294

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序的示例：

 

算法的实现：

Java代码 复制代码 收藏代码
  1. public class ArraySort {   
  2.   
  3.     public static void main(String[] args) {   
  4.         ArraySort sort = new ArraySort();   
  5.   
  6.         // 排序的原始数组   
  7.         int[] arraysort = { 11, 22, 332, 223, 20, 234 };   
  8.         // 遍历出原始数据   
  9.         for (int i = 0; i < arraysort.length; i++) {   
  10.             System.out.println("原始数据" + arraysort[i]);   
  11.         }   
  12.   
  13.         // 冒泡排序后的数   
  14.         int[] maopao = sort.SortMaoPao(arraysort);   
  15.         for (int i = 0; i < maopao.length; i++) {   
  16.             // System.out.println(maopao[i]);   
  17.         }   
  18. }   
  19.   
  20. /**  
  21.      * 冒泡排序的方法  
  22.      *   
  23.      * @param arraysort传入的原始数组  
  24.      * @return返回排序好了的数组  
  25.      *   
  26.      *                  思路:将第一个与后面的比较  
  27.      */  
  28.     public int[] SortMaoPao(int[] MaoPaosort) {   
  29.         for (int i = 0; i < MaoPaosort.length; i++) {   
  30.             for (int j = i + 1; j < MaoPaosort.length; j++) {   
  31.                 // 判断两个数的大小   
  32.                 if (MaoPaosort[i] > MaoPaosort[j]) {   
  33.                     int temp = MaoPaosort[i];   
  34.                     MaoPaosort[i] = MaoPaosort[j];   
  35.                     MaoPaosort[j] = temp;   
  36.                 }   
  37.             }   
  38.         }   
  39.   
  40.         return MaoPaosort;   
  41.     }  
public class ArraySort {

	public static void main(String[] args) {
		ArraySort sort = new ArraySort();

		// 排序的原始数组
		int[] arraysort = { 11, 22, 332, 223, 20, 234 };
		// 遍历出原始数据
		for (int i = 0; i < arraysort.length; i++) {
			System.out.println("原始数据" + arraysort[i]);
		}

		// 冒泡排序后的数
		int[] maopao = sort.SortMaoPao(arraysort);
		for (int i = 0; i < maopao.length; i++) {
			// System.out.println(maopao[i]);
		}
}

/**
	 * 冒泡排序的方法
	 * 
	 * @param arraysort传入的原始数组
	 * @return返回排序好了的数组
	 * 
	 *                  思路:将第一个与后面的比较
	 */
	public int[] SortMaoPao(int[] MaoPaosort) {
		for (int i = 0; i < MaoPaosort.length; i++) {
			for (int j = i + 1; j < MaoPaosort.length; j++) {
				// 判断两个数的大小
				if (MaoPaosort[i] > MaoPaosort[j]) {
					int temp = MaoPaosort[i];
					MaoPaosort[i] = MaoPaosort[j];
					MaoPaosort[j] = temp;
				}
			}
		}

		return MaoPaosort;
	}

 

分享到：
| java笔记链接
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    数据结构与算法(Python版)《数据结构课程设计》教学大纲.pdf

    数据结构与算法(Python版)《数据结构课程设计》教学大纲.pdf数据结构与算法(Python版)《数据结构课程设计》教学大纲.pdf数据结构与算法(Python版)《数据结构课程设计》教学大纲.pdf数据结构与算法(Python版)《数据...

    精心整理史上最全的数据结构flash演示动画，共5个版本，祝大家考研成功！

    精心整理史上最全的数据结构flash演示动画，共5个版本，祝大家考研成功！ \数据结构flash演示\版本1 \数据结构flash演示\版本2 \数据结构flash演示\版本3 \数据结构flash演示\版本4 \数据结构flash演示\版本5 ...

    数据结构1800试题.pdf

    你还在苦苦寻找数据结构的题目吗？这里刚刚上传了一份数据结构共1800道试题，轻松解决期末挂科的难题。不信？你下载看看，这里是纯题目，你下载了再来私信我答案。按数据结构教材分章节，每一章节都有选择题、或有...

    数据结构考研统考三年真题集

    数据结构考研统考三年真题集数据结构考研统考三年真题集数据结构考研统考三年真题集数据结构考研统考三年真题集数据结构考研统考三年真题集数据结构考研统考三年真题集数据结构考研统考三年真题集数据结构考研统考三...

    C++数据结构与程序设计

    C++数据结构原理与经典问题求解》是一部关于计算机科学与工程领域基础性核心课程——数据结构与算法的专著，本书《内容实用，体例新颖，结构清晰，既可以作为大、中专院校在校师生相关课程的参考书，也可以作为信息...

    数据结构与算法视频课程（59集）

    资源名称：数据结构与算法视频课程（59集）资源目录：【】mysql视频教程第41讲存储过程【】数据结构与算法_1.10算法的评价【】数据结构与算法_1.1编程的灵魂：数据结构 算法【】数据结构与算法_1.2算法的作用：猜...

    数据结构课程设计航空客运订票系统源代码+报告文档和可执行文件.zip

    数据结构课程设计航空客运订票系统源代码+报告文档和可执行文件数据结构课程设计航空客运订票系统源代码+报告文档和可执行文件数据结构课程设计航空客运订票系统源代码。数据结构课程设计航空客运订票系统源代码+...

    数据结构习题解答（C语言版）

    数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。 二、学习要点 1...

    数据结构实例（内含17个详细经典实例）

    数据结构实践教程：内含17个经典数据结构实例 根据五个不同数据结构，对每个结构都有2~4个经典实例。每个实例都有项目简介、设计思路、数据结构、完整程序、运行结果五个部分，可以直接拿来做一篇课程设计。实例名称...

    数据结构很好的数据结构很好的数据结构很好的

    是我见过的最好的数据结构是我见过的最好的数据结构是我见过的最好的数据结构是我见过的最好的数据结构是我见过的最好的数据结构是我见过的最好的数据结构是我见过的最好的数据结构是我见过的最好的数据结构是我见过...

    算法与数据结构习题答案+课件+参考资料 国防工业出版社 张永 李睿

    　本书分为基本概念、简单数据结构（线性表、栈、队列）、复杂数据结构（树、图）和算法与数据结构应用（排序、查找、算法设计基础）四部分，详细介绍了常用数据结构和算法的基本概念及其不同的实现方法，对各种数据...

    算法与数据结构（c++版）电子版

    本书是高等教育“十一五”国家级规划教材，系统介绍各种数据结构、常用算法及算法分析技术。数据结构的内容包括线性结构、树形结构、哈希结构、索引结构；算法方面的内容包括选择算法、查找算法、排序算法。本书还...

    数据结构数据结构

    数据结构数据结构数据结构

    数据结构 考试 试卷 数据结构期末复习

    数据结构 考试 试卷 数据结构期末复习

    数据结构课程设计 停车场模拟管理系统报告(含源码).docx

    数据结构课程设计 停车场模拟管理系统报告(含源码).docx数据结构课程设计 停车场模拟管理系统报告(含源码).docx数据结构课程设计 停车场模拟管理系统报告(含源码).docx数据结构课程设计 停车场模拟管理系统报告(含...

    数据结构课后答案+代码版数据结构课后答案+代码版

    数据结构课后答案+代码版数据结构课后答案+代码版数据结构课后答案+代码版数据结构课后答案+代码版数据结构课后答案+代码版数据结构课后答案+代码版数据结构课后答案+代码版数据结构课后答案+代码版数据结构课后答案...

    上海交大数据结构课件 上海交大数据结构课件

    上海交大数据结构课件 上海交大数据结构课件 上海交大数据结构课件 上海交大数据结构课件 上海交大数据结构课件 上海交大数据结构课件

    数据结构报告模板.doc

    数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新...

Magicbox
Global site tag (gtag.js) - Google Analytics