每天一个算法

[TOC]

排序

选择排序

先上代码：

/**
* 选择排序
*/
private static void SelectSort(int [] array){
        System.out.println();
        System.out.println("交换前：");
        for(int num:array){
            System.out.print(num+" ");
        }
        for(int i=0;i<array.length;i++){
            int k=i;
            for(int j=k+1;j<array.length;j++){
                if(array[j]<array[k]){
                    k=j;
                }
            }
            if(i!=k){
                int temp=array[i];
                array[i]=array[k];
                array[k]=temp;
            }
        }
        System.out.println();
        System.out.println("交换后：");
        for(int num:array){
            System.out.print(num+" ");
        }
    }

对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换
特点：

• 运行时间和输入无关，具体表现为：一个已经有序的数组或者是主键全部相等的数组和一个元素随机排序的数组所用的排序时间是一样长的。
• 数据移动是最少的，每次交换都会改变两个数组元素的值，因此选择排序用了N次交换----交换次数和数组的大小是线性关系

插入排序

插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序
先上代码：

/**
     * 插入排序
     * @param array
     * @param arraySize
     */
    static void insertionSort(int array[], int arraySize)  
    {  
        int i,j,tmp;  
        for (i = 1; i < arraySize; i++) {  
            tmp = array[i];  
            for (j = i - 1; j >= 0 && array[j] > tmp; j--) {  
                array[j+1] = array[j];  
            }  
            array[j+1] = tmp;  
        }  
        
        for (int k : array) {
            System.out.print(k+"   ");
        }
    }  

对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要_{N^2/4次比较以及}N^2/4此交换。
最坏情况下需要_{N^2/2比较和}N^2/2次交换，最好情况下需要N-1次比较和0次交换。

image.png

package page;

import java.util.HashMap;
import java.util.Map;

public class test1 {
    
    public static void main(String[] args) {
            String target="123xxxdfsdf123";
//          正则--> 去除字母 替换成“-”，按“-”分割--> 变成数组
            String [] numberArr=target.replaceAll("[a-zA-Z]+", "-").split("-");
            Map<String,Integer> map=new HashMap<>();
            for(int i=0;i<numberArr.length;i++){
                if(null==map.get(numberArr[i])){
                    // 说明map中没有这个key
                    map.put(numberArr[i], 1);
                }else{
                    // 说明map中存有这个key，value++;
                    map.put(numberArr[i], map.get(numberArr[i])+1);
                }
            }
            
            getMapMax(map);
    }
    
    
    /**
     * 根据map拿到里面的最大重复值 并且计算
     * @param map
     */
    private static void getMapMax(Map<String,Integer> map){
        int tempMaxCount=0;
        String tempMaxResult=null;
        int result=0;
        for(Map.Entry<String, Integer> entry :map.entrySet()){
            if(tempMaxCount<entry.getValue()){
                tempMaxCount=entry.getValue();
                tempMaxResult=entry.getKey();
            }
        }
        result=tempMaxCount*(Integer.valueOf(tempMaxResult));
        System.out.println("出现次数最多的是"+tempMaxCount+"次,它的值是"+tempMaxResult
                +",所以结果是"+result);
    }
}