Java 算法集合
算法分类
算法是一门古老且庞大的学科，随着历史的发展，演化出多种多样的算法。按照不同的应用和特性，算法可以分为不同的类别。
1、按照应用来分类
按照算法的应用领域，即解决的问题，算法可以分为基本算法、数据结构相关的算法、几何算法、图论算法、规划算法、数值算法、数值分析算法、加密/解密算法、排序算法、查找算法、并行算法和数论算法等。
2、按照确定性来分类
按照算法结果的确定性来分类，算法可以分为确定性算法和非确定性算法。
- 确定性算法：这类算法在有限的时间内完成计算，得到的结果是唯一的，且经常取决于输入值。
- 非确定性算法：这类算法在有限的时间内完成计算，单是得到的结果往往不是唯一的，即存在多值性。
3、按照算法的思路来分类
按照算法的思路来分类，算法可以分为递推算法、递归算法、穷举算法、贪婪算法、分治算法、动态规划算法和迭代算法等多种算法。
1.排列组合
数字1，2 有组合【1】【2】【1，2】
数字1，2，3 有组合【1】【2】【3】【1,2】，【1，3】，【2，3】，【1，2，3】
有没有算法在给出一组数字的时候，做出以上排列组合
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Combination {
public static void combiantion(String chs[]){
if(chs==null||chs.length==0){
return ;
}
List<String> list=new ArrayList<String>();
for(int i=1;i<=chs.length;i++){
combine(chs,0,i,list);
}
}
//从字符数组中第begin个字符开始挑选number个字符加入st中
public static void combine(String []cs,int begin,int number,List<String> list){
if(number==0){
System.out.println(list.toString());
return ;
}
if(begin==cs.length){
return;
}
list.add(cs[begin]);
combine(cs,begin+1,number-1,list);
list.remove((String)cs[begin]);
combine(cs,begin+1,number,list);
}
public static void main(String args[]){
System.out.println("请输入一个整型数，以获取从1到这个数的所有组合。");
Scanner input= new Scanner(System.in);
int n = input.nextInt();
List<String> list=new ArrayList<String>();
for (int i=1; i<n+1;i++)
list.add(Integer.toString(i));
Object obj[]=list.toArray();
String s[]=new String[obj.length];
for (int i=0;i<s.length;i++)
s[i]=obj[i].toString();
combiantion(s);
}
}
请输入一个整型数，以获取从1到这个数的所有组合。
5
[1]
[2]
[3]
[4]
[5]
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 4, 5]
[1, 3, 4, 5]
[2, 3, 4, 5]
[1, 2, 3, 4, 5]
Press any key to continue...
2.排序算法
1.冒泡排序
长度为i的数组元素两两比较，不符合顺序，就交换两个元素的位置：
/**
* 冒泡排序
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[]{1, 4, 10, 5, 3, 2, 19, 23, 11};
sort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 升序
* @param arr
*/
private static void sort(int[] arr){
int temp;
for(int i=0; i<arr.length; i++){
for(int j=0; j<i; j++){
if(arr[i] < arr[j]){
temp = arr[i];
arr[i] =arr[j];
arr[j] = temp;
}
}
}
}
}
/**
* 冒泡排序
* @param source 待排序数组
* @param desc 是否降序
* @return
*/
public static void bubleSort( int[] source ,boolean desc){
int temp = 0 ;
if(desc ){
for(int i = source. length - 1 ;i > 0; i--){
for(int j = 0; j < i; j++){
if(source [j ] < source[ j + 1]){
temp = source[j ];
source[j ] = source [j + 1 ];
source[j + 1 ] = temp ;
}
}
}
} else{
for(int i = source. length - 1 ;i > 0; i--){
for(int j = 0; j < i; j++){
if(source [j ] > source[ j + 1]){
temp = source[j ];
source[j ] = source [j + 1 ];
source[j + 1 ] = temp ;
}
}
}
}
}
/**
* 冒泡排序的泛型实现
* @param source
* @param desc
*/
public static <T extends Comparable <? super T>> void bubleSort(T [] source,boolean desc){
T temp = null;
if(desc ){
for(int i = source. length - 1 ;i > 0; i--){
for(int j = 0; j < i; j++){
if(source [j ].compareTo (source [j + 1]) < 0 ){
temp = source[j ];
source[j ] = source [j + 1 ];
source[j + 1 ] = temp ;
}
}
}
} else{
for(int i = source. length - 1 ;i > 0; i--){
for(int j = 0; j < i; j++){
if(source [j ].compareTo (source [j + 1]) > 0 ){
temp = source[j ];
source[j ] = source [j + 1 ];
source[j + 1 ] = temp ;
}
}
}
}
}
2 快速排序
- 令索引 i从数列左方往右方查找，知道找到小于base的数
- 令索引 j从数列右方往左方查找，知道找到大于base的数
- 如果i<=j则交换i和j两处的值，如果i>j离开循环
- 如果start<j，对基数左边轴递归
- 如果end>i，对基数右边轴递归
package com.cary.serial;
import java.util.ArrayList;
import java.util.Arrays;
/**
* 快速排序
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{1, 4, 10, 5, 3, 2, 19, 23, 11};
sort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
* 升序
* @param arr
*/
private static void sort(int[] arr, int start, int end){
if(start < end){
int base = arr[start];//以第一个元素为基准
int i = start;
int j = end;
int temp;
do{
while(arr[i]<base && i<end)
i++;
while(arr[j]>base && j>start)
j--;
if(i <= j){
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
j--;
}
}while (i <= j);
if(start < j){
sort(arr, start, j);
}
if(i < end){
sort(arr, i, end);
}
}
}
}
/**
* 快速排序的泛型实现
* @param source
* @param begin
* @param end
* @param desc
*/
public static <T extends Comparable <? super T>>
void quickSort(T [] source ,int begin, int end ,boolean desc){
int low = begin ;
int high = end ;
T middle = source [low ];//中轴数
if(desc ){
while(low < high){
//从后向前比较，如果发现比middle大的数，则放入low位置
while(low < high && source[high ].compareTo (middle ) <= 0){
high--;
}
//刚开始的时候source[low]放在middle中，low位置相当于空位，
//后面的循环source[low]被放在high位置,low同样相当于空位
if(low < high){
source[low ] = source [high ];
}
//从前向后比较，如果发现比middle小的数，则放入high位置
while(low < high && source[low ].compareTo (middle ) >= 0){
low++;
}
//source[high]已经被放入low位置,high相当于空位
if(low < high){
source[high ] = source [low ];
}
}
} else{
while(low < high){
//从后向前比较，如果发现比middle小的数，则放入low位置
while(low < high && source[high ].compareTo (middle ) >= 0){
high--;
}
//刚开始的时候source[low]放在middle中，low位置相当于空位，
//后面的循环source[low]被放在high位置,low同样相当于空位
if(low < high){
source[low ] = source [high ];
}
//从前向后比较，如果发现比middle大的数，则放入high位置
while(low < high && source[low ].compareTo (middle ) <= 0){
low++;
}
//source[high]已经被放入low位置,high相当于空位
if(low < high){
source[high ] = source [low ];
}
}
}
//循环完成之后low=high，再将中轴数middle放入
if(low == high ){
source[low ] = middle ;
}
if(low > begin){
quickSort(source ,begin ,low - 1 ,desc );
}
if(high < end){
quickSort(source , high + 1 ,end ,desc );
}
}
3.选择排序
- 每次循环都遍历出数组中最小元素，记录索引值
- 通过索引值，将最小元素放到数组的最左边
- 对剩余未排序的元素数组再执行上述两个步骤
package com.cary.serial;
import java.util.Arrays;
/**
* 选择排序
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = new int[]{1, 4, 10, 5, 3, 2, 19, 23, 11};
sort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 升序
* @param arr
*/
private static void sort(int[] arr){
for(int i=0; i<arr.length; i++){
int min = i;
for(int j=i+1; j<arr.length; j++){
if(arr[j] < arr[min]){
min = j;
}
}
if(min != i){
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
}
/**
* 选择排序的泛型实现
* @param source
* @param desc
*/
public static <T extends Comparable <? super T>> void selectionSort(T [] source ,boolean desc){
int minPos = 0 ;//记录最小值的索引
int maxPos = 0 ;//记录最大值的索引
T temp = null;
if(desc ){
for(int i = 0; i < source.length -1 ;i ++){
maxPos = i ;
for(int j = i; j < source.length ;j ++){
if(source [j ].compareTo (source [maxPos ]) > 0){
maxPos = j ;
}
}
if(maxPos != i ){
temp = source[i ];
source[i ] = source [maxPos ];
source[maxPos ] = temp ;
}
}
} else{
for(int i = 0; i < source.length -1 ;i ++){
minPos = i ;
for(int j = i; j < source.length ;j ++){
if(source [j ].compareTo (source [minPos ]) < 0){
minPos = j ;
}
}
if(minPos != i ){
temp = source[i ];
source[i ] = source [minPos ];
source[minPos ] = temp ;
}
}
}
}
4.插入排序
/**
* 插入排序
*
* 从第一个元素开始，该元素可以认为已经被排序
* 取出下一个元素，在已经排序的元素序列中从后向前扫描
* 如果该元素（已排序）大于新元素，将该元素移到下一位置
* 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
* 将新元素插入到该位置中
* 重复步骤2
* @param numbers 待排序数组
*/
public static void insertSort(int[] numbers)
{
int size = numbers.length;
int temp = 0 ;
int j = 0;
for(int i = 0 ; i < size ; i++)
{
temp = numbers[i];
//假如temp比前面的值小，则将前面的值后移
for(j = i ; j > 0 && temp < numbers[j-1] ; j --)
{
numbers[j] = numbers[j-1];
}
numbers[j] = temp;
}
}
/**
* 插入排序的泛型实现
* @param source
* @param desc
*/
public static <T extends Comparable <? super T>> void insertionSort(T [] source ,boolean desc){
T temp = null;
if(desc ){
for(int i = 1; i < source.length ;i ++){
temp = source[i ];
int j = i - 1 ;
while(j >= 0 && source[j ].compareTo (temp ) < 0){
source[j + 1 ] = source [j ];
j--;
}
if(j != (i - 1)){
source[j + 1 ] = temp ;
}
}
} else{
for(int i = 1; i < source.length ;i ++){
temp = source[i ];
int j = i - 1 ;
while(j >= 0 && source[j ].compareTo (temp ) > 0){
source[j + 1 ] = source [j ];
j--;
}
if(j != (i - 1)){
source[j + 1 ] = temp ;
}
}
}
}
3.查找算法
1.二分非递归查找
算法思想：又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。
package com.cary.serial;
import java.util.Arrays;
/**
* 二分查找
*/
public class BinarySearch {
public static void main(String[] args) {
int[] arr = new int[]{1, 3, 11, 15, 17, 18, 19, 23, 29};
System.out.println(search(arr, 15));
}
private static int search(int[] arr, int number){
int start = 0;
int end = arr.length-1;
while(start<=end){
int middle = (start+end)/2;
if(number==arr[middle]){
return middle+1;
} else if(number < arr[middle]){
end = middle-1;
} else {
start = middle+1;
}
}
return -1;
}
}
2.二分递归查找
package com.cary.serial;
import java.util.Arrays;
/**
* 二分查找
*/
public class BinarySearch {
public static void main(String[] args) {
int[] arr = new int[]{1, 3, 11, 15, 17, 18, 19, 23, 29};
System.out.println(search(arr, 0, arr.length-1, 15));
}
private static int search(int[] arr,int start, int end, int number){
if(start <= end){
int middle = (start+end)/2;
if(number == arr[middle]){
return middle+1;
} else if(number<arr[middle]){
return search(arr, start, middle-1, number);
} else {
return search(arr, middle+1, end, number);
}
}
return -1;
}
}