蛮力法
冒泡排序
2的3次方以内的用冒泡排序
private void BubbleSort(int[] array) {
for (int j = array.length-1; j >0; j--) {
boolean flag =true;
for (int i = 0; i < j; i++) {
if (array[i] > array[i + 1]) {
flag=false;
int tmp =array[i+1];
array[i+1]=array[i];
array[i] =tmp;
}
}
if (flag){
break;
}
}
}
选择排序
先定位再交换
public class SelectSort {
public static void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
//选出当前序列最小值的index
int index = i;
for (int j = i + 1; j < array.length; j++) {
if (array[index] > array[j]) {
index = j;
}
}
if (index != i) {
int tmp = array[index];
array[index] = array[i];
array[i] = tmp;
}
}
}
}
递归
斐波那契数列
public static int FibonacciSequence(int i) {
if (i == 1 || i == 2) {
return 1;
} else {
return FibonacciSequence(i - 1) + FibonacciSequence(i - 2);
}
}
调用;
//斐波那契数列
for (int i = 1; i < 11; i++) {
System.out.println( Recursion.FibonacciSequence(i));
}
输出结果：
1
1
2
3
5
8
13
21
34
55
汉诺塔
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
每次只能移动一个圆盘；
大盘不能叠在小盘上面。
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
private void hanoi(int n, int start, int middle, int end) {
if (n == 1) {
System.out.println(start + "---------------->" + end);
} else {
hanoi(n - 1, start, end, middle);
System.out.println(start + "---------------->" + end);
hanoi(n - 1, middle, start, end);
}
}
调用：
hanoi(3, 1, 2, 3);
输出：
1---------------->3
1---------------->2
3---------------->1
1---------------->3
2---------------->3
2---------------->1
3---------------->2
分治法
顺序查找
二分查找
首先这个序列必须是有序的
int [] test ={1,2,3,4,7,9,10,12};
/**
* 二分查找
* @param array 数据
* @param startIndex 开始位置交标
* @param endIndex 结束位置交标
* @param key 寻找的数字
* @return 数字所在的交标 返回负值表示异常
*/
private int binarySearch(int[] array, int startIndex, int endIndex, int key) {
if (startIndex < 0 || endIndex < 0 || startIndex >= endIndex || endIndex > array.length) {
return -1;
}
int low = startIndex;
int high = endIndex-1;//遵循左闭右开原则
while (low <= high) {
int mid = (low + high) >>> 1;
int midValue = array[mid];
if (key < midValue) {
high = mid - 1;
} else if (key > midValue) {
low = mid + 1;
} else {
return mid;
}
}
return -(low + 1);
}
快速排序
应用场景：数据量大并且是线性排序。
注意：不要在链式结构中使用，重复数据过多也不合适
/**
* 快速排序
*
* @param array
* @param begin
* @param end
*/
private static void quickSort(int[] array, int begin, int end) {
if (end - begin <= 1) {
return;
}
int x = array[begin];//暂存枢纽
int low = begin;
int high = end;
boolean direction = true;//排序方向 true:为从右往左 false:从左往右
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);
quickSort(array, begin + 1, end);
}
输出结果：
31 68 45 90 23 39 54 12 87 76
12 23 31 39 45 54 68 76 87 90
归并排序
解决快排不能操作单链表的问题，但是空间牺牲大
/**
* 归并排序
*
* @param array
* @param left
* @param right
*/
public static void mergeSort(int[] array, int left, int right) {
if (left == right) {
return;
} else {
int mid = (left + right) / 2;
mergeSort(array, left, mid);//排好左边
mergeSort(array, mid + 1, right);//排好右边
merge(array, left, mid + 1, right);//再对左右进行合并
}
}
/**
* 通过拆分数组合并数据来对数据排序
*
* @param array
* @param left
* @param mid
* @param right
*/
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++];
} else {
array[k++] = rightArray[j++];
}
}
//表示左边还有数据没有合并完
while (i < leftSize) {
array[k++] = leftArray[i++];
}
//表示右边边还有数据没有合并完
while (j < rightSize) {
array[k++] = rightArray[j++];
}
}
插入
直接插入排序
在已经有序的数据中，插入一个数据，使用插入排序效率是非常高的。比如纸牌和麻将
/**
* 直接插入排序
* @param array
*/
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int j =i;
int target =array[i];
while (j>0 &&target<array[j-1]){
array[j]=array[j-1];
j--;
}
array[j]=target;
}
}
希尔排序
对插入排序进行优化，增加了一个步长
/**
* 希尔排序
*
* @param array
* @param step 步长
*/
public static void shellSort(int[] array, int step) {
for (int k = 0; k < step; k++) {//k 是对步长的一个定位，选择每次操作的开始位置
for (int i = k + step; i < array.length; i = i + step) {
int j = i;
int target = array[i];
while (j > step - 1 && target < array[j - step]) {
array[j] = array[j - step];
j=j-step;
}
array[j] = target;
}
}
}
