Java一些常见算法集合
排序
//示例1
public void tests() {
int[] numbers = { 3, 2, 20, 54, 10, 5, 78, 1, 100 };
int tmep = 0;
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers.length - i - 1; j++)
if (numbers[j] > numbers[j + 1]) {
tmep = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = tmep;
}
}
for (int n = 0; n < numbers.length; n++) {
System.out.print(numbers[n] + ",");
}
System.out.println("===============");
for (int m = numbers.length - 1; m >= 0; m--) {
System.out.print(numbers[m] + ";");
}
System.out.println("list结果：===============");
List<Integer> list = new ArrayList<Integer>();
for (int a = 0; a < numbers.length; a++) {
list.add(numbers[a]);
}
Collections.sort(list);
for (Integer str : list) {
System.out.print(str + ";");
}
}
//示例2
public static void main(String[] arg){
Comparable []num={4,9,12,3,2,45,89};
insertionSort(num);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+",");
}
}
public static void insertionSort(Comparable []data){
for(int index=1;index<data.length;index++){
Comparable key =data[index];
int position=index;
while(position>0 && data[position-1].compareTo(key)>0){
data[position]=data[position-1];
position--;
}
data[position]=key;
}
}
####素数
public void testNum() {
for (int m = 2; m < 100; m++) {
int n;
for (n = 2; n <= (int) (Math.sqrt(m)); n++) {
if (m % n == 0) {
break;
}
}
if (n > (int) (Math.sqrt(m))) {
System.out.print(m + ";");
}
}
System.out.println("==============");
for (int i = 2; i < 100; i++) {
int j;
for (j = 2; j <= i / 2; j++) {
if (i % j == 0) {
break;
}
}
if (j > i / 2) {
System.out.print(i + ";");
}
}
}
一个N个整数的无序数组，给你一个数sum，求出数组中是否存在两个数，使它们的和等于sum
/**
* 一个N个整数的无序数组，给你一个数sum，求出数组中是否存在两个数，使他们的和为sum
* 解决思路：hash表,复杂度O(n)
* @param numbers
*/
public static void init(int[] numbers){
Map<Integer,Integer> maps=new HashMap<Integer, Integer>();
int sum=60;
int key=0;
for(int i=0;i<numbers.length;i++){
key=sum-numbers[i];
maps.put(numbers[i],numbers[i]);
if(maps.containsKey(key)){
System.out.println(key+":"+numbers[i]);
}
}
}
给一组数，其中只有一个数是重复了奇数次，其余都重复了偶数次，如何找出奇数次的那个数
/**
* 给一组数，其中只有一个数是重复了奇数次，其余都重复了偶数次，如何找出奇数次的那个数
* 解决思路：异或运算，复杂度O(n)
* @param nums
*/
public static void method1(int[] nums){
int x=nums[0];
for(int i=1;i<nums.length;i++){
x=x ^ nums[i];
}
System.out.println(x);
}
快速排序
/**
* 快速排序
* @param num
* @param left
* @param right
* @return
*/
public static int middleSort(int[] num,int left,int right){
//作为中间轴数
int temp=num[left];
while (left<right){
//从右到左，找到第一个比中间轴数小得，移动到左端
while (left<right && num[right]>temp){
right--;
}
num[left]=num[right];
//从左到右，找到第一个比中间轴数大得，移到右端
while (left<right && num[left] < temp){
left++;
}
num[right]=num[left];
}
//将中轴数赋值
num[left]=temp;
return left;
}
//快速排序开始
public static void sort(int[] num,int left,int right){
if(left<right){
//根据左右索引相同才停止，不同的话，按着分治思想找到中间轴数，一分为二，以此类推
int middle=middleSort(num,left,right);
sort(num,left,middle-1);
sort(num,middle+1,right);
}
}
Hash算法
哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值，哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所存储的位置称为哈希地址或散列地址（哈希(hash)算法，即散列函数，它是一种单向密码体制，即它是一个从明文到密文的不可逆的映射，只有加密过程，没有解密过程，同时，哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出）
/**
*加法hash
*@param str 字符串
*@param n 一个质数
*@ return hash结果
* 为什么用质数或素数，而不用其他数
* 因为哈希函数是一个对应，任意m值对应到H(m)，并且要满足单向性和抗冲突性
* 抗冲突性其实就是函数里面的单射
* 你想想如果用的是合数而不是素数，往往因为包含因数过多而使得两个不同的数映射成同一个数从而不满足单射的要求
*/
public static int addHash(String str,int n){
int hash,i;
for(hash=str.length(),i=0;i<str.length();i++){
hash +=str.charAt(i);
}
return (hash%n);
}
----EOF-----