算法相关1

海龙2017

浏览: 60580 次
性别:
来自: 上海

最近访客更多访客>>

wangjungen

huxiulei

siemens800

redsnower

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

算法

1.选择排序：不稳定，时间复杂度 O(n^2)
2.插入排序：稳定，时间复杂度 O(n^2)
3.冒泡排序：稳定，时间复杂度 O(n^2)
4.堆排序：不稳定，时间复杂度 O(nlog n)
5.归并排序：稳定，时间复杂度 O(nlog n)
6.快速排序：不稳定，时间复杂度最理想 O(nlogn) 最差时间O(n^2)
7.希尔排序：不稳定，时间复杂度平均时间 O(nlogn) 最差时间O(n^s) 1<s<2

快速排序：
采用递归，第一次以第一位作为中轴，高位放中轴右边（高位与地位置换），低位放中轴左边，再递归左边，递归右边。
https://www.cnblogs.com/0201zcr/p/4763806.html

二分法查找：

package test_yhl.thread;

public class MinAbsTest{
    
	private static int findLocation(int[] testInt, int value) {
		
		int left = 0;
		int right = testInt.length-1;
		
		int LocationValue = 0;
		while(left<= right) {//=
			int middle = (right+left)/2;//+，放在while里面
			if (value < testInt[middle]) {
				right = middle-1;//-1
			}else if(value > testInt[middle]){
				left = middle+1;//+1
			} else{
				LocationValue= middle;
				break;//break;
			}
		}
		return LocationValue;
	}
	
    public static void main(String[] args) throws InterruptedException{  

    	int[] testInt = new int[]{3,10,29,43,48,74,86,300};//new int[]{}
    	System.out.println(findLocation(testInt,300));		
    }
}

插入排序：
http://blog.csdn.net/booirror/article/details/45339387
两层循环，第一层顺序循环，第二层在未排序序列从后向前比较置换值，直到未排序序列最后值置替换为此次值。
插入排序原理：它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序核心：假设第一个元素排好，之后的元素对排好的部分从后向前比较并逐一移动。

package test_yhl.thread;

import java.util.Arrays;

public class MinAbsTest{
    
	public static void main(String[] arg) {
		int[] testInts = new int[]{6,7,112,7,12,34};
		
		int y = 0;// y在for外
		for (int x=0; x<testInts.length; x++) {
			int tem = testInts[x]; //必须定义临时testInts[x]
			for (y=x; y>0 && tem < testInts[y-1]; y--) {
				testInts[y] = testInts[y-1];//[y] [y-1]
			}
			testInts[y] = tem;// [y]
		}
		
		System.out.println(Arrays.toString(testInts));
	}
}

　8 2 4 9 3 6 首先我们考虑数字2，假设后面的数字不存在（手中只有一张8，又抓来了2），那么显然2应该放在8的前面。

　　2 8 4 9 3 6 又抓来了一张4，现在大家都知道应该怎么办了吧？

　　2 4 8 9 3 6 又来了个9，没错，正好不用换顺序

　　2 4 8 9 3 6 同样的道理，考虑3该放的位置，显然放在2和4的中间

　　2 3 4 8 9 6 最后一个也是一样，最后得到从小到大的序列

　　2 3 4 6 8 9 完成排序

选择排序：
从左到右边一个一个区比较，左边已排序越来越多，右边未排序越来越少

package test_yhl.thread;

import java.util.Arrays;

public class MinAbsTest{
    static int z;
	public static void main(String[] arg) {
		int[] a = new int[]{16,7,338,12,34,112};

		int n=a.length;
		int i,j,k;
		for(i=0; i<n; i++){
			k=i;
			for(j=i+1; j<n;j++){
				if(a[k] > a[j]){// [k] [j]
					k=j;
				}
			}
			if(a[k]!=a[i]) {
				int tem = a[i];
				a[i] = a[k];
				a[k] = tem;
			}
		}

		System.out.printf(Arrays.toString(a));
	}
}

冒泡排序：
原理：比较两个相邻的元素，将值大的元素交换至右端。

package test_yhl.thread;

import java.util.Arrays;

public class MinAbsTest{
    static int z;
	public static void main(String[] arg) {
		int[] a = new int[]{-13,-32,-8,5512,6,34,7,338,112};

		int i,j;
		for(i =0;i<a.length-1;i++) {
			for(j=0; j<a.length-1-i; j++) { // -1-i
				
				if(a[j]>a[j+1]) {
//如果是绝对值排序 if(Math.abs(a[j])>Math.abs(a[j+1])) {
// Math.pow(b,2);表示b的平方
					int tem = a[j];
					a[j] = a[j+1];
					a[j+1] = tem;
				}
			}
		}
		
		System.out.println(Arrays.toString(a));
	}
}

归并排序：
https://www.cnblogs.com/chengxiao/p/6194356.html

package org.xdemo.example.SpringActivemq.service.consumer;

import java.util.Arrays;

public class ConsumerTest {

	public static void main(String[] args) throws Exception {
        int []arr = {9,8,7,6,5,4,3,2,1};
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
// 第一个子组合式，left到mid；第二个子组合是mid+1到right。
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){ // <=
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中 <=
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中<=
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){ //<=
            arr[left++] = temp[t++];
        }
    } 
}

堆排序：
https://www.cnblogs.com/jingmoxukong/p/4303826.html
https://www.cnblogs.com/chengxiao/p/6129630.html

股票最佳买入时机：

        
        int aa[] = {1,8,6,3,5,9,11,10,6};
        int min = aa[0];
        int max = 0; // 最大收益
        for (int i =0; i<aa.length; i++) {
            if(aa[i] < min) {
                min = aa[i];
            }
            if(aa[i] - min > max) {
                max = aa[i] - min ;
            }
        }
        System.out.println(max);
//10

二叉树层次遍历：借助队列Queue

VacantCountVo vacantCountVo2 = new VacantCountVo();
        vacantCountVo2.setValue(9);
        VacantCountVo vacantCountVo3 = new VacantCountVo();
        vacantCountVo3.setValue(20);

        VacantCountVo vacantCountVo1 = new VacantCountVo();
        vacantCountVo1.setValue(3);
        vacantCountVo1.setLeft(vacantCountVo2);
        vacantCountVo1.setRight(vacantCountVo3);

        Queue<VacantCountVo> queue = new LinkedList<>();
        queue.add(vacantCountVo1);

        List<List<Integer>> listList = new ArrayList<>();

        while (!queue.isEmpty()) {

            List<Integer> list = new ArrayList<>();
            int count = queue.size();
            while(count > 0) {
                VacantCountVo vacantCountVo4 = queue.poll();
                if (vacantCountVo4.getLeft() != null) {
                    queue.add(vacantCountVo4.getLeft());
                }
                if (vacantCountVo4.getRight() != null) {
                    queue.add(vacantCountVo4.getRight());
                }
                list.add(vacantCountVo4.getValue());
                count --;
            }

            listList.add(list);
        }

        System.out.println(JSON.toJSONString(listList));
// [[3],[9,20]]

二个数组怎样找出公共部分,两个数组的交集

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
         int c[] = null;
         for(int i = 0;i<nums1.length;i++) {
             for(int j=0; j<nums2.length;j++){
                 if(nums1[i] == nums2[j]) {
                     set.add(nums1[i]);
                 }
             }
         }
        Iterator<Integer> iterator = set.iterator();
        int []a = new int[set.size()];
        int z = 0;
        while (iterator.hasNext()){
            a[z++] = iterator.next();
        }
        return a;
    }
}

class Solution {
    public int[] intersection(int[] arrayA, int[] arrayB) {

        Set<Integer> intersectionSet = new HashSet();
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);

        int indexArrayA = 0;
        int indexArrayB = 0;
        int sizeArrayA = arrayA.length;
        int sizeArrayB = arrayB.length;
        while (indexArrayA < sizeArrayA) {
            for (int i = indexArrayB; i < sizeArrayB; i++) {
                if (arrayA[indexArrayA] == arrayB[i]) {
                    intersectionSet.add(arrayA[indexArrayA]);
                    indexArrayA++;
                    indexArrayB++;
                    break;
                } else if (arrayA[indexArrayA] < arrayB[i]) {
                    indexArrayA++;
                    break;
                } else if (i == sizeArrayB - 1) {
                    indexArrayA++;
                }
            }
        }
        
        Iterator<Integer> iterator = intersectionSet.iterator();
        int []a = new int[intersectionSet.size()];
        int i = 0;
        while (iterator.hasNext()){
            a[i++] = iterator.next();
        }

        return a;
    }
}