`

数据结构

算法 
阅读更多

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笔记链接
评论
发表评论

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

相关推荐

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

    数据结构是计算机科学中的核心课程之一，主要研究如何在计算机中高效地组织和存储数据，以便于进行各种操作。上海交通大学的数据结构课件是学习这一主题的重要资源，它涵盖了广泛的知识点，帮助学生深入理解数据结构...

    数据结构1800题（含详解答案）

    ### 数据结构基础知识点详解 #### 一、基础知识概念解析 **1. 算法的复杂性** - **题目**: 算法的计算量的大小称为计算的（）。 - **答案**: B. 复杂性 - **解析**: 算法的复杂性通常用来衡量算法执行效率的...

    西安理工大学863数据结构真题 -西安理工大学863数据结构真题需要的滴滴我，都是我去年备考时的真题资料，还有复试资料哦~

    西安理工大学863数据结构真题集锦 作为一名 IT 行业大师，我将根据提供的文件信息，生成相关的知识点，以下是详细的输出结果： 一、数据结构概述 数据结构是计算机科学中的一门基础学科，旨在研究如何存储和组织...

    数据结构的pdf课件

    数据结构是计算机科学中的核心课程，它探讨了如何在计算机中高效地组织和管理数据，以便于快速查找、存储和处理。这份“数据结构的pdf课件”是学习这一主题的重要资源，尤其对于初学者来说，它能提供系统性的指导和...

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

    数据结构是计算机科学中的核心概念，它涉及到如何在计算机中有效地组织、存储和处理大量数据。数据结构的设计和选择直接影响到算法的效率以及程序的性能。在这个领域，我们研究各种不同的数据组织方式，如数组、链表...

    数据结构(第4版)习题及实验参考答案-数据结构复习资料完整版(c语言版).docx

    "数据结构(第4版)习题及实验参考答案-数据结构复习资料完整版(c语言版)" 本文档是关于数据结构的习题及实验参考答案，涵盖了数据结构的基础知识、逻辑结构、物理结构、算法、时间复杂度等方面。 数据结构基础 ...

    Java常见数据结构面试题（带答案）

    "Java常见数据结构面试题（带答案）" 以下是对Java常见数据结构面试题的知识点总结： 栈和队列 * 栈和队列的共同特点是只允许在端点处插入和删除元素。 * 栈通常采用的两种存储结构是线性存储结构和链表存储结构...

    李春葆数据结构源代码

    《李春葆数据结构源代码》是一份宝贵的教育资源，它为学习数据结构提供了直观的实践素材。李春葆教授在第三版的教材中深入浅出地讲解了数据结构这一计算机科学的基础概念，而源代码正是理论知识的具体实现，是理解和...

    《初识数据结构》教学建议.pdf

    ### 数据结构的基本概念 数据结构是计算机存储、组织数据的方式。它旨在使数据的存取和处理更加高效。数据结构通常由数据对象和数据关系两部分构成。数据对象是指具有相同数据类型的元素的集合；数据关系则定义了...

    数据结构和算法分析 C++版 第三版

    "数据结构和算法分析 C++版 第三版" 本资源是《数据结构和算法分析 C++版 第三版》的摘要信息，作者是Clifford A. Shaffer，来自 Virginia Tech 的计算机科学系。该书将数据结构和算法分析的基本概念和技术进行了...

    北京邮电大学809数据结构复习指南

    【北京邮电大学809数据结构复习指南】是一份由成功上岸北邮AI院的学长编写的详尽复习资料，旨在帮助备考北邮研究生考试的学生，特别是那些选择809数据结构作为专业课的考生。复习指南依据北邮研究生招生网的考试大纲...

    考研王道数据结构代码.zip

    数据结构是计算机科学中的核心课程，它探讨了如何在计算机中高效地组织和管理数据。在准备考研的道路上，深入理解和掌握数据结构至关重要，因为它是算法设计和分析的基础。"考研王道数据结构代码.zip"这个压缩包包含...

    数据结构试题库及答案.docx

    数据结构试题库及答案.docx 本资源摘要信息将围绕数据结构试题库及答案的相关知识点进行详细解释。 数据结构概论 数据结构是研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的关系和运算等的学科。...

    严蔚敏数据结构题集(C语言版)完整答案.doc

    数据结构题集（C语言版）完整答案 本资源提供了数据结构题集的完整答案，涵盖了数据结构的基本概念、抽象数据类型、存储结构、数据类型等方面的知识点。下面是对资源中提到的知识点的详细解释： 1. 数据结构的基本...

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

    数据结构是计算机科学中至关重要的基础概念，它研究的是非数值计算问题中计算机的数据组织方式、它们之间的关系以及相应的操作。本章主要介绍了数据结构的基本概念、抽象数据类型（ADT）的定义与实现，以及如何用类...

    2020 天勤数据结构 高分笔记 + 习题

    数据结构是计算机科学中的核心课程，对于准备考研的学子来说，掌握好数据结构至关重要。这份“2020 天勤数据结构 高分笔记 + 习题”资源包含了两个关键部分，即高分笔记和习题集，旨在帮助考生深入理解和应用数据...

    数据结构 朱战力 习题解答 数据结构 朱战力 习题解答

    数据结构是计算机科学中的核心课程之一，主要研究如何在计算机中高效地组织和管理数据，以便进行快速查找、插入和删除等操作。朱战力教授的《数据结构》习题解答是一个宝贵的资源，帮助学生深入理解和掌握这门学科的...

    数据结构（严蔚敏版）

    数据结构是计算机科学与技术领域中的核心课程之一，它研究如何在计算机中组织和存储数据，以便高效地访问和修改。严蔚敏教授编著的《数据结构》是一本广泛被采用的经典教材，深受广大计算机专业学生和研究人员的青睐...

    西北民族大学--数据结构考试卷答案.pdf

    "西北民族大学--数据结构考试卷答案.pdf" 以下是根据提供的文件信息生成的相关知识点： 数据结构定义 数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。 数据结构分类 数据结构可以分为...

    数据结构 C语言描述 耿国华 高等教育出版社 课后习题答案

    数据结构是计算机科学的基础课程，它探讨如何有效地组织和管理数据，以便进行高效的数据操作。在C语言描述下，耿国华的《数据结构》教材是深入理解这一主题的重要资源，而课后习题答案则提供了检验学习效果的途径。 ...

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