`

数据结构

算法 
阅读更多

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

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

相关推荐

    PTA-数据结构与算法题目集.zip

    PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 PTA-数据结构与算法题目集 ...

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

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

    数据结构1800试题.pdf

    数据结构是计算机科学中的核心课程，它探讨如何高效地组织和管理数据，以便进行快速查找、插入和删除等操作。这份“数据结构1800试题”提供了丰富的练习题目，涵盖了数据结构的主要概念和算法，适合学生进行复习和...

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

    数据结构1800题（含答案）数据结构1800题（含答案）数据结构1800题（含答案）数据结构1800题（含答案）数据结构1800题（含答案）数据结构1800题（含答案）数据结构1800题（含答案）数据结构1800题（含答案）数据结构...

    JS数据结构与算法.pdf

    JS 数据结构与算法.pdf 本书主要介绍了 JavaScript 语言的基础知识，包括数据结构和算法。以下是该书的详细知识点： 一、JavaScript 基础知识 * 变量和数据类型 * 运算符和控制结构 * 函数和对象 * 数组和字符串 ...

    严蔚敏数据结构动态演示

    数据结构是计算机科学中的核心概念，它涉及到如何在内存中有效地组织和管理数据，以便进行高效的操作。严蔚敏教授的《数据结构》是一本经典的教材，深入浅出地介绍了各种数据结构及其算法。"严蔚敏数据结构动态演示...

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

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

    苏大872计算机-苏州大学《数据结构》20卷试真题库+答案.rar

    苏州大学《数据结构》20卷试真题库是一本涵盖数据结构基础知识、经典算法、应用实践等方面的试题集合，适用于计算机科学、计算机工程、软件工程等专业的学生以及从事计算机算法开发的程序员。本书以数据结构和算法为...

    王道数据结构.zip

    《王道数据结构》是针对计算机科学与技术专业考研学子的重要参考资料，主要涵盖了数据结构的基础理论、算法设计以及分析等内容。这份压缩包包含了2019年和2020年的版本，无水印，适合考生们进行系统的学习和复习。 ...

    王道考研——数据结构PPT.zip

    数据结构是计算机科学中的核心课程之一，主要研究如何在计算机中组织、存储和管理数据，以便高效地进行各种操作。王道考研的数据结构PPT涵盖了这门学科的关键概念和技术，对于准备考研的学生来说，是一份非常有价值...

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

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

    数据结构与算法分析--C语言描述_数据结构与算法_

    数据结构与算法是计算机科学的基础，对于理解和设计高效的软件至关重要。C语言因其高效、底层特性，常被用于实现数据结构和算法，使得程序更接近硬件，性能更优。本资源"数据结构与算法分析--C语言描述"是针对数据...

    对于数据结构的定义和讲解

    数据结构是计算机科学中的核心概念，它关注的是数据的逻辑结构、物理结构以及它们之间的相互关系。数据结构不仅仅是关于数据的简单存储，更在于如何有效地组织、管理和处理数据，以优化程序的效率和性能。 首先，...

    数据结构教程 by 李春葆

    数据结构是计算机科学中的核心课程，它探讨了如何在计算机中高效地组织和管理数据，以便于进行快速的存取和处理。李春葆教授的数据结构教程是一本广泛使用的教材，它深入浅出地介绍了这一领域的基本概念和算法。在这...

    数据结构（唐发根）

    数据结构是计算机科学中的核心课程之一，主要研究如何在计算机中高效地组织和存储数据，以便于进行各种操作。唐发根教授的数据结构教程是一部深受初学者欢迎的教材，它全面且深入地介绍了数据结构的基本概念、算法和...

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

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

    数据结构经典算法总结

    数据结构是计算机科学中至关重要的基础概念，它研究如何有效地组织和存储数据，以便于高效地访问和操作。本文将对数据结构的经典算法进行详细解析，帮助理解和掌握这些核心概念。 首先，我们要明确数据和数据元素的...

    数据结构高分笔记part1

    数据结构是计算机科学中的核心课程，对于理解和设计高效的算法至关重要，尤其在计算机软件开发、数据库管理、算法分析等领域。这份“数据结构高分笔记part1”显然是为了帮助备考研究生入学考试的专业学生准备的，...

    北航--数据结构课件

    数据结构是计算机科学中的核心课程，它探讨了如何在计算机中有效地存储和组织数据，以便进行高效的检索、插入和删除等操作。北京航空航天大学（北航）的数据结构课程以其严谨性和实用性著称，该课程的课件对于学习者...

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

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

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