排序算法整理:冒泡排序、堆排序、插入排序、归并操作、快速排序、希尔排序、选择排序_w18478272407的博客-程序员宅基地


SortUtils.java


package prms.utils.sort;

import java.util.Arrays;

/**
 * @ClassName:     SortUtils
 * @Description:  <p> 排序算法 工具类 </p>
 * @author         edgar
 * @email 		   【[email protected]】
 * @version        V 1.0  
 * @date           2017-3-28 15:35:12
 */
public class SortUtils {
	
	/**
	 * @Title:        SortUtils
	 * @Description:    私有化构造 :类不能实例化
	 */
	private SortUtils(){}
	
	public static void main(String[] args) {
		int[] arr = { 2, 5, 3, 1, 4 };
		System.out.println("排序前:" + Arrays.toString(arr));
		
		 bubbleSort(arr);
		 heapSort(arr);
		insertSort(arr);
		mergeSort(arr);
		quickSort(arr);
		selectionSort(arr);
		shellSort(arr);
		System.out.println("排序后:" + Arrays.toString(arr));
	}
	
	
	/**
	 * @Title: bubbleSort
	 * @Description: 冒泡排序
	 *              依次比较相邻的两个数,将小数放在前面,大数放在后面。
	 *              即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。
	 *              然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,
	 *              直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,
	 *              将最大的数放到了最后。在第二趟:仍从第一对数开始比较
	 *              (因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),
	 *              将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),
	 *              第二趟结束,在倒数第二的位置上得到一个新的最大数
	 *              (其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。 
	 * @param data   
	 * @return void 
	 */
	public static void bubbleSort(int[] data){
		for (int i = 0; i < data.length - 1; i++) {
			for (int j = 0; j < data.length - 1 - i; j++) {
				if (data[j] > data[j + 1]) {
					swap(data, j, j + 1);
				}
			}
		}
	}
	
	/**
	 * @Title: heapSort
	 * @Description: 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征, 使得在当前无序区中选取最大(或最小)关键字的记录变得简单。  
	 *         (1)用大根堆排序的基本思想    
	 *         	① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区    
	 *         	②再将关键字最大的记录R[1](即堆顶)和无序区的最后一个 记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],
	 *         且满足R[1..n-1].keys≤R[n].key    ③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。
	 *         然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,
	 *         由此得到新的无序区R[1..n-2]和有序区R[n-1..n],
	 *         且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。   直到无序区只有一个元素为止。   
	 *         (2)大根堆排序算法的基本操作:   
	 *          ① 初始化操作:将R[1..n]构造为初始堆;    
	 *          ②每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换, 然后将新的无序区调整为堆(亦称重建堆)。
	 *          
	 * @param data   
	 * @return void 
	 */
	public static void heapSort(int[] data) {
		MaxHeap h = new MaxHeap();
		h.init(data);
		for (int i = 0; i < data.length; i++)
			h.remove();
		System.arraycopy(h.queue, 1, data, 0, data.length);
	}

	private static class MaxHeap {
		private int size = 0;
		private int[] queue;
		
		void init(int[] data) {
			this.queue = new int[data.length + 1];
			for (int i = 0; i < data.length; i++) {
				queue[++size] = data[i];
				fixUp(size);
			}
		}
		
		@SuppressWarnings("unused")
		public int get() {
			return queue[1];
		}
		public void remove() {
			swap(queue, 1, size--);
			fixDown(1);
		}
		// fixdown
		private void fixDown(int k) {
			int j;
			while ((j = k << 1) <= size) {
				if (j < size && queue[j] < queue[j + 1])
					j++;
				if (queue[k] > queue[j]) // 不用交换

					break;
				swap(queue, j, k);
				k = j;
			}
		}
		private void fixUp(int k) {
			while (k > 1) {
				int j = k >> 1;
				if (queue[j] > queue[k])
					break;
				swap(queue, j, k);

				k = j;
			}
		}

	}
	
