冒泡排序
步骤
冒泡排序算法的运作如下：（从后往前）
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
举个栗子
原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |
-
第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
- 第二趟排序(外循环)
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
- 第三趟排序(外循环)
第一次两两比较2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 |5| 6 | 9 |
交换后状态| 1 | 2 | 4 |5| 6 | 9 |第四趟排序(外循环)无交换
第五趟排序(外循环)无交换
排序完毕,输出最终结果1 2 4 5 6 9
冒泡排序代码
public class BubbleSort
{
public void sort(int[] a)
{
int temp = 0;
for (int i = a.length - 1; i > 0; --i)
{
// 遍历数组，找到范围内的最大值
for (int j = 0; j < i; ++j)
{
// 交换两个数，把大的数放在后面
if (a[j + 1] < a[j])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
}
使用场景：
8个数据以下的排序适合使用，效率最高
选择排序
处理步骤：
(1)从待排序序列中，找到关键字最小的元素；
(2)如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
(3)从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
选择排序的代码实现
public void selectionSort(int[] list) {
// 需要遍历获得最小值的次数
// 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列
for (int i = 0; i < list.length - 1; i++) {
int index = i; // 用来保存最小值得索引
// 寻找第i个小的数值
for (int j = i + 1; j < list.length; j++) {
if (list[index] > list[j]) {
index = j;
}
}
// 将找到的第i个小的数值放在第i个位置上
if(index!=i) {//表示打到过最小值
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
}
递归算法
递归的实现
递归算法有四个特性：
（1）必须有可最终达到的终止条件，否则程序将陷入无穷循环；
（2）子问题在规模上比原问题小，或更接近终止条件；
（3）子问题可通过再次递归调用求解或因满足终止条件而直接求解；
（4）子问题的解应能组合为整个问题的解。
举个栗子
public void fun(int n){
System.out.println(n);
if(n<0){
return ;
}else{
fun(n-1);
System.out.println(n);
}
}
递归的执行过程
思考java方法调用流程是如何实现的
fun（3）的执行结果
3 2 1 0 -1
0 1 2 3
过程分析
- 首先执行fun（3），把fun（3）的代码压如栈中,打印3，调用fun（2）
- 执行fun（2），把fun（2）的代码压如栈中,打印2，调用fun（1）
- 执行fun（1），把fun（1）的代码压如栈中,打印1，调用fun（0）
- 执行fun（0），把fun（0）的代码压如栈中,打印1，调用fun（-1）
- 执行fun（-1），把fun（-1）的代码压如栈中,打印-1，n<0条件不满足，返回
- 执行fun（0）剩余的代码 System.out.println(0)，打印0，方法使用fun（0）完成，出栈
- 执行fun（1）剩余的代码 System.out.println(1)，打印1，方法使用fun（1）完成，出栈
- 执行fun（2）剩余的代码 System.out.println(2)，打印2，方法使用fun（2）完成，出栈
- 执行fun（3）剩余的代码 System.out.println(3)，打印3，方法使用fun（3）完成，出栈
- 方法全部已经出栈，调用fun（3）全部完成
fibonacci数列
斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）
public static long fibonacci(int n) {
if((0 == n) || (1 == n)) {
return n;
}else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
1加到n累加
用递归实现从1加到n，即1+2+3+4+...+n。
public static long total(int n) {
if(1 == n) {
return n;
}else {
return total(n-1) + n;
}
}
汉诺塔
中序遍历
public class Hanoi {
/**
*
* @param n 盘子的数目
* @param origin 源座
* @param assist 辅助座
* @param destination 目的座
*/
public void hanoi(int n, char origin, char assist, char destination) {
if (n == 1) {
move(origin, destination);
} else {
hanoi(n - 1, origin, destination, assist);
move(origin, destination);
hanoi(n - 1, assist, origin, destination);
}
}
// Print the route of the movement
private void move(char origin, char destination) {
System.out.println("Direction:" + origin + "--->" + destination);
}
public static void main(String[] args) {
Hanoi hanoi = new Hanoi();
// 三个元素 1 2 3 从上往下叠加
hanoi.hanoi(3, 'A', 'B', 'C');
}
}
二分查找
算法实现思路：
找出位于数组中间的值（为便于表述，将该值放在一个临时变量tmp中）。
需要找到的key和tmp进行比较。
如果key值大于tmp，则把数组中间位置作为下一次计算的起点；重复第1、2步骤继续查找。
如果key值小于tmp，则把数组中间位置作为下一次计算的终点；重复第1、2步骤继续查找。
如果key值等于tmp，则返回数组下标，完成查找。
注意：设计成左闭右开--是一种区间无重复的思想
//二分查找 在array找formIndex到toIndex之间的数，有没有key这个值
public static int binarySearch(int[] array,int fromIndex,int toIndex,int key){
int low=fromIndex;
int high=toIndex-1;// 思考toIndex为什么要-1
while(low<=high){
int mid=(low+high)/2;// >>>1 无符号除2
int midVal=array[mid];
if(key>midVal){//去右边找
low=mid+1;
}else if(key<midVal){
high=mid-1;
}else{
return mid;
}
}
return -(low+1);
}
binarySearch(array,0,array.length,key)
二分查找递归代码
仅做研究学习使用，不适合用于实际开发，因为函数的压栈、出栈消耗的时间过长
//二分查找法（递归）
public static int binSearch(int srcArray[], int start, int end, int key) {
int mid = (end + start) / 2;
if (srcArray[mid] == key) {
return mid;
}
if (start < end) {
if (key > srcArray[mid]) {
return binSearch(srcArray, mid + 1, end, key);
} else if (key < srcArray[mid]) {
return binSearch(srcArray, start, mid - 1, key);
}
}
return -1;
}
分治法
分治法的精髓：
- 分--将问题分解为规模更小的子问题；
- 治--将这些规模更小的子问题逐个击破；
- 合--将已解决的子问题合并，最终得出“母”问题的解；
快速排序
下图一张展示一次快排的步骤，另一种展示全部快排的步骤
快速排序的代码 （前序遍历）
quickSort(array,0,array.length-1);
//快速排序 31 12 68 40 59 21 x=31
public static void quickSort(int[] array,int begin,int end){
if(end-begin==0) {return ;}
int x=array[begin];//31
int low=begin;//0
int high=end;//5
//由于会在两头取数据，需要一个方向
boolean direction =true;
//开始进行数据的移动
L1:
while(low<high){
if(direction){//从右往左找
for(int i=high;i>low;i--){
if(array[i]<=x){
array[low++]=array[i];
high=i;
direction=!direction;
continue L1;
}
}
high=low;
}else{
for(int i=low;i<high;i++){
if(array[i]>=x){
array[high--]=array[i];
low=i;
direction=!direction;
continue L1;
}
}
low=high;
}
}
//把最后找到的值放入中间位置
array[low]=x;
//开始完成左右两边的操作
quickSort(array,begin,low-1);//L
quickSort(array,low+1,end);//R
}
应用场景：
- 数据量大并且是线性结构
不适用场景：
- 有大量重复数据的时候，性能不好
- 单向链式结构处理性能不好（一般来说，链式都不使用）
归并排序
归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。
public static void merge(int[] array,int left,int mid,int right){
int leftSize=mid-left;
int rightSize=right-mid+1;
//生成数组
int[] leftArray=new int[leftSize];
int[] rightArray=new int[rightSize];
//填充左边的数组
for(int i=left;i<mid;i++){
leftArray[i-left]=array[i];
}
//填充右边的数组
for(int i=mid;i<=right;i++){
rightArray[i-mid]=array[i];
}
//合并数组
int i=0;
int j=0;
int k=left;
while(i<leftSize && j<rightSize){
if(leftArray[i]<rightArray[j]){
array[k]=leftArray[i];
k++;
i++;
}else{
array[k]=rightArray[j];
k++;
j++;
}
}
while(i<leftSize){//左边还有数据没用完
array[k]=leftArray[i];
k++;
i++;
}
while(j<rightSize){//右边还有数据没用完
array[k]=rightArray[j];
k++;
j++;
}
}
public static void mergeSort(int array[],int left,int right){
if(left==right){
return;
}else{
int mid=(left+right)/2;
mergeSort(array,left,mid);//排好左边 L
mergeSort(array,mid+1,right);//排好右边 R
merge(array,left,mid+1,right);//再对左右进行合并 D
}
}
