这学期老师把算法交完了，整理了一些最常用的算法，其实最主要的还是算法思想
算法思想有很多，业界公认的常用算法思想有8种，分别是枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟。当然8种只是一个大概的划分，是一个“仁者见仁、智者见智”的问题
- 设置两个变量i、j，排序开始的时候：i=0，j=N-1；
- 以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
- 从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
- 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
- 重复第3、4步，直到i==j；
- 3,4步中，没找到符合条件的值，即3中 A[ j ] 不小于key,4中 A[ i ]不大于key的时候改变 j、i 的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候 i，j 指针位置不变。另外，i== j这一过程一定正好是 i + 或 j - 完成的时候，此时令循环结束
| 此时ref=5，i=1，j=11，从后往前找，第一个比5小的数是x8=2，因此序列为：2 3 7 6 4 1 0 5 9 10 8 |
|---|
| 此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2 3 5 6 4 1 0 7 9 10 8 |
| 此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2 3 0 6 4 1 5 7 9 10 8 |
| 此时，i=3，j=7，从第3位往后找，第一个比5大的数是x4=6，因此：2 3 0 5 4 1 6 7 9 10 8 |
| 此时，i=4，j=7，从第7位往前找，第一个比5小的数是x6=1，因此：2 3 0 1 4 5 6 7 9 10 8 |
| 此时，i=4，j=6，从第4位往后找，直到第6位才有比5大的数，这时，i=j=6，ref成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前后两部分数，可以采用同样的方法来排序 |
package test1;
public class First {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("hello，world！");
int[] a =new int[]{100,44,66,88,33,11,44,2};
System.out.println("未排序前的数据为：");
print(a);
System.out.println("排序后的结果为：");
sort(a,0,a.length-1);
print(a);
}
public static void print(int[] b){
for(int i = 0;i < b.length;i++){
System.out.println(b[i]);
}
System.out.println("");
}
//排序方法
static void sort(int[] a,int low,int high){
if(low>=high)
return;// low小于high ,则直接返回
if((high-low)==1){//如果只有两个数字，则直接进行比较
if(a[0]>a[1])
swap(a,0,1);
return;
}
int pivot = a[low];//取第一个数作为哨兵
int left = low + 1;//开始逐步进行交换，因为哨兵为第一个元素，所以进行第二个数进行开始与最右边的进行对比
int right = high;
while(left < right){
while(left < right && left <= high){//如果左小于右则一直循环 33 100,40,60,87,34,11,56,0
if (a[left]>pivot) //left =1 right=7
break;
left++;//左下标往右边走一点
}
//从右边开始找
while(left <= right&& right > low){//如果左大于右则一直循环
if(a[right]<=pivot)
break;
right--;//右下标往左走一点
}
if(left < right)//如果没有找完，则交换数字
swap(a,right,left);
}
swap(a,low,right);//交换哨兵，进行下一次快速排序
sort(a,low,right);
sort(a,right+1,high);
}
private static void swap(int[] array,int i,int j){
int temp;
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
结果为
2.直接排序算法
原理
直接选择排序(Straight Select Sorting) 也是一种简单的排序方法，它的基本思想是：第一次从R[0]R[n-1]中选取最小值，与R[0]交换，第二次从R[1]R[n-1]中选取最小值，与R[1]交换，…，第i次从R[i-1] ~ R[n-1]中选取最小值，与R[i-1]交换，…，第n-1次从R[n-2] ~ R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
演示 演示例如:给定n=8，数组R中的8个元素的排序码为(8,3,2,1,7,4,6,5),则直接选择排序的过程如下所示
由于不方便画出关联箭头 所以用 n – n 表示 ：
| 初始状态 [ 8 3 2 1 7 4 6 5 ] 8 – 1 |
|---|
| 第一次 [ 1 3 2 8 7 4 6 5 ] 3 – 2 |
| 第二次 [ 1 2 3 8 7 4 6 5 ] 3 – 3 |
| 第三次 [ 1 2 3 8 7 4 6 5 ] 8 – 4 |
| 第四次 [ 1 2 3 4 7 8 6 5 ] 7 – 5 |
| 第五次 [ 1 2 3 4 5 8 6 7 ] 8 – 6 |
| 第六次 [ 1 2 3 4 5 6 8 7 ] 8 – 7 |
| 第七次 [ 1 2 3 4 5 6 7 8 ] 排序完成 |
package test1;
import java.util.*;
public class Sort {
public static void main(String[] args) {
int array[] = new int[20];//定义数组的大小
array = new int[] { 5, 3, 7, 9, 23, 42, 12, 1 };
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
System.out.println(Arrays.toString(array));// 输出每次循环后排序所得的内容
}
System.out.println(Arrays.toString(array));// 输出最后的排序结果
}
}
结果
3.插入排序
插入排序的基本思想是:每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
-
从有序数列和无序数列{a2,a3，…，an}开始进行排序；
-
处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与ai-1，a i-2，…，a1进行比较，找出合适的位置将ai插入；
-
重复第二步，共进行n-i次插入处理，数列全部有序。
package test1;
import java.util.Arrays;
public class InsertionSorting {
public static void main(String[] s) {
int[] arr = {1,2,3,0};
System.out.println("排序前："+Arrays.toString(arr));
insertSort(arr,0,arr.length);
System.out.println("排序后："+Arrays.toString(arr));
}
public static void insertSort(int[] object,int low,int high) { //将第一个值看做一个有序序列
for(int i = 1;i < high;i++) {
if(object[i] < object[i-1]) {
int temp = object[i];//待比较的数值
int j = i-1;
for(;j >= low&&object[j] > temp;j--) {
object[j+1] = object[j];
}
//比较完成后获得j最后的位置
object[j+1] = temp;
}
}
}
}
结果
排序前：[1, 2, 3, 0]
排序后：[0, 1, 2, 3]
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度
实例在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，
末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]
package test1;
import java.util.Arrays;
public class SplitInsertionSort {
public static void main(String[] args){
// 待排序的数组
int[] array = { 1, 0, 2, 5, 3, 4, 9, 8, 10, 6, 7};
System.out.println("折半排序前："+Arrays.toString(array));
binaryInsertSort(array);
// 显示排序后的结果。
System.out.println("折半排序后"+Arrays.toString(array));
}
// Binary Insertion Sort method
private static void binaryInsertSort(int[] array){
for(int i = 1; i < array.length; i++){
int temp = array[i];
int low = 0;
int high = i - 1;
while(low <= high){
int mid = (low + high) / 2;
if(temp < array[mid]){
high = mid - 1;
}else{
low = mid + 1;
}
}
for(int j = i; j >= low + 1; j--){
array[j] = array[j - 1];
}
array[low] = temp;
}
}
}
结果
折半排序前：[1, 0, 2, 5, 3, 4, 9, 8, 10, 6, 7]
折半排序后[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
冒泡排序（Bubble Sort）它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数
- 针对所有的元素重复以上的步骤，除了最后一个
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
package test1;
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int arr[]) {
for(int i = 0 ; i < arr.length-1 ; i++) {
for(int j = 0 ; j < arr.length-1-i ; j++) {
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] arr = {10,20,3,0,40,52,3,4};
System.out.println("冒泡排序前："+Arrays.toString(arr));
bubbleSort(arr);
System.out.println("冒泡排序后"+Arrays.toString(arr));
}
}
结果
冒泡排序前：[10, 20, 3, 0, 40, 52, 3, 4]
冒泡排序后[0, 3, 3, 4, 10, 20, 40, 52]
数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
方案：设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
package test1;
import java.util.Arrays;
public class BubbleSort {
public static void BubbleSort1(int [] arr){
int temp;//临时变量
boolean flag;//是否交换的标志
for(int i=0; ii; j--){ //选出该趟排序的最大值往后移动
if(arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true; //只要有发生了交换，flag就置为true
}
}
// 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
if(!flag) break ;}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] arr = {10,20,3,0,40,52,3,4};
System.out.println("冒泡排序前："+Arrays.toString(arr));
BubbleSort1(arr);
System.out.println("冒泡排序后"+Arrays.toString(arr));
}
}
结果
冒泡排序前：[10, 20, 3, 0, 40, 52, 3, 4]
冒泡排序后[0, 3, 3, 4, 10, 20, 40, 52]
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
给定实例的shell排序的排序过程
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：5，2，1
package test1;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args){
int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
System.out.println("排序前"+Arrays.toString(array));
//希尔排序
int gap = array.length;
while (true) {
gap /= 2; //增量每次减半
for (int i = 0; i < gap; i++) {
for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
int k = j - gap;
while (k >= 0 && array[k] > array[k+gap]) {
int temp = array[k];
array[k] = array[k+gap];
array[k + gap] = temp;
k -= gap;
}
}
}
if (gap == 1)
break;
}
System.out.println();
System.out.println("排序后"+Arrays.toString(array));
}
}
结果
排序前[49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1]
排序后[1, 12, 13, 27, 34, 38, 49, 49, 64, 65, 76, 78, 97]
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并
归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作
如 设有数列{6，202，100，301，38，8，1}
初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数
i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3
i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4
i=3 [ 1 6 8 38 100 202 301 ] 4
总计： 11次代码
package test1;
import java.util.Arrays;
public class MergeSort {
//测试
public static void main(String[] args) {
Integer[] I = {5,3,1,4,2,10,6,7};
System.out.println("排序前："+Arrays.toString(I));
sort(I);
System.out.println("排序后："+Arrays.toString(I));
}
//实现归并操作
public static void merge(Comparable[] a, int lo, int mid, int hi){
//定义三个指针
int p1= lo; //p1指向左子组的第一个元素
int p2= mid+1; //p2指向右子组的第一个元素
int i = lo; //i指向辅助数组的第一个元素
//定义辅助数组
Comparable[] aux = new Comparable[a.length];
//实现归并
while(p1<=mid || p2<=hi) {
if (p1 > mid) aux[i++] = a[p2++];
else if (p2 > hi) aux[i++] = a[p1++];
else if (a[p1].compareTo(a[p2]) < 0) aux[i++] = a[p1++];
else aux[i++] = a[p2++];
}
//将排序之后的aux数组复制给原来的数组a，这样a中对应的元素便是有序的
for (int k = lo; k <= hi; k++) {
a[k]=aux[k];
}
}
public static void sort(Comparable[] a){
sort(a,0,a.length-1);
}
public static void sort(Comparable[] a, int lo, int hi){
if (hi<=lo) return;
//分成两组
int mid = lo+(hi-lo)/2;
//通过递归进行排序
sort(a,lo,mid);
sort(a,(mid+1),hi);
merge(a,lo,mid,hi);
}
}
结果
排序前：[5, 3, 1, 4, 2, 10, 6, 7]
排序后：[1, 2, 3, 4, 5, 6, 7, 10]
非递归实现归并排序的划分函数Merge和递归的归并排序是一样的，但是使用了一种较为巧妙的方法来代替递归过程，具体过程都注释在代码中了，代码如下：
package test1;
import java.util.Arrays;
public class UnMargeSort {
//划分函数，一定程度上的排序，并排不完，需要递归调用来完成归并排序，相当于把问题分而治之
public static void Merge(int []dsi,int []src,int left ,int m, int right)
{
int i = left, j = m+1;
int k = left;
while(i<=m && j<=right)
{
dsi[k++] = src[i] < src[j]? src[i++]:src[j++];
}
while(i<=m)
{
dsi[k++] = src[i++];
}
while(j<=right)
{
dsi[k++] = src[j++];
}
}
public static void NiceMergePass(int []dis,int []src,int s,int n) // n => index;
{
System.out.printf("s = %d n",s);
int i = 0;
for(i = 0;i+2*s -1 <= n;i = i+2*s)
{ // i <= n -2*s+1
Merge(dis,src,i,i+s-1,i+2*s-1);
System.out.printf("left: %d m: %d right: %d n",i,i+s-1,i+2*s-1);
}
if(n >= i+s)
{
//如果最后一个元素的下标值n>=i+s，那么就是说还有数字没有进行划分
// 我们直接给Merge()函数的参数列表传参改变划分的范围以保证每个元素都被划分
Merge(dis,src,i,i+s-1,n);
System.out.printf("left: %d m: %d right: %d n",i,i+s-1,n);
}
else
{
//如果最后一个元素的下标值n
9.堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
原理
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
- 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
代码
package test1;
import java.util.Arrays;
public class HeapSort {
public static int[] heapSort(int[] array) {
//这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //调整堆
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换,作用是去掉大顶堆
// 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(array, 0, j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(array, 0, j);
}
return array;
}
public static void adjustHeap(int[] array, int i, int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
// 让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子树,并且右子树大于左子树
k++;
}
//如果发现结点(左右子结点)大于根结点，则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
i = k;
} else { //不用交换，直接终止循环
break;
}
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String [] args){
int [] arr = {11,5,8,66,4,2,0,44};
System.out.println("排序前："+Arrays.toString(arr));
heapSort(arr);
System.out.println("排序后："+Arrays.toString(arr));
}
}
结果
排序前：[11, 5, 8, 66, 4, 2, 0, 44]
排序后：[0, 2, 4, 5, 8, 11, 44, 66]
10.基数排序
基数排序属于分配式排序，又称桶子法（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法
实例
第一步
以LSD为例，假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
实现方法
最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
package test1;
import java.util.Arrays;
public class RadixSort {
public static void sort(int[] number, int d) //d表示最大的数有多少位
{
int k = 0;
int n = 1;
int m = 1; //控制键值排序依据在哪一位
int[][] temp = new int[10][number.length]; //数组的第一维表示可能的余数0-9
int[] order = new int[10]; //数组order[i]用来表示该位是i的数的个数
while(m <= d)
{
for(int i = 0; i < number.length; i++)
{
int lsd = ((number[i] / n) % 10);
temp[lsd][order[lsd]] = number[i];
order[lsd]++;
}
for(int i = 0; i < 10; i++)
{
if(order[i] != 0)
for(int j = 0; j < order[i]; j++)
{
number[k] = temp[i][j];
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
m++;
}
}
public static void main(String[] args)
{
int[] data = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
System.out.println("排序前："+Arrays.toString(data));
RadixSort.sort(data, 3);
System.out.println("排序后："+Arrays.toString(data));
}
}
结果
排序前：[73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100]
排序后：[14, 22, 28, 33, 39, 43, 55, 65, 73, 81, 93, 100]
11.桶排序
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
代码
package test1;
import java.util.Arrays;
public class BucketSort {
public static void basket(int data[])//data为待排序数组
{
int n=data.length;
int bask[][]=new int[10][n];
int index[]=new int[10];
int max=Integer.MIN_VALUE;
for(int i=0;i(Integer.toString(data[i]).length())?max:(Integer.toString(data[i]).length());
}
String str;
for(int i=max-1;i>=0;i--){
for(int j=0;j
结果
排序前：[99, 55, 44, 33, 20, 11, 25, 69, 50]
排序后：[11, 20, 25, 33, 44, 50, 55, 69, 99]
求最优连续子序列 使用分治算法
这种比较难以理解，是使用分治的这种思想很多动态规划算法非常像数学中的递推。我们如果能找到一个合适的递推公式，就能很容易的解决问题。
package test1;
public class test{
public static int matrixChain(int[] p, int[][] m, int[][] s) {
int n = p.length - 1;
for (int i = 1; i <= n; i++)
// 本身为0
m[i][i] = 0;
for (int r = 2; r <= n; r++) {
for (int i = 1; i <= n - r + 1; i++) {
int j = i + r - 1;
m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; // 求出Ai到Aj的连乘
s[i][j] = i; // 记录划分位置
for (int k = i + 1; k < j; k++) {// 寻找是否有可优化的分割点
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; // 公式
if (t < m[i][j]) {
m[i][j] = t;
s[i][j] = k;
}
}
}
}
return m[1][n];
}
public static void traceback(int i, int j, int[][] s) {
// 输出A[i:j] 的最优计算次序
if (i == j) {
// 递归出口
System.out.print("A"+i);
return;
} else {
System.out.print("(");
// 递归输出左边
traceback(i, s[i][j], s);
// 递归输出右边
traceback(s[i][j] + 1, j, s);
System.out.print(")");
}
}
public static void main(String[] args) {
int[] p = new int[]{35,15, 5, 10, 20};
int[][] m = new int[p.length][p.length];
int[][] s = new int[p.length][p.length];
System.out.println("最优值为： "+matrixChain(p, m, s));
traceback(1, p.length-1, s);
}
}
结果
最优值为： 7125
((A1A2)(A3A4))
Java实现汉诺塔
package test1;
import java.util.*;
import java.util.Scanner;
public class shop {
//用于记录移动的次数
static int m = 0;
//展示函数
public static void move(int disk, char M, char N) {
System.out.println("第" + (++m) + "次操作，将" +
disk + "号盘从" + M + "移动到" + N);
}
public static void hanoi(int n, char A, char B, char C) {
if(n == 1) {
move(n, A, C);
}else {
hanoi(n - 1, A, C, B);
move(n, A, C);
hanoi(n - 1, B, A, C);
}
}
public static void main(String[] args) {
boolean i=true;
while(i){
Scanner in = new Scanner(System.in);
System.out.println("请您输入hanoi的个数：");
int a = in.nextInt();
hanoi(a, 'A', 'B', 'C');
System.out.println("总共使用" + m + "次");
}
}
}
结果
请您输入hanoi的个数：
3
第1次操作，将1号盘从A移动到C
第2次操作，将2号盘从A移动到B
第3次操作，将1号盘从C移动到B
第4次操作，将3号盘从A移动到C
第5次操作，将1号盘从B移动到A
第6次操作，将2号盘从B移动到C
第7次操作，将1号盘从A移动到C
总共使用7次
请您输入hanoi的个数：
各个算法的数值
排序算法 平均时间复杂度 冒泡排序 O(n²) 冒泡排序 O(n²) 选择排序 O(n²) 插入排序 O(n²) 希尔排序 O(n1.5) 快速排序 O(N*logN) 归并排序 O(N*logN) 堆排序 O(N*logN) 基数排序 O(d(n+r))
其实算法只是在于思想，理解这个算法比背会这个代码要好的多，完整的代码也只是不断的从基本算法的去添完整，防止一些意外的出界行为，重在理解算法。望共勉
附上我的源码，排序算法都在里面 Java算法全套代码 