	/**
	 * @Title: insertSort
	 * @Description: 插入排序基本思想
	 *             将n个元素的数列分为已有序和无序两个部分,如插入排序过程示例下所示:   
	 *             {
   {a1},{a2,a3,a4,…,an}}   
	 *             {
   {a1⑴,a2⑴},{a3⑴,a4⑴ …,an⑴}}  
	 *             {
   {a1(n-1),a2(n-1) ,…},{an(n-1)}}   
	 *             每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,
	 *             找出插入位置,将该元素插入到有序数列的合适位置中。
	 * @param data   
	 * @return void 
	 */
	public static void insertSort(int[] data) {
		for (int i = 1; i < data.length; i++) {
			for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
				swap(data, j, j - 1);
			}
		}

	}
	
	/**
	 * @Title: mergeSort
	 * @Description: 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。 
	 *             如设有数列{6,202,100,301,38,8,1}   
	 *             初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数   
	 *             i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3   
	 *             i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4   
	 *             i=3 [ 1 6 8 38 100 202 301 ] 4 
	 * @param data   
	 * @return void 
	 */
	public static void mergeSort(int[] data) {
		int[] temp = new int[data.length];
		mergeSort(data, temp, 0, data.length - 1);
	}
	private static void mergeSort(int[] data, int[] temp, int l, int r) {
		int mid = (l + r) / 2;
		if (l == r){
			return;
		}
		
		mergeSort(data, temp, l, mid);
		mergeSort(data, temp, mid + 1, r);

		for (int i = l; i <= r; i++) {
			temp[i] = data[i];
		}
		int i1 = l;
		int i2 = mid + 1;
		for (int cur = l; cur <= r; cur++) {
			if (i1 == mid + 1){
				data[cur] = temp[i2++];
			}else if (i2 > r){
				data[cur] = temp[i1++];
			}else if (temp[i1] < temp[i2]){
				data[cur] = temp[i1++];
			}else{
				data[cur] = temp[i2++];
			}
		}
	}

	/**
	 * @Title: quickSort
	 * @Description:快速排序
	 *             一趟快速排序的算法是:   
	 *             1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;  
	 *             2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];   
	 *             3)从j开始向前搜索,即由后开始向前搜索(j=j-1即j--),找到第一个小于key的值A[j],A[i]与A[j]交换;   
	 *             4)从i开始向后搜索,即由前开始向后搜索(i=i+1即i++),找到第一个大于key的A[i],A[i]与A[j]交换;   
	 *             5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。
	 *             找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。) 
	 * @param data   
	 * @return void 
	 */
	public static void quickSort(int[] data) {
		quickSort(data, 0, data.length - 1);
	}
	private static void quickSort(int[] data, int i, int j) {
		int pivotIndex = (i + j) / 2;
		// swap
		swap(data, pivotIndex, j);
		
		int k = partition(data, i - 1, j, data[j]);
		swap(data, k, j);
		if ((k - i) > 1){
			quickSort(data, i, k - 1);
		}
		if ((j - k) > 1){
			quickSort(data, k + 1, j);
		}
	}

	/**
	 * @param data
	 * @param i
	 * @param j
	 * @return
	 */
	private static int partition(int[] data, int l, int r, int pivot) {
		do {
			while (data[++l] < pivot);
			while ((r != 0) && data[--r] > pivot);
			swap(data, l, r);
		} while (l < r);
		swap(data, l, r);
		return l;
	}

	/**
	 * @Title: shellSort
	 * @Description: 希尔排序:
	 * 		 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成(n除以d1)个组。所有距离为d1的倍数的记录放在同一个组中。
	 * 		先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),
	 * 		即所有记录放在同一组中进行直接插入排序为止。 
	 * 
	 * 
	 *      属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序    
	 *      排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,
	 *      组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1, 即所有记录放进一个组中排序为止    
	 *      初始:d=5   49 38 65 97 76 13 27 49 55 04    
	 *      49 13   |-------------------|    
	 *      38 27     |-------------------|    
	 *      65 49   |-------------------|    
	 *      97 55     |-------------------|    
	 *      76 04   |-------------------|    
	 *      一趟结果   13 27 49 55 04 49 38 65 97 76    
	 *      d=3    13 27 49  55 04 49 38 65 97 76    
	 *      13 55 38 76 |------------|------------|------------|    
	 *      27 04 65 |------------|------------|    
	 *      49 49 97 |------------|------------|   
	 *      二趟结果  13 04 49* 38 27 49 55 65 97 76    
	 *      d=1   13 04 49 38 27 49 55 65 97 76
	 *         |----|----|----|----|----|----|----|----|----|    三趟结果   
	 *      04 13 27 38 49 49 55 65 76 97
	 * @param data   
	 * @return void 
	 */
	public static void shellSort(int[] data) {
		for (int i = data.length / 2; i > 2; i /= 2) {
			for (int j = 0; j < i; j++) {
				insertSort(data, j, i);
			}
		}
		insertSort(data, 0, 1);
	}

	/**
	 * @param data
	 * @param j
	 * @param i
	 */
	private static void insertSort(int[] data, int start, int inc) {
		for (int i = start + inc; i < data.length; i += inc) {
			for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
				swap(data, j, j - inc);
			}
		}
	}
	
	/**
	 * @Title: selectionSort
	 * @Description: 选择排序基本思路:
	 *              把第一个元素依次和后面的所有元素进行比较。第一次结束后,就会有最小值出现在最前面。依次类推
	 * @param data   
	 * @return void 
	 */
	public static void selectionSort(int[] data) {
		for (int x = 0; x < data.length - 1; x++) {
			for (int y = x + 1; y < data.length; y++) {
				if (data[y] < data[x]) {
					swap(data, x, y);
				}
			}
		}
	}
	
	/**
	 * @Title: swap
	 * @Description: 交换数组中的两个元素
	 * @param data
	 * @param i
	 * @param j   
	 * @return void 
	 */
	public static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}
	
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/w18478272407/article/details/85802386

智能推荐

安卓指纹启动流程_内核工匠的博客-程序员宅基地

本文主要基于Android10.0系统开源代码介绍指纹识别模块的整体架构和启动流程。一.指纹识别整体框架结合上图,Android系统的指纹识别软件上主要分成4层:应用层:应用开发者调用AO...

创建计划任务用bat批处理定时备份sqlserver数据库_天上下雨的博客-程序员宅基地

选择创建计划任务备份数据库其实是自己给自己挖了一个坑,在安装SQLSERVER数据库的时候没有注意版本,安装的是express版本,而这个版本是没有【SQLSERVER代理】功能的。就没有办法在SQLSERVER上直接创建备份作业来定时备份数据库。必须得重新安装数据库,但是服务器已经全部配置好了,客户已经在正常使用了,怕重新安装数据库出问题,所以就想着用其他的办法来对数据库进行备份。在这里建议安装...

安装redis-dump命令_fct2001140269的博客-程序员宅基地_redis-dump命令

安装redis-dump命令1.安装redis-dump执行的shell脚本如下:#!/bin/bash#首先到tmp下,用来存放下载的安装文件cd /tmpmkdir rvmcd rvm# 开始安装RVMgpg --keyserver hkp://keys.gnupg.net --recv-keys 409B6B1796C275462A1703113804BB82D39DC0...

css 绝对定位元素挡住下方元素点击解决办法_fanyanjiang的博客-程序员宅基地_css绝对定位被遮挡

pointer-events:none; 表示它将捕获不到任何点击,而只是让事件穿透到它的下面。pointer-events:auto; 表示鼠标不会穿透当前层, 鼠标事件仍会监听这个父元素下面的子元素。外层div如果已经绝对或相对定位了(并且本层有点击事件或其他执行事件继续有效,这两步执行后,外层的父元素上的事件会正常执行,同时下层元素也可点击): position: absolute; z-index:9999 pointer-events: none;内层div设置绝对定位:

下血本买的!6年菜鸟开发面试字节跳动安卓研发岗,详细的Android学习指南_普通网友的博客-程序员宅基地

" 对于程序员来说,如果哪一天开始他停止了学习,那么他的职业生涯便开始宣告消亡。”高薪的IT行业是众多年轻人的职业梦想,然而,一旦身入其中却发觉没有想像中那么美好。被称为IT蓝领的编程员,工作强度大,像个编码“机器”;技术更新换代快,饭碗不稳定。随着年龄的增长,尤其是工作2-5年的Android程序员该何去何从?就得看自己的眼光、胆识和机遇了!现在的终端开发已经开始进入稳定期,在这个阶段大厂压力很大小厂更会收到挤压,人们使用的App越来越固定,即使是大厂,几年前平台级应用发个Push就能引流几十万,.

ibmMQ-第五章_fanyuanwaifdl的博客-程序员宅基地

第五章WebSphere MQ 控制命令目标11. 了解WebSphere MQ控制命令12. 熟悉WebSphere MQ控制命令集5.1 如何使用控制命令 如果需要使用控制命令,则用户必须属于mqm组。控制命令在不同平台上的使用会有些注意事项,如下所示:WebSphere MQ Windows 版 所有控制命令都可以从命令行发出。使用 WebSphere MQ

随便推点

使用RecyclerView实现的Banner,Android中广告轮播_林凯986的博客-程序员宅基地_android recyclerview 实现banner

废话不多说先上效果图布局文件<?xml version="1.0" encoding="utf-8"?><LinearLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:app="http://schemas.android.com/apk/res-auto" android:layout_width="match_parent" android:layout_heig

怎么读Man Page和BNF_「已注销」的博客-程序员宅基地_man page怎么读

之前其实嫌弃麻烦,感觉在学习过程中要花很多时间在读man page上。基本是直接搜索问题找答案,但不知道怎么解决,下次遇到类似的又该怎么办。感觉这个知识不在自己的掌控下很难受。所以这次在网上找了找怎么读man page。鸟哥的我稍微有看,但是其实我是想知道关于参数的那些括号啊,分号啊有一些什么意思。然后我找到了BNF,我觉得这个的帮助是很大的。

开发者们看过来,这场长沙的开发者技术大会正在为你而来~_溪源More的博客-程序员宅基地

开发者们看过来,这场长沙的开发者技术大会正在为你而来~ 看过去,历史的尘埃与沧海桑田古语有云“近代中国,湖南独撑半边天”,湖南长沙,作为湖南省的省会,自古以来便是各界风云人士兴起之地。随着互联网时代的到来,长沙,这座历史悠久的文化名城,不仅仅是中国互联网人才的基地,更是成为已经逐渐成为中南地区具有足够影响力的实力当担,包括芒果视频、映客直播等...

MySQL基础_梦幻蔚蓝的博客-程序员宅基地

文章目录MySQL基础1,数据库相关概念1.1 数据库1.2 数据库管理系统1.3 常见的数据库管理系统1.4 SQL2,MySQL2.1 MySQL安装2.1.1 下载2.1.2 安装(解压)2.2 MySQL卸载2.3 MySQL配置2.3.1 添加环境变量2.3.2 新建配置文件2.3.3 初始化MySQL2.3.4 注册MySQL服务2.3.5 启动MySQL服务2.3.6 修改默认账户密码2.4 MySQL登陆和退出2.4.1 登陆2.4.2 退出2.5 My

iOS 面试题汇总_饭小粒的博客-程序员宅基地

1. Object-c的类可以多重继承么?可以实现多个接口么?Category是什么?重写一个类的方式用继承好还是分类好?为什么?答: Object-c的类不可以多重继承;可以实现多个接口,通过实现多个接口可以完成C++的多重继承;Category是类别,一般情况用分类好,用Category去重写类的方法,仅对本Category有效,不会影响到其他类与原有类的关系。2. #import 跟#include 又什么区别,@class呢, #import<> 跟 #import””又什么区别

2086 Problem A 最大连续子序列_fantasydreams的博客-程序员宅基地_problem a. 最大子矩阵和问题 时间限制 1000 ms 内存限制 64 mb 题目描述

问题 A: 最大连续子序列 时间限制: 1 Sec 内存限制: 32 MB 献花: 66 解决: 38 [献花][花圈][TK题库] 题目描述 给定K个整数的序列{ N1, N2, …, NK },其任意连续子序列可表示为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,例如给定序列{ ...