目 录CONTENT

文章目录

经典算法(排序、查找)

Josue
2022-03-30 / 0 评论 / 0 点赞 / 107 阅读 / 3,549 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-30,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

一、算法时间复杂度

1.1、衡量一个程序(算法)执行时间的两种方法

  • 事后统计。程序必须执行。需要再同一计算机的相同状态下运行,才能比较哪个算法速度更快
  • 事前估算。通过分析某个算法的时间复杂的来判断

1.2、时间频度(Tn)

一个算法花费的时间与算法重语句的执行次数成正比,执行语句越多,花费时间越多。

二、排序算法

2.1、冒泡 排序

基本思想:通过对待排序序列从前往后(下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,像水底的气泡一样逐渐往上冒。时间复杂程度为O(n^2)

public static void encapsulationBubbleSort(int[] arr){
        int temp = 0;
     boolean flag = false;
        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]){
                    temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
             if (!flag){
                break;
            }else {
                flag = false;
            }
            System.out.println("这是第"+i+"次排序");
            System.out.println(Arrays.toString(arr));
            System.out.println("-----------------------");
        }
    }

2.2、选择排序

基本思想:每轮排序选出最小值,一次排序

 public static void sort(int[] arr){
        for (int i = 0; i < arr.length; i++) {

            int minIndex = i;
            int min = arr[i];

            for (int j = i+1; j < arr.length ; j++) {

                if (arr[minIndex] > arr[j]){

                    minIndex = j;   //重置minIndex
                    min = arr[j];   //重置min
                }
            }

            arr[minIndex] = arr[i]; //交换最小值坐标
            arr[i] = min;

        }

    }

2.3、插入排序

思想:将一组数据分成两组,分别将其称为有序组待插入组。每次从待插入组中取出一个元素,与有序组的元素进行比较,并找到合适的位置,将该元素插到有序组当中。

public static  void InsertSort(int[] arr){

        // arr[] = {1, 8, 6, -3, 2};
        for (int i = 1; i < arr.length ; i++) {

            int insertVal = arr[i];
            int insertIndex = i - 1;

            while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            
            arr[insertIndex+1] = insertVal;
        }
        
    }

2.4、希尔排序

思想:进行分组交换,例如

10个数分为(10/2)5组,大小对比交换;再分为(5/2)2组,大小对比交换;

public static void shellSortMove(int[] arr){

        for (int gap = arr.length/2; gap >0 ; gap/=2) {
           
            for (int i = gap; i < arr.length ; i++) {   
                
                int j = i;
                int temp = arr[j];
                if (arr[j] <arr[j - gap]){
                    while (j-gap >=0 &&temp <arr[j-gap]){
                        arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }

2.5、快速排序

思路:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

 public static void quickSort2(int[] arr, int left, int right){

        if (left >= right)return;
        int l = left;
        int r = right;
        int pivot = arr[left];

        while (l < r){
            while (l < r && arr[r] >=pivot){
                r--;
            }
            if (l < r){
                arr[l] = arr[r];
            }
            while (l < r && arr[l] <=pivot){
                l++;
            }
            if (l < r){
                arr[r] = arr[l];
            }
            if (l >=r){
                arr[l] = pivot;
            }
        }

        System.out.println(Arrays.toString(arr));
        quickSort2(arr,left,r-1);
        quickSort2(arr,r+1,right);

    }

2.6、归并排序

思路:将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。类似二叉树

public static int[] mergeSort(int[] nums, int l, int h) {
        if (l == h)
            return new int[] { nums[l] };
         
        int mid = l + (h - l) / 2;
        int[] leftArr = mergeSort(nums, l, mid); //左有序数组
        int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
        int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
         
        int m = 0, i = 0, j = 0; 
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length)
            newNum[m++] = leftArr[i++];
        while (j < rightArr.length)
            newNum[m++] = rightArr[j++];
        return newNum;
    }
    public static void main(String[] args) {
        int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
        int[] newNums = mergeSort(nums, 0, nums.length - 1);
        for (int x : newNums) {
            System.out.println(x);
        }
    }

2.7、基数排序

思路:基数排序(桶子法)。通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用。空间换时间,数据过大会导致内存溢出。

负数不建议使用基数。

三、查找算法

3.1、二分查找

二分算法需保证算法是有序的。

思路:每次从中间开始对比,依次折中。

public static ArrayList binarySearch(int[] arr,int low,int top,int value){
        ArrayList<Integer> resIndex = new ArrayList<>();
        while (low < top ){
            int mid = (low+top)/2;
            if (value<arr[mid]){
               top = mid;
            }
            else if (value > arr[mid]){
               low = mid;
            }
            else if (value == arr[mid]){

//                return mid;
               int temp =  mid-1;
               while (true){
                   if (temp<0||arr[temp]!=value){
                       break;
                   }
                   resIndex.add(temp);
                   temp--;
               }
                resIndex.add(mid);
              int temp2 = mid+1;
               while (true){
                   if (temp2>arr.length||arr[temp2]!=value){
                       break;
                   }
                   resIndex.add(temp2);
                   temp2++;
               }

               return resIndex;
            }

            if (top-low == 1){
                return null;
            }

        }
        return null;
    }

3.2、插值查找法(查找算法)

公式:int mid = left +(right-left)*(findVal-arr[left])/(arr[right]-arr[left])

特地:需要数据有序且均匀分布

0

评论区