java常见算法（持续更新中）_算法 java

下面几种算法是我们在初学阶段比较常见的算法。

冒泡排序

核心思想:每一轮比较,都将剩余元素中最大的值放到剩余位置最末位
核心操作:两两比较,交换值

public static void main(String[] args) {

  int[] arr = {22,13,5,1,77,31,17,55,3};
  for (int i = 0; i < arr.length-1; i++) {
   for (int j = 0; j < arr.length-1-i; j++) {
    //如果遍历到的元素,大于下一个元素,交换值
    if (arr[j] > arr[j+1]){
     int temp = arr[j];
     arr[j] = arr[j+1];
     arr[j+1] = temp;
    }
   }
  }
  
 System.out.println(Arrays.toString( arr ));
  
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二分查找

核心思想: 通过二分查找,逐渐缩小bug查找范围,进而提高bug排查效率。
必须是有顺序的区间范围

public class TestMian{
 public static void main(String[] args) {
 //前提是数组有序
  int[] arr = {1,7,17,28,31,55};
  int binarySearch = binarySearch(arr,100);
  System.out.println("下标是:"+binarySearch);
  
 }
 

 下午传入一个数组和一个int值,查找当前int值在数组中的下标,如果找到下标,则返回,
 如果没有找到,则返回-1 如果有重复的要素,则只会返回第一个出现的元素下标 

 public static int binarySearch(int[] arr,int ele) {
  int minIndex = 0;//最小下标
  int maxIndex = arr.length-1;//最大下标
  int middleIndex = (maxIndex + minIndex)/2;//中间下标
  
  用ele跟每次取得的中间值比较,根据大小关系,继续进行下一次比较,如果大了,
  调整最大取值,如果小了,调整最小取值. 
  直到ele==arr[middleIndex]或者所有数组比较完毕(即,最小下标等于最大下标
  的时候,表示比较完毕了)停止

  while (minIndex <= maxIndex) {
   if (arr[middleIndex] == ele) {
    return middleIndex;
   }else if (arr[middleIndex] > ele) {
    maxIndex = middleIndex - 1;
   }else if (arr[middleIndex] < ele) {
    minIndex = middleIndex + 1;
   }
   middleIndex = (minIndex + maxIndex)/2;
  }
  return -1;//-1只是一种没有找到数组中元素的状态.表示没有找到
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

插入排序

核心思想：我们将一个数组a看一个两个数组,第一个数组b为有序的包含a[0],第二个数组c为剩下的无序数组。遍历数组c 与 数组b做比较，然后根据大小插入数据

public static void main(String[] args) {
    int[] arr= {14,11,5,9,20,2};
    System.out.println("插入排序前：");
    System.out.println(Arrays.toString(arr));
    System.out.println("排序中");
    insertionSort(arr);
    //insertionSort1(arr); 两种均可
    System.out.println("插入排序后：");
    System.out.println(Arrays.toString(arr));

}
public static void insertionSort(int arr[]){
    for (int i = 1; i < arr.length; i++) {//默认第一个元素为有序表，剩下的n-1个元素为无序表
        //插入数据
        int insertVal = arr[i]; //11
        //当i=0时，index=0即表示指向第一个有序表元素
        int index = i-1; 
        //insertVal<arr[index]待插入的数，没有找到插入位置
        while (index >= 0 && insertVal <arr[index], index--){
            // 满足条件，将 arr[index]赋值给arr[index+1] 以达到排序的目的
            arr[index+1] = arr[index];
         
        }
        arr[index+1] = insertVal;//插入的位置找到
        System.out.println(Arrays.toString(arr));//观察排序数组
    }
 public static void insertionSort1(int arr[]){
        for (int i = 1; i < arr.length; i++) {//默认第一个元素为有序表，剩下的n-1个元素为无序表
            //插入数据
            int insertVal = arr[i]; //11
            //当i=0时，index=0即表示指向第一个有序表元素
            int index ;
            //insertVal<arr[index]待插入的数，没有找到插入位置
            for (index = i-1; index >= 0 && insertVal <arr[index]; index--){
                // 满足条件，将 arr[index]赋值给arr[index+1] 以达到排序的目的
                arr[index+1] = arr[index];
            }
            arr[index+1] = insertVal;//插入的位置找到
            System.out.println(Arrays.toString(arr));//观察排序数组
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

希尔排序

核心思想： 关键在于“增量交换”，因此又叫做缩小增量排序。
希尔排序目的为了加快速度改进了插入排序，它是非稳定排序算法，该方法因 D.L.Shell 于 1959 年提出而得名。
步骤：
   交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2…1} 来表示。

public class ShellSort {
   
    public static void main(String[] args) {
        int []arr ={3,2,1,7,8,5,4,6};//无序数组
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
   
    public static void sort(int arr[]) {
        int j;
        // gap = arr.length / 2为第一次增量  4
        for (int gap = arr.length / 2; gap >  0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) { //相当于这里的数组为  {8,5,4,6}
                int  tmp = arr[i]; //
                //这里做插入排序,参考上面 insertionSort1() 方法
                for (j = i; j >= gap && tmp<arr[j - gap]; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

希尔排序

核心思想：从准备排序的数组中按照指定的规则选择某一个元素，然后按照规则进行交换位置。
算法步骤

 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

 3.重复第二步，直到所有元素均排序完毕。

 public static void main(String[] args) {
            int []arr ={3,2,1,7,8,5,4,6};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }

        public static void sort(int  arr[]) {
            //循环需要插入排序的数组
            for (int i = 0; i < arr.length; i++) {
                //当前的下标
                int tmp  = i;
                //最小值  这里我们假设 arr[i]为最小值
                int min = arr[i];
                //j 是除去排好序后的剩下未排序的数组的长度
                for (int j = arr.length-1; j > i; j--) {
                    if (min > arr[j]){
                        tmp = j;
                        min = arr[j];
                    }
                }
                arr[tmp] = arr[i];
                arr[i] = min;
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24