JAVA算法介绍（二）

?6?归并排序算法

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列

分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

public class MergeSortTest {

public static void main(String[] args) {

int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };

print(data);

mergeSort(data);

System.out.println("排序后的数组：");

print(data);

}

public static void mergeSort(int[] data) {

sort(data, 0, data.length - 1);

}

public static void sort(int[] data, int left, int right) {

if (left >= right)

return;

// 找出中间索引

int center = (left + right) / 2;

// 对左边数组进行递归

sort(data, left, center);

// 对右边数组进行递归

sort(data, center + 1, right);

// 合并

merge(data, left, center, right);

print(data);

}

/**

* 将两个数组进行归并，归并前面 2 个数组已有序，归并后依然有序

*

* @param data

* 数组对象

* @param left

* 左数组的第一个元素的索引

* @param center

* 左数组的最后一个元素的索引，center+1 是右数组第一个元素的索引

* @param right

* 右数组最后一个元素的索引

*/

public static void merge(int[] data, int left, int center, int right) {

// 临时数组

int[] tmpArr = new int[data.length];

// 右数组第一个元素索引

int mid = center + 1;

// third 记录临时数组的索引

int third = left;

// 缓存左数组第一个元素的索引

int tmp = left;

while (left <= center && mid <= right) {

// 从两个数组中取出最小的放入临时数组

if (data[left] <= data[mid]) {

tmpArr[third++] = data[left++];

} else {

tmpArr[third++] = data[mid++];

}

}

// 剩余部分依次放入临时数组（实际上两个 while 只会执行其中一个）

while (mid <= right) {

tmpArr[third++] = data[mid++];

}

while (left <= center) {

tmpArr[third++] = data[left++];

}

// 将临时数组中的内容拷贝回原数组中

// （原 left-right 范围的内容被复制回原数组）

while (tmp <= right) {

data[tmp] = tmpArr[tmp++];

}

}

public static void print(int[] data) {

for (int i = 0; i < data.length; i++) {

System.out.print(data[i] + "\t");

}

System.out.println();

}

}

7?桶排序算法

?

public static void bucketSort(int[] arr){

int max = Integer.MIN_VALUE;

int min = Integer.MAX_VALUE;

for(int i = 0; i < arr.length; i++){

max = Math.max(max, arr[i]);

min = Math.min(min, arr[i]);

}

//创建桶

int bucketNum = (max - min) / arr.length + 1;

ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);

for(int i = 0; i < bucketNum; i++){

bucketArr.add(new ArrayList<Integer>());

}

//将每个元素放入桶

for(int i = 0; i < arr.length; i++){

int num = (arr[i] - min) / (arr.length);

bucketArr.get(num).add(arr[i]);

}

//对每个桶进行排序

for(int i = 0; i < bucketArr.size(); i++){

Collections.sort(bucketArr.get(i));

}

}

8?基数排序算法?

?

public class radixSort {

inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,2

5,53,51};

public radixSort(){

sort(a);

for(inti=0;i<a.length;i++){

System.out.println(a[i]);

}

}

public void sort(int[] array){

//首先确定排序的趟数;

int max=array[0];

for(inti=1;i<array.length;i++){

if(array[i]>max){

max=array[i];

}

}

int time=0;

//判断位数;

while(max>0){

max/=10;

time++;

}

//建立 10 个队列;

List<ArrayList> queue=newArrayList<ArrayList>();

for(int i=0;i<10;i++){

ArrayList<Integer>queue1=new ArrayList<Integer>();

queue.add(queue1);

}

//进行 time 次分配和收集;

for(int i=0;i<time;i++){

//分配数组元素;

for(intj=0;j<array.length;j++){

//得到数字的第 time+1 位数;

int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);

ArrayList<Integer>queue2=queue.get(x);

queue2.add(array[j]);

queue.set(x, queue2);

}

int count=0;//元素计数器;

//收集队列元素;

for(int k=0;k<10;k++){

while(queue.get(k).size()>0){

ArrayList<Integer>queue3=queue.get(k);

array[count]=queue3.get(0);

queue3.remove(0);

count++;

}

}

}

}

}

9?剪枝算法

?

10?回溯算法

11?最短路径算法

从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最

短路径。解决最短路的问题有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA

算法等。

12? 最小生成树算法

现在假设有一个很实际的问题：我们要在 n 个城市中建立一个通信网络，则连通这 n 个城市需要

布置 n-1 一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？

于是我们就可以引入连通图来解决我们遇到的问题，n 个城市就是图上的 n 个顶点，然后，边表示

两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有 n 个

顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连

通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。

构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST 性质（假设

N=(V,{E})是一个连通网，U 是顶点集 V 的一个非空子集，如果（u，v）是一条具有最小权值的边， 其中 u 属于 U，v 属于 V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍两种使 用 MST 性质生成最小生成树的算法：普里姆算法和克鲁斯卡尔算法。

?