文档章节

几种基本算法

学渣要逆袭
 学渣要逆袭
发布于 2017/05/11 18:07
字数 1437
阅读 9
收藏 0

在这里记录下:

/**
 * 排序
 */
public class PaiXuTest {

	// 1、直接插入排序
	/*
	 * 基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排 好顺序的,现在要把第n个数插到前面的有序数中,使得这 n个数
	 * 也是排好顺序的。如此反复循环,直到全部排好顺序。
	 */
	public static void insertSort(int array[]) {
		int temp = 0;
		for (int i = 0; i < array.length; i++) {
			int j = i - 1;
			temp = array[i];
			for (; j >= 0 && temp < array[j]; j--) {
				array[j + 1] = array[j];// 将temp的值整体向后移动一个单位
			}
			array[j + 1] = temp;
		}

		for (int i = 0; i < array.length; i++) {
			System.out.println("插入排序="+array[i]);
		}
	}

	// 2、希尔排序(最小增量排序)
	/*
	 * 基本思想:算法先将要排序的一组数按某个增量 d(n/2,n为要排序数的个数)分成若 干组,每组中记录的下标相差
	 * d.对每组中全部元素进行直接插入排序,然后再用一个较小 的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到 1 时,进行直接
	 * 插入排序后,排序完成。
	 */

	public static void shellSort(int array[]) {
		double d1 = array.length;
		int temp = 0;
		while (true) {
			d1 = Math.ceil(d1 / 2);
			int d = (int) d1;
			for (int i = 0; i < d; i++) {
				for (int j = i + d; j < array.length; j += d) {
					int k = j - d;
					temp = array[j];
					for (; k >= 0 && temp < array[k]; k -= d) {
						array[k + d] = array[k];
					}
					array[k + d] = temp;
				}
			}
			if (d == 1) {
				break;
			}

		}
		for (int i = 0; i < array.length; i++) {
			System.out.println("希尔排序="+array[i]);
		}
	}

	// 3、选择排序
	/*
	 * 基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;
	 * 
	 * 然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一
	 * 
	 * 个数比较为止。
	 */
	public static void selectSort(int array[]) {
		int point = 0;
		for (int i = 0; i < array.length; i++) {
			int j = i + 1;
			point = i;
			int temp = array[i];
			for (; j < array.length; j++) {
				if (array[j] < temp) {
					temp = array[j];
					point = j;
				}
			}
			array[point] = array[i];
			array[i] = temp;
		}

		for (int i = 0; i < array.length; i++) {
			System.out.println("选择排序"+array[i]);
		}
	}

	// 4、冒泡排序
	/*
	 * 基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对
	 * 
	 * 相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的
	 * 
	 * 数比较后发现它们的排序与排序要求相反时,就将它们互换。
	 */
	public static void bubbleSort(int array[]){
		int temp = 0;
		for (int i = 0; i < array.length-1; i++) {
			for (int j = 0; j < array.length-1-i; j++) {
				if (array[j] > array[j+1]) {
					temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				}
			}
		}
		for (int i = 0; i < array.length; i++) {
			System.out.println("冒泡排序"+array[i]);
		}
	}
	
	//5、快速排序 
	/*
	 * 基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,
	 * 
	 * 将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其
	 * 
	 * 排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
	 */ 
	public static void quickSort(int array[]){
		// 判断数组是否为空
		if (array.length > 0) {
			_quickSort(array, 0, array.length-1);
		}
		for (int i = 0; i < array.length; i++) {
			System.out.println("快速排序="+array[i]);
		}
	}
	public static	int getMiddle(int[] list,int low,int hight){
		// 数组的第一个做为中轴
		int temp = list[low];
		while (low < hight) {
			while (low < hight && list[hight] >= temp) {
				hight --;	
			}
			// 比中轴小的记录移动到低	端
			list[low] = list[hight];
			while (low < hight && list[low] <= temp) {
				low ++;
			}
			// 比中轴大的移动到高端
			list[hight] = list[low];
		}
		// 中轴记录到尾
		list[low] = temp;
		// 返回中轴的位置
		return low;
	}
	public static void _quickSort(int[] list,int low,int hight) {
		if (low < hight) {
			// 将list 数组进行一分为二
			int middle = getMiddle(list, low, hight);
			// 对低字表进行递归排序
			_quickSort(list, low, middle-1);
			// 对高子表进行递归排序
			_quickSort(list, middle+1, hight);
		}
	}
	
	// 6、归并排序
	/*
	 * 基本排序:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有
	 * 
	 * 序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并
	 * 
	 * 为整体有序序列。
	 */ 
	public static void mergingSort(int array[]){
		sort(array,0,array.length-1);
		for (int i = 0; i < array.length; i++) {
			System.out.println("归并排序"+array[i]);
		}
	}
	public static void sort(int[] array, int left, int right) {
		if (left < right) {
			// 找出中间索引
			int middle = (left+right) / 2;
			// 对左边数组进行递归
			sort(array, left, middle);
			// 对右边数组进行递归
			sort(array, middle+1, right);
			// 合并
			merge(array,left,middle,right);
		}
		
	}
	public static void merge(int[] array, int left, int middle, int right) {
		int[] tempArray = new int[array.length];
		int mid = middle +1;
		// third 记录中间数组的索引
		int third = left;
		int temp = left;
		while (left <= middle && mid <= right) {
			// 从两个数组中取出最小的数组放在中间数组
			if (array[left] <= array[mid]) {
				tempArray[third++] = array[left++];
			}else{
				tempArray[third++] = array[mid++];
			}
		}
		// 剩余部分依次放入中间数组
		while (mid <= right) {
			tempArray[third++] = array[mid++];
		}
		while (left <= middle) {
			tempArray[third++] = array[left++];
		}
		// 将中间数组中的内容复制到原数组
		while (temp <= right) {
			array[temp] = tempArray[temp++];
		}
	}

	// 主程序
	public static void main(String[] args) {
		int array[] = { 49, 38, 65, 97, 76, 13, 27 };
		/* Java 工具类
		 * Arrays.sort(array);
		for (int i = 0; i < array.length; i++) {
			System.out.println("--" + array[i]);
		}*/

		// 1、PaiXuTest.insertSort(array);
		// 2、PaiXuTest.shellSort(array);
		// 3、PaiXuTest.selectSort(array);
		// 4、bubbleSort(array);
		// 5、quickSort(array);
		// 6、mergingSort(array);
	}

}

 

 

本文转载自:

学渣要逆袭
粉丝 0
博文 37
码字总数 9342
作品 0
朝阳
后端工程师
私信 提问
程序员的自我修养——操作系统篇

目录: 1. 进程的有哪几种状态,状态转换图,及导致转换的事件。 2. 进程与线程的区别。 3. 进程通信的几种方式。 4. 线程同步几种方式。 5. 线程的实现方式. (用户线程与内核线程的区别) 6...

马浩
2014/06/30
0
0
谱聚类简明教程(前言)

原文:A Tutorial on Spectral Clustering https://arxiv.org/pdf/0711.0189 作者:U von Luxburg - ‎2007 - ‎被引用次数:5313 摘要:     近年来,谱聚类已发展成为最流行的现代聚类算...

reasonW
2018/01/01
0
0
统计学习方法|AdaBoost

01 起 在之前的文章中,我们学习了几种经典的分类算法:KNN,Naive Bayes,Decision Tree,Logistic Regression,SVM。 接下来我们学习一种方法来提升分类效果,这种方法的核心思想就是:三个...

邓莎
2018/10/07
0
0
浙大的游戏设计教程

第一部分 游戏程序设计概览 计算机游戏简介:什么是游戏、游戏的分类等 游戏的基本开发流程? 游戏开发的基本理念及方法 游戏软件的体系结构:包括三维游戏引擎的架构分析 游戏的调试与测试 ...

Matrix4X4
2012/08/19
361
2
程序员?这些面试题你能答对几个?

  三人行必有我师,人生是需要不断学习的,在这里我们相遇就是缘分,希望各位可以看完这篇文章,也欢迎大家在下面留言讨论,天冷了,也动动手指转发收藏一下,谢谢大家!   一、数据结构...

java分享
2017/12/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

数据库

数据库架构 数据库架构可以分为存储文件系统和程序实例两大块,而程序实例根据不同的功能又可以分为如下小模块。 1550644570798 索引模块 常见的问题有: 为什么要使用索引 什么样的信息能成...

一只小青蛙
今天
4
0
PHP常用经典算法实现

<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){ if ( $low <= $high){ $mid = int......

半缘修道半缘君丶
昨天
5
0
GIL 已经被杀死了么?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/8KvQemz0SWq2hw-2aBPv2Q 花下猫语: Python 中最广为人诟病的一点,大概就是它的 GIL 了。...

豌豆花下猫
昨天
5
0
git commit message form

commit message一般包括3部分:Header、Body、Footer。 <type>(<scope>):<subject>blank line<body>blank line<footer> header是必需的,body、footer可以省略。 header中type、subject......

ninjaFrog
昨天
5
0
聊聊Elasticsearch的CircuitBreakerService

序 本文主要研究一下Elasticsearch的CircuitBreakerService CircuitBreakerService elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/indices/breaker/CircuitBreakerService.ja......

go4it
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部