基础算法介绍

╰半夏微凉° 2022-08-30 05:17 127阅读 0赞

1.冒泡排序:

从小到大顺序,通过不断循环,把最大的数字放在最后面,然后下次循环再次对前面几个数字小的排序,反之从大到小排序也一样

public static void main(String[] args) {
            int[] arr = {1,25,2,38,5,20};
            //要循环全部数字才能排序完成
            for (int i = 0; i < arr.length; i++) {
                /**
                1.为什么数组大小-1,因为下面if判断已经进行+1判断了,
                  最后一位后面已经没有数字了,不需要和后面的数字比对大小了.
    
                2.为什么数组大小需要-i,假如第一次循环,已经把整个数组中
                  最大的放在了数组后面,所以第二次循环的时候不需要对比
                  最后一位数字了,因为他已经是数组中最大的了,
                  只需要对比前面几个数字大小把最大的放在倒数第二位就可以了.
    
                  通过这样-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));
        }

2.快排排序:

①选择一个基准数值,通常选择第一个数值或者最后一个数值,通过第一次循环,将待排序数组值分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置.

②上述中,要做到这一步,就需要三个循环条件,首先是数组中最大坐标和最小坐标未相等,如果他们相等了,就代表数组中所有的数值已经循环一遍了,如果基准数值不是最小值,那么相等坐标的右边都是大于基准元素的,左边都是小于基准元素的.如果是最小值,那么他的左边没有值,右边全是比他大的值.

其中两个条件循环,一个是让最大坐标,不断的循环比较,把比基准数值小的值的坐标标记出来,另外一个是让最小坐标,不断的循环比较,把比基准数值小的值的坐标标记出来,然后进行交换坐标位置.

这样的目的就是让小的值往左边走,大的值往右边走

③然后再去同样的方法去对一开始的基准值,左边小于他的数值进行小值排序,右边大于他的数值进行大值排序，直到序列中的所有记录均有序为止。

④总体思想就是分而治之.对数组不断的进行切割排序,从而快速的排出顺序

public static void main(String[] args) {
            int[] arr = {4,1,8,5,3,2,9,10,6,7};
            //要循环全部数字才能排序完成
            TestController.quickShort(arr,0,arr.length-1);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void quickShort(int[] arr,int left,int right){
            if(left > right){
                return;
            }
    
            //初始化索引
            int i = left;
            int j = right;
            //基准数
            int baseNum = arr[left];
            //两个索引不相遇
            while(i != j){
                //注意下面两个判断不能颠倒顺序,因为j最小的时候也要大于或等于i,如果反过来,
                 可能会遗漏数值;
                
                //因为J是数组坐标最大坐标,所以让右边坐标的往左边走,右边的坐标不能小于
                  左边的坐标,数值一直找到小于基准值
                while(j>i && arr[j] >= baseNum){
                    //如果找不到小于基准值的,就继续让右边的J索引下标值一直减少,相当于
                     就是索引往左边走了.
                    j--;
                }
                //因为i是数组坐标最小坐标,所以让左边坐标的往右边走,左边的坐标不能大于
                  右边的坐标,数值一直找到大于基准值
                while(i<j && arr[i] <= baseNum){
                    i++;
                }
                
                //找到后,进行交换顺序,这样左边的大于基准值的就跑到了右边去,
                  右边小于基准值的就跑到左边去了
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
    
            //当i和j相遇后, 把基准数和相遇位置的数交换位置,这样基准值的左边都是比他小的数值,
              右边都是比他大的数值
            arr[left] = arr[i];
            arr[i] = baseNum;
    
            //这一步第一循环打印出来就是[3, 1, 2, 4, 5, 8, 9, 10, 6, 7],4是最初的基准值.
            System.out.println(Arrays.toString(arr));
    
            //然后在原来的基准数的索引处分别对他左边和右边的数值进行递归调用;
            //对左边数值小片段进行递归排序
            quickShort(arr,left,i-1);
    
            //对右边数值大片段进行递归排序
            quickShort(arr,i+1,right);
        }

3.取两个数组中重复数字

用排序加双指针的方法进行快速筛选

public static  int[] intersect(int[] nums1, int[] nums2) {
            //确保nums1是长度小的数组,因为下面要确定重复数组的大小,包括确定指针和数组相匹配
            if(nums1.length>nums2.length){
                return intersect(nums2,nums1);
            }
            //需要对数组排好序,这样数字小的就在前面,数字大的在后面
            Arrays.sort(nums1);
            Arrays.sort(nums2);
    
            int i=0,j=0,k=0;
            int len1=nums1.length,len2=nums2.length;
    
            //建立存放重复数值的数组
            int [] res=new int[len1];
    
            //i是数组长度小的指针,j是数组长度大
            while(i<len1&&j<len2){
                //如果i的数值大于J的数值,代表j所在的数值小,需要j往前加走,在和i进行比较下一个数值
                if(nums1[i]>nums2[j]){
                    j++;
                } else if(nums1[i]<nums2[j]){
                    i++;
                } else{
                    res[k++]=nums1[i];
                    i++;
                    j++;
                }
            }
            //因为重复数组初始化大小是按照最大初始化的,实际重复数值可能没有那么多,需要截取
            return Arrays.copyOfRange(res,0,k);
        }

3.二分查找算法:

在有序数组中找到目标数值的坐标,思想就是先找到数组中间的值,如果目标值比他大,就找数组右边,反之找左边.

private static int searchKey(int[] arr, int target) {
            //前提是数组是有序的
            int left = 0;
            int right = arr.length - 1;
            while (left <= right) {
                //取中间坐标值,左边都是比他小的,右边都是比他大的数值
                int mid = (left + right) / 2;
    
                if (arr[mid] == target) {
                    return mid;
                } else if (arr[mid] > target) {
                    //目标数比中间数小,应该往找左边的
                    right = mid - 1;
                } else {
                    //目标数比中间数大,应该往找右边的
                    left = mid + 1;
                }
            }
            return -1;
        }