java几种常见的算法_java项目中用到的算法

一、排序算法

冒泡排序：比较所有相邻元素,如果第一个比第二个大，则交换它们。
选择排序：找到数组中的最小值，选中它并将其放置在第一位。
插入排序：从第二个数开始往前比，比它大就往后排。
归并排序：把数组劈成两半，再递归地对数组进行“分”操作，直到分成一个个单独的数。
快速排序：从数组中任意选择一个基准，所有比基准小的元素放到基准前面，比基准大的元素放到基准的后面

1、插入排序

//插入
    public static void insertSort(int[] a){
        int len=a.length;//单独把数组长度拿出来，提高效率
        int insertNum;//要插入的数
        for (int i = 1; i <len ; i++) {//因为第一次不用，所以从1开始
            insertNum=a[i];
            int j=i-1;//序列元素个数
            while (j>=0&&a[j]>=insertNum){//从后往前循环，将大于insertNum的数向后移动
                a[j+1]=a[j];
                j--;
            }
            a[j+1]=insertNum;//找到位置，插入当前元素
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2、冒泡排序

//冒泡
    //设置循环次数。
    //设置开始比较的位数，和结束的位数。
    //两两比较，将最小的放到前面去。
    //重复2、3步，直到循环次数完毕。
    public static void MPSort(int[] a){
        for (int i = 0; i < a.length-1 ; i++) {
            for (int j = 0; j <a.length-1-i ; j++) {
                if (a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3、选择排序

//选择
    //首先确定循环次数，并且记住当前数字和当前位置。
    //将当前位置后面所有的数与当前数字进行对比，小数赋值给key，并记住小数的位置。
    //比对完成后，将最小的值与第一个数的值交换。
    public static void selectSort(int[] a){
        int len=a.length;
        for (int i = 0; i <len ; i++) {
            int value=a[i];
            int position=i;
            for (int j = i+1; j <len ; j++) {//找到最小的值和位置
                if (a[j]<value){
                    value=a[j];
                    position=j;
                }
            }
            a[position]=a[i];//进行交换
            a[i]=value;

        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二、查找算法

1、二分查找

//二分查找
    //对于二分查找算法要求, 查找前的数据必须是已经排好序的,
    //得到数组的开始位置start和结束位置end, 取中间位置mid的数据a[mid]跟待查找数据key进行比较
    public static int binarySerch(int[] a,int key){
        int start=0;
        int end=a.length-1;
        int mid=-1;
        while (start<=end){
            mid=(end+start)/2;
            if (a[mid]==key){
                return mid;//找到
            }else if (a[mid]>key){
                end=mid-1;
            }else if (a[mid]<key){
                start=mid+1;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19