文档章节

排序知识笔记

GoldenVein
 GoldenVein
发布于 2014/03/26 09:30
字数 518
阅读 29
收藏 0

排序分类:内部排序和外部排序

内部排序:只使用内存 外部排序:内存和空间结合使用

内部排序:1、插入排序(直接插入排序、希尔排序) 2、选择排序(简单选择排序、堆排序) 3、交换排序(冒泡排序、快速排序)4、归并排序 5、分配排序(箱排序、基数排序)

所需辅助空间最多:归并排序 所需辅助空间最小:堆排序 平均速度最快: 快速排序 不稳定: 快速排序、希尔排序、堆排序

选择排序算法根据以下三点来选择排序算法: 1、数据的模块 2、数据的类型 3、数据已有的顺序

当规模较小时选择直接插入排序或者冒泡排序,当数据量较小时候对于任何算法来说体现不出来差异性。 如果全是正整数优先选择桶排序 当数据已有顺序,选择冒泡排序,如果是大量的随机数据选择快速排序(不稳定)。

各种排序的实现: 1)冒泡排序

 public static int[] BubbleSort(int[] data) {
	boolean flag = true;
	for (int i = 0; i < data.length && flag; i++) {
		flag = false;
		for (int j = 0; j < data.length - i - 1; j++) {
			if (data[j] > data[j + 1]) {
				int tmp = data[j];
				data[j] = data[j + 1];
				data[j + 1] = tmp;
				flag = true;
			}
		}
	}
	return data;
}

2)快速排序

public static int[] quickSort(int[] data) {
	if (data.length > 0) {
		quickSortCore(data, 0, data.length - 1);
	}
	return data;
}

private static void quickSortCore(int[] list, int low, int high) {
	if (low < high) {
		int middle = getMiddle(list, low, high); // 将list数组进行一分为二
		quickSortCore(list, low, middle - 1); // 对低字表进行递归排序
		quickSortCore(list, middle + 1, high); // 对高字表进行递归排序
	}
}

private static int getMiddle(int[] list, int low, int high) {
	int tmp = list[low]; // 数组的第一个作为中轴
	while (low < high) {
		while (low < high && list[high] >= tmp) {

			high--;
		}
		list[low] = list[high]; // 比中轴小的记录移到低端
		while (low < high && list[low] <= tmp) {
			low++;
		}
		list[high] = list[low]; // 比中轴大的记录移到高端
	}
	list[low] = tmp; // 中轴记录到尾
	return low; // 返回中轴的位置
}

© 著作权归作者所有

上一篇: 斐波那契数列
下一篇: 常见TCP端口号
GoldenVein
粉丝 8
博文 113
码字总数 23459
作品 0
朝阳
程序员
私信 提问
【面试总结】记一次失败的 bilibili 面试总结(2)

上一篇文章能受到这样的关注度,感谢各位同学的点赞和评论,给了我很多动力继续去更新这个系列,也希望它们能够对大家有一定的帮助。蟹蟹大家。 传送门 面试总结(1):HTML布局、CSS选择器及J...

一颗赛艇🚤
03/13
0
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
【Visual C++】游戏开发笔记之十一 基础动画显示(四) 排序贴图

本系列文章由zhmxy555编写,转载请注明出处。 http://blog.csdn.net/zhmxy555/article/details/7385605 作者:毛星云 邮箱: happylifemxy@qq.com 欢迎邮件交流编程心得 “排序贴图”是源自于...

长平狐
2012/11/12
68
0
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
2018/07/25
0
0
Android--面试中遇到的问题总结(三)

《Android 开发工程师面试指南 LearningNotes 》,作者是陶程,由梁观全贡献部分。大家可以去知乎关注这两位用心的少年。这份指南包含了大部分Android开发的基础、进阶知识,不仅可以帮助准备...

sealin
2017/02/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

64.监控平台介绍 安装zabbix 忘记admin密码

19.1 Linux监控平台介绍 19.2 zabbix监控介绍 19.3/19.4/19.6 安装zabbix 19.5 忘记Admin密码如何做 19.1 Linux监控平台介绍: 常见开源监控软件 ~1.cacti、nagios、zabbix、smokeping、ope...

oschina130111
今天
13
0
当餐饮遇上大数据,嗯真香!

之前去开了一场会,主题是「餐饮领袖新零售峰会」。认真听完了餐饮前辈和新秀们的分享,觉得获益匪浅,把脑子里的核心纪要整理了一下,今天和大家做一个简单的分享,欢迎感兴趣的小伙伴一起交...

数澜科技
今天
7
0
DNS-over-HTTPS 的下一代是 DNS ON BLOCKCHAIN

本文作者:PETER LAI ,是 Diode 的区块链工程师。在进入软件开发领域之前,他主要是在做工商管理相关工作。Peter Lai 也是一位活跃的开源贡献者。目前,他正在与 Diode 团队一起开发基于区块...

红薯
今天
10
0
CC攻击带来的危害我们该如何防御?

随着网络的发展带给我们很多的便利,但是同时也带给我们一些网站安全问题,网络攻击就是常见的网站安全问题。其中作为站长最常见的就是CC攻击,CC攻击是网络攻击方式的一种,是一种比较常见的...

云漫网络Ruan
今天
12
0
实验分析性专业硕士提纲撰写要点

为什么您需要研究论文的提纲? 首先当您进行研究时,您需要聚集许多信息和想法,研究论文提纲可以较好地组织你的想法, 了解您研究资料的流畅度和程度。确保你写作时不会错过任何重要资料以此...

论文辅导员
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部