`
suhuanzheng7784877
  • 浏览: 702320 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
Ff8d036b-05a9-33b5-828a-2633bb68b7e6
读金庸故事,品程序人生
浏览量:47699
社区版块
存档分类
最新评论

Java基础复习笔记11基本排序算法

阅读更多

1.       排序

排序是一个历来都是很多算法家热衷的领域,到现在还有很多数学家兼计算机专家还在研究。而排序是计算机程序开发中常用的一种操作。为何需要排序呢。我们在所有的系统中几乎都要检索数据,而这些欲检索的数据如果有规律的话,比如按照某些字段、属性降序排序的话,那么从这些有规律的数据查询结果或者结果集的话就快速得多。

2.       常用算法

常用的算法有:直接选择排序、堆排序、冒泡排序、快速交换排序、直接插入排序、折半插入排序、Shell排序、归并排序、桶式排序、基数排序。这些都属于常用排序算法,也都是内部排序算法。所谓内部排序就是不借助任何外部的内存处理器,直接使用内存,在内存中完成就可以的排序方式。

3.       直接选择排序

直接排序的思想就是进行二重遍历,由外层元素依次和内层元素进行对比,之后交换位置。算法如下

package sort;

import java.util.Arrays;

/**
 * 选择排序
 * 
 * @author liuyan
 */
public class SelectSort {

	// 选择排序法
	public static void selectSort(Integer[] integers) {
		for (int i = 0; i < integers.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < integers.length; j++) {
				if (integers[i] < integers[j]
						&& integers[minIndex] < integers[j]) {

					// 只记住标记
					minIndex = j;
				}
			}

			// 每次只交换一次即可
			if (minIndex != i) {
				Integer temp = integers[i];
				integers[i] = integers[minIndex];
				integers[minIndex] = temp;
			}
		}
	}
}
 4.       堆排序

堆排序的思想就是将要排序的数组看成一个完全二叉树(出最后一层节点外,其他节点都是2个子节点),之后建立大顶堆,将完全二叉树建立成一个父节点值都大于它的子节点的树。之后将根节点和要排序的数组的最后一个元素进行换位。之后除了数组最后一个元素外重复建堆过程。算法如下

package sort;

import java.util.Arrays;

/**
 * 堆排序
 * 
 * @author liuyan
 */
public class HeapSort {

	/**
	 * 构建堆数组
	 * 
	 * @param datas
	 * @param lastIndex
	 */
	public static void buildHeap(Integer[] datas, int lastIndex) {
		
		//从目标的父节点开始遍历
		for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
			
			//记录父节点位置
			int maxIndex = i;
			
			//当父节点的子节点存在的时候
			while (maxIndex * 2 + 1 <= lastIndex) {
				
				//默认附一个大值为父节点的左子节点的索引
				int biggerIndex = maxIndex * 2 + 1;
				
				//此处判断是否父节点还有一个右子节点
				if (biggerIndex < lastIndex) {
					
					//如果有右子节点判断左右子节点的值大小,记录一个最大的位置,好用于交换
					if (datas[biggerIndex] < datas[biggerIndex + 1]) {
						biggerIndex++;
					}

				}
				
				//此处是比较父节点值和左右子节点值,找个最大的做父亲
				if (datas[maxIndex] < datas[biggerIndex]) {
					Integer temp = datas[maxIndex];
					datas[maxIndex] = datas[biggerIndex];
					datas[biggerIndex] = temp;
					
					//记录一下最大值的索引
					maxIndex = biggerIndex;
				} else {
					break;
				}

			}

		}

	}

	/**
	 * 堆排序
	 * 
	 * @param datas
	 */
	public static void heapSort(Integer[] datas) {

		// 数组大小
		int arrayLength = datas.length;

		// 遍历数组
		for (int i = 0; i < arrayLength - 1; i++) {

			// 构建堆
			buildHeap(datas, arrayLength - 1 - i);

			// 交换元素
			Integer temp = datas[0];
			datas[0] = datas[arrayLength - 1 - i];
			datas[arrayLength - 1 - i] = temp;
		}

	}

 5.       冒泡排序

冒泡排序在使用频率上来说,也许是仅次于直接选择排序的算法的了。因为起泡的思想也很简单就是循环数组中的元素,相邻元素一一对比,进行交换。算法如下

package sort;

import java.util.Arrays;

/**
 * 冒泡排序法
 * 
 * @author liuyan
 */
public class BubbleSort {

	/**
	 * 冒泡排序
	 * 
	 * @param datas
	 */
	public static void bubbleSort(Integer[] datas) {
		int datasLength = datas.length;
		for (int i = 0; i < datasLength - 1; i++) {
			for (int j = 0; j < datasLength - 1 - i; j++) {
				if (datas[j] < datas[j + 1]) {

					// 交换之
					Integer temp = datas[j + 1];
					datas[j + 1] = datas[j];
					datas[j] = temp;
				}
			}
		}

	}

}

 6.       快速排序

所谓快速排序法是从待排序的数组中找一个标本作为分界值(一般是数组的第一个元素),所有比这个值小的值放到它的左边(或者右边),将比它大的值放到它的右边(或者左边),这样这个分界值左右两边的值要么全部比它大,要么全部比它小。之后再利用递归,将此标本右边、左边的所有元素也按部就班。算法如下

package sort;

import java.util.Arrays;

/**
 * 快速排序
 * 
 * @author liuyan
 */
public class QuickSort {

	/**
	 * 交换数组元素位置
	 * 
	 * @param datas
	 * @param i
	 * @param j
	 */
	public static void chang(Integer[] datas, int i, int j) {
		Integer temp = datas[i];
		datas[i] = datas[j];
		datas[j] = temp;

	}

	/**
	 * 快速排序法
	 * 
	 * @param datas
	 * @param startIndex
	 * @param endIndex
	 */
	public static void quickSort(Integer[] datas, int startIndex, int endIndex) {

		if (startIndex < endIndex) {
			
			//标本
			Integer startData = datas[startIndex];
			
			//左边的开始索引
			int i = startIndex;
			
			//右边的开始索引
			int j = endIndex + 1;
			while (true) {
				
				//找左边比标本大的下标
				while (i < endIndex && datas[++i] > startData){
				}
				
				//找右边比标本小的下标
				while (j > startIndex && datas[--j] < startData){
				}
					
				if (i < j) {
					
					//交换i、j元素位置
					chang(datas, i, j);
				} else {
					break;
				}
			}
			
			//交换开始位置、j的元素为止
			chang(datas, startIndex, j);
			
			//递归标本左边
			quickSort(datas, startIndex, j - 1);
			
			//递归标本右边
			quickSort(datas, j + 1, endIndex);
		}

	}
}

 7.       直接插入排序

直接插入排序的原理就是将数组中的元素依次和前面元素进行比较,如果发现了比它大的(或者小的),记录标志位、记录被比较元素,之后从标志位一位一位的向后进行元素移动,之后空出来的的那一位就是留给被比较元素的。这样造成了一个现象就是被比较的元素前面的所有元素都是排序过了的。算法如下。

package sort;

import java.util.Arrays;

/**
 * 直接插入排序
 * 
 * @author liuyan
 */
public class InsertSort {

	/**
	 * 直接插入
	 * 
	 * @param datas
	 */
	public static void insertSort(Integer[] datas) {
		
		//从数组第二个元素开始遍历
		for (int i = 1; i < datas.length; i++) {
			
			//当前元素和前一个元素进行对比【此处前面的元素已经排序好了】
			if (datas[i] < datas[i - 1]) {
				
				//记录当前要比较的元素值
				Integer temp = datas[i];
				
				//从当前元素往前开始比较
				int j = i - 1;
				
				//如果满足前面索引有效并且前面的元素值都是比当前值大的,那就进行元素后移动操作
				for (; j >= 0 && datas[j] > temp; j--) {
					
					//元素后移
					datas[j + 1] = datas[j];

				}
				
				//前移操作后,j的索引就是中间那个比前面元素大,比后面元素小的位置索引-1
				
				//将其要对比的值插进去
				datas[j + 1] = temp;
			}

		}
	}
}

 8.       折半插入排序

折半插入排序是在原直接插入的基础上作了改进。对于折半插入法,被比较的元素不用和前面所有的元素进行一一对比,而是先找到0位元素到此被比较元素的中点元素,和这个重点元素进行比较,看看谁大,之后就是被比较元素元素和这个中点元素之间再找一个中点进行比较,或者是0点和原中点元素找个新中点。这样就可以缩小范围,反正排在被比较元素之前的元素是一个已经排好大小的序列,那就可以善加利用这已经排好的序列。当然了,找到位置后,该移动元素的还是要移动的。算法如下:

package sort;

import java.util.Arrays;

/**
 * 折半排序
 * 
 * @author liuyan
 */
public class BinaryInsertSort {

	/**
	 * 折半排序
	 * 
	 * @param datas
	 */
	public static void binaryInsertSort(Integer[] datas) {

		// 从数组第二个元素开始遍历
		for (int i = 1; i < datas.length; i++) {

			// 记录当前要比较的元素值
			Integer temp = datas[i];

			// 低位开始
			int low = 0;

			// 高位开始
			int hight = i - 1;

			// 位置有效,低位、高位
			while (low <= hight) {

				// 中间位置
				int mind = (low + hight) / 2;
				
				//被比较元素大于中间元素
				if (temp > datas[mind]) {
					
					//低位调整在中点之后
					low = mind + 1;
				} else {//被比较元素小于中间元素
					
					//高位在中点之前
					hight = mind - 1;
				}
			}
			// 低高位调整完毕后,将中点元素依次往后移动
			for (int j = i; j > low; j--) {

				// 元素后移
				datas[j] = datas[j - 1];

			}

			// 前移操作后,low的索引就是中间那个比前面元素大,比后面元素小的位置索引low
			// 将其要对比的值插进去
			datas[low] = temp;
		}
	}
}

 9.       归并排序

归并排序的主要思想就是将原来的数组分开成2大部分,建立一个新的临时数组,分别从2部分开始顺序走,将2部分的元素进行比较,先将小元素放入到临时数组,之后索引往前走一位,剩下的在进行比较。算法如下:

 

 

 

 

 

package sort;

import java.util.Arrays;

/**
 * 归并排序
 * 
 * @author liuyan
 */
public class MergeSort {

	/**
	 * 归并排序
	 * 
	 * @param datas
	 * @param start
	 * @param datasLength
	 */
	public static void mergeSort(Integer[] datas, int leftIndex, int rightIndex) {
		
		//当分块索引有效时
		if (leftIndex < rightIndex) {
			
			//找出中间索引
			int center = (leftIndex + rightIndex) / 2;
			
			//把左边到中点的元素集合继续分堆儿
			mergeSort(datas, leftIndex, center);
			
			//把右边到中点的元素集合继续分堆儿
			mergeSort(datas, center + 1, rightIndex);
			
			//归并
			merge(datas, leftIndex, center, rightIndex);
		}

	}

	/**
	 * 归并
	 * 
	 * @param datas
	 * @param left
	 * @param center
	 * @param right
	 */
	private static void merge(Integer[] datas, int left, int center, int right) {
		
		//建立一个临时的数组,用于装载排序后的数组
		Integer[] temp = new Integer[datas.length];
		
		//第二队的开始索引位置
		int mind = center + 1;
		
		//临时数组从第一队的索引开始
		int third = left;
		
		//仅仅记录开始索引位置
		int tmp = left;
		while (left <= center && mind <= right) {//分队后的数组进行比较
			if (datas[left] <= datas[mind]) {
				
				//左边的略小,左边索引前进
				temp[third++] = datas[left++];
			} else {
				
				//右边的略小,右边索引前进
				temp[third++] = datas[mind++];
			}

		}
		
		//如果第二队数组还没走完,继续走完,将第二队右边的元素都放到临时数组后面
		while (mind <= right) {
			temp[third++] = datas[mind++];
		}
		
		//如果第一队数组还没走完,继续走完,将第一队右边的元素都放到临时数组后面
		while (left <= center) {
			temp[third++] = datas[left++];
		}
		
		//将临时数组中的所有元素(排序好的),原样覆盖到原先的数组
		while (tmp <= right) {
			datas[tmp] = temp[tmp++];
		}
	}
}

 总结到这里发现自己实在不行了。要吐了,算法真的是数学大师+计算机专业的人才能搞得了得。相当于大脑就是一个编译器+数学公式器+内存监视器。向所有世界上还在为算法而奋斗的人们致敬,先总结到这里。

分享到:
评论

相关推荐

    Java基础复习笔记10数据结构-排序二叉树

    【Java基础复习笔记10数据结构-排序二叉树】 排序二叉树是一种特殊类型的二叉树,其每个节点的数据值满足以下特性:对于任意节点,其左子树中的所有节点值都小于该节点,而右子树中的所有节点值都大于或等于该节点...

    JavaSE基础复习笔记

    Java中提供了多种排序算法,如冒泡排序、选择排序、插入排序、快速排序等。了解这些算法的基本原理及其实现方式对于提高数据处理效率至关重要。 综上所述,Java的基础复习不仅仅是对语言特性的简单回顾,更重要的是...

    Java基础复习笔记09数据结构-哈夫曼树

    ### Java基础复习笔记09数据结构-哈夫曼树 #### 1. 哈夫曼树概述 哈夫曼树是一种特殊的二叉树,它在计算机科学领域有着广泛的应用,尤其是在数据压缩方面。哈夫曼树也被称为最优二叉树,其构建原则是使得带权路径...

    Java基础复习笔记04数据结构-线性表

    ### Java基础复习笔记04数据结构-线性表:深入解析与应用 #### 线性表的概念 线性表是计算机科学中最基础的数据结构之一,它由一系列相同类型的元素组成,这些元素按照一定的顺序排列,形成一个有序的序列。在逻辑...

    Java基础复习笔记07数据结构-树的概述

    本篇复习笔记主要关注树的概述,包括树的概念、基本操作、使用场景以及一种特殊的树实现——记父节点实现。 1. **树的概念** 树是一种由N个节点构成的有限集合,这些节点之间存在父子关系。与线性结构(如数组、...

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

    内容概要:这是本人在复习数据结构排序算法所写的markdown文档,对各个算法进行了比较,分析其稳定性。通过对六种排序算法的介绍,了解其中的核心原理,手写源码过程中对其代码进行注释讲解。 适用人群:本人文档是...

    java面试,基础学习笔记

    这份"java面试,基础学习笔记"包含了针对面试者复习和初学者学习的关键知识点,旨在帮助你深入理解和掌握Java的核心概念。 在"core_java"部分的学习笔记中,你将深入探讨Java的基础语法和核心特性。这包括但不限于:...

    java各种笔记.zip

    "java各种笔记.zip"这个压缩包文件很可能包含了关于Java学习的各种资料,如笔记、教程、代码示例等,旨在帮助学习者深入理解Java编程。下面我们将详细探讨Java的一些核心知识点。 1. **Java基础**: - **语法**:...

    Java《剑指Offer》刷题笔记.zip

    1. **基础数据结构与算法**:Java中常见的数据结构如数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)以及图等是面试的基础。算法方面,排序(快速排序、归并排序、堆排序等)、查找(二分查找、哈希查找)...

    软考中级软件设计师专题复习笔记

    3. **算法**:学习并掌握排序、查找、图论等常见算法,能够分析算法的时间复杂度和空间复杂度,以优化代码效率。 4. **操作系统**:理解操作系统的原理,包括进程管理、内存管理、文件系统和设备管理等。这包括了解...

    北航计算机专业课 代码及期末复习笔记.zip

    北航计算机专业的学习资源是众多学子关注的焦点,这个名为"北航计算机专业课 代码及期末复习笔记.zip"的压缩包文件包含了丰富的学习材料,旨在帮助学生更好地理解和掌握计算机科学的关键知识。其中,源码文件是编程...

    软件工程师软考复习笔记资料

    同时,对数据结构和算法的理解也是必不可少的,如排序算法、查找算法等,这些都直接影响到程序的效率。 5. **数据库管理**:数据库是软件系统中存储数据的核心,考生需要了解关系型数据库的基本原理,如SQL语言的...

    java学习笔记之大鹏JAVA终级总结

    - 数据结构与算法:排序算法、查找算法、链表操作、树结构等常见问题。 - 高并发与高可用:分布式锁、分布式ID生成、CAP定理、BASE理论等。 - Spring框架:IoC、AOP原理,以及Spring Boot、Spring Cloud的相关...

    计算机专业期末考试复习笔记.zip

    【标题】"计算机专业期末考试复习笔记.zip"的文件是一个包含计算机专业知识的压缩包,用于帮助学生准备期末考试。从这个标题我们可以推断,这个压缩包内可能包含了多个文档或讲义,涵盖了计算机科学与技术的主要课程...

    基础复习资料.zip

    6. **算法与数据结构**:基础的排序算法(冒泡、选择、插入等)、查找算法、栈、队列、树和图等。 7. **软件工程**:软件开发过程、版本控制、测试方法、需求分析等。 8. **计算机科学理论**:如计算模型、复杂度...

    Java数据结构与算法15天笔记.zip

    通过阅读这些笔记,你可以系统地学习Java中的数据结构和算法,掌握它们的基本概念、操作和应用场景,为提升编程技能和解决复杂问题打下坚实基础。记得结合博客文章深入学习,理论与实践相结合,才能更好地理解和运用...

Global site tag (gtag.js) - Google Analytics