冒泡选择排序 普通二分查找

冒泡排序

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。
走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

选择排序

• 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

冒泡排序与选择排序示意图

package com.qianfeng.test;

public class Demo3 {
	public static void main(String[] args) {
		/*
		 * 排序：
		 * 冒泡排序，选择排序
		 * 查找：
		 * 二分查找
		 */
		
		int[] arr1 = {4,5,6,4,1,3};
		System.out.println("冒泡排序前：");
		for (int i : arr1) {
			System.out.print(i);
		}
		System.out.println();
		System.out.println("冒泡排序后：");
		//冒泡排序
		bubbleSort(arr1);
		for (int i : arr1) {
			System.out.print(i);
		}
		System.out.println();
		System.out.println("选择排序前：");
		int[] arr2 = {4,8,7,1,3,4};
		for (int i : arr2) {
			System.out.print(i);
		}
		System.out.println();
		System.out.println("选择排序后：");
		//选择排序
		selectSort(arr2);
		for (int i : arr2) {
			System.out.print(i);
		}
	}
	//冒泡排序
	public static void bubbleSort(int[] arr) {
//		int temp;
		for (int i = 0; i < arr.length - 1; i++) {//确定的整体次数，比较的次数比元素的个数少1
			for (int j = 0; j < arr.length - i - 1; j++) {//确定一个元素的时候比较的次数
				if (arr[j] > arr[j+1]) {
//					temp = arr[j];
//					arr[j] = arr[j+1];
//					arr[j+1] = temp;
					arr[j] = arr[j]^arr[j+1];
					arr[j+1] = arr[j]^arr[j+1];
					arr[j] = arr[j]^arr[j+1];
				}
			}
		}
	}
	
	
	//选择排序
	public static void selectSort(int[] arr) {
		int temp;
		for (int i = 0; i < arr.length - 1; i++) {//确定的整体次数，比较的次数比元素的个数少1
			for (int j = i; j < arr.length - 1; j++) {//确定一个元素的时候比较的次数
				if (arr[i] > arr[j+1]) {

					arr[i] = arr[i]^arr[j+1];
					arr[j+1] = arr[i]^arr[j+1];
					arr[i] = arr[i]^arr[j+1];
				}
			}
		}
	}
}

查找：

• 注意点：

1. 查到值时，返回值的下标
2. 查不到时，返回-1
3. 当有相同的值出现时，按照当前的查找方法返回查到的值的第一个值的下标，查找结束

普通查找

public static int search(int[] arr, int key) {
	for (int i = 0; i < arr.length; i++) {
		if(arr[i] == key) {
			return i;
		}
	}
	return -1;
}

二分查找

public static int erFenSearch(int[] arr, int key) {
		int h = arr.length - 1;
		int l = 0;
		int m = 0;
		while(l<=h) {
			m = (h + l)/2;
			if(arr[m] == key) {
				return m;
			}else if(arr[m] > key) {
				h = m - 1;
			}else if(arr[m] < key) {
				l = m + 1;
			}
			
		}
		return -1;
			
	}