基础算法(二)

        上一篇:基础算法(一)

        1. 冒泡排序(BubbleSort)

        原理:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。   由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。   用二重循环实现,外循环变量设为i,内循环变量设为j。外循环重复9次,内循环依次重复9,8,...,1次。每次进行比较的两个元素都是与内循环j有关的,它们可以分别用a[j]和a[j+1]标识,i的值依次为1,2,...,9,对于每一个i,j的值依次为1,2,...10-i。

        实现的代码如下:

public static void bubbleSort(int[] array) {
		for(int i = 1; i < array.length; i++) {
			for(int j = 0; j < array.length - i; j++) {
				if(array[j] > array[j + 1]) {
					int tmp = array[j + 1];
					array[j + 1] = array[j];
					array[j] = tmp;
				}
			}
		}
}

2. 选择排序

        原理:n个数的直接选择排序可经过n-1趟直接选择排序得到有序结果:         ①初始状态:无序区为R[1..n],有序区为空。         ②第1趟排序,在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。         ……         ③第i趟排序,第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。         这样,n个数的直接选择排序可经过n-1趟直接选择排序得到有序结果。

        实现的代码如下:

public static void selectionSort(int[] array) {
		for(int i = 0; i < array.length - 1; i++) {
			int min = i;
			for(int j = i + 1; j < array.length; j++) {
				if(array[j] < array[min]) {
					min = j;
				}
			}
			if(min != i) {
				int temp = array[min];
				array[min] = array[i];
				array[i] = temp;
			}
		}
}

3. 寻找孤立数字         需求:给定一个数组,数组内的数两两相同,只有一个数是孤立的,用最快的方式找出这个数。

        分析:循环数组,判断第i个元素的值和其它位置的值是否相等,如果不存在相等的,那么这个数就是孤立数据。

        实现的代码如下:        

int[] array = {1, 2, 3, 2, 3, 1, 4};
int single = 0;
for(int i = 0; i < array.length; i++) {
  boolean isSingle = true;
  for(int j = 0; j < array.length; j++) {
    if(j != i && array[i] == array[j]) {
      isSingle = false;
      break;
    }
  }
  if(isSingle) {
    single = array[i];
    break;
  }
}

        显然这样的嵌套循环判断复杂度是很高的,所以使用^,则实现的代码如下:

int[] array = {1, 2, 3, 2, 3, 1, 4};
int single = array[0];
for(int i = 1; i < array.length; i++) {
		single ^= array[i];
}

        一个for循环搞定,不怕做不到,就怕想不到。

4. 进制转换

        将一个整型数据转换成二进制字符串。

        分析:整型一共32位,最高位代表正负,那么得到第i位的数只需要将整数右移i-1位,实现的代码如下;

public static String toBinary(int value) {
		StringBuilder build = new StringBuilder();
		for(int i = 31; i >= 0; i--) {
			build.append(value >> i & 1);// 和1做与操作之后,该位置之前的数全部干掉
		}
		return build.toString();	
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2762
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

471
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2349
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

822
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4
来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1831
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2608
来自专栏闵开慧

Failed to set permissions of path

12/09/04 16:46:34 INFO support.ClassPathXmlApplicationContext: Refreshing org...

2757
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

931
来自专栏marsggbo

Udacity并行计算课程 CS344 编程作业答案

892

扫码关注云+社区