java的常见算法

朱雀 2023-10-08 12:20 17阅读 0赞

*  **冒泡排序**

依次比较相邻的两个数，将小的放在前面，大的放在后面。即在第一趟，首先比较第1个数和第2个数，小的放在前面，大的放在后面，然后比较第2个数和第3个数，小的放在前面，大的放在后面，如此继续，直至比较完最后两个数，这样外层循环结束一次，已经将最大的数放在了最后。后面按照这个规律执行外层循环的剩余次数，每次选出最大的，直至结束。

// 冒泡排序    时间复杂度 O(n²)
        public void bubbleSort(int[] arr) {
            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;
                    }
                }
            }
        }

*  **选择排序**

每次从现有数据挑出一个最小的直接放在最前面，第二次再将剩余的数据进行依次比较，拿出最小的放在除前面次数外的最前面，以此类推。（第一次是拿第1个数，依次和后面的数做比较，小的就放在第1个，第2次是拿第2个数，依次和后面的数比较，小的就放在第2个，如此类推，直到结束）

// 选择排序      时间复杂度 O(n²)
        public void selectSort(int[] arr) {
            for (int x = 0; x < arr.length-1; x++) {
                for (int y = x+1; y < arr.length; y++) {
                    if(arr[x]>arr[y]){
                        int temp = arr[y];
                        arr[y] = arr[x];
                        arr[x] = temp;
                    }
                }
            }
        }

*  **插入排序**

将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）

// 插入排序      时间复杂度 O(n²)
        public void insertSort(int[] arr) {
            for (int i = 0; i <arr.length-1 ; i++) {
                for (int j = i+1; j >0 ; j--) {
                    if (arr[j] < arr[j - 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = temp;
                    }
                }
            }
        }

*  **希尔排序**

希尔排序是插入排序的一种高速而稳定的改进版本

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。

// 希尔排序(插入排序的升级版)        时间复杂度不稳定 O(nlogn) -- O(n²)
        public void hillSort(int[] arr) {
            int gap = arr.length / 2;
            //不断缩小gap，直到1为止  (gap为希尔增量)
            for (;gap > 0; gap = gap / 2) {
                for (int j = gap; j < arr.length; j++) {
                    //使用当前gap进行组内插入排序
                    for (int k = j; k >= gap && arr[k] < arr[k - gap]; k -= gap) {
                        int temp = arr[k];
                        arr[k] = arr[k - gap];
                        arr[k - gap] = temp;
                    }
                }
            }
        }

*  **堆排序**

堆排序是选择排序的一种改进

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值，再将末尾切开。然后将剩余n-1个元素重新构造成一个大顶堆，再将根节点与末尾元素交换，这样会得到剩余元素的次大值。如此反复执行，便能得到一个有序序列了。

// 堆排序(选择排序的升级版)     时间复杂度 O(nlogn)
        public void heapSort(int []arr){
            //1.构建大顶堆
            for(int i=arr.length/2-1;i>=0;i--){
                //从第一个非叶子结点从下至上，从右至左调整结构
                adjustHeap(arr,i,arr.length);
            }
            //2.交换堆顶元素与末尾元素 + 调整堆结构
            for(int j=arr.length-1;j>0;j--){
                swap(arr,0,j);
                adjustHeap(arr,0,j);
            }
        }
        public void adjustHeap(int []arr,int i,int length){
            int temp = arr[i];//先取出当前元素i
            for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
                if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                    k++;
                }
                if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                    arr[i] = arr[k];
                    i = k;
                }else{
                    break;
                }
            }
            arr[i] = temp;//将temp值放到最终的位置
        }
        public void swap(int []arr,int a ,int b){
            int temp=arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

*  **归并排序**

归并排序是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列，两个子序列再分别递归调用该排序方法自身，里面分别进行排序，最后再将他们合并成一个子序列，也就是排好序的了。

// 归并排序      时间复杂度 O(nlogn)
        public void mergeSort(int [] arr,int start,int end){
            if(start < end){//当子序列中只有一个元素时结束递归
                int mid = (start + end) / 2;//划分子序列
                mergeSort(arr, start, mid);//对左侧子序列进行递归排序
                mergeSort(arr, mid + 1, end);//对右侧子序列进行递归排序
                merge(arr, start, mid, end);//合并
            }
        }
        public void merge(int []a,int left,int mid,int right){
            int []tmp = new int[a.length];//辅助数组
            int p1 = left, p2 = mid + 1, k = left;//p1、p2是检测指针，k是存放指针
            while(p1 <= mid && p2 <= right){
                if(a[p1] <= a[p2])
                    tmp[k++] = a[p1++];
                else
                    tmp[k++] = a[p2++];
            }
            //如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
            while(p1 <= mid) tmp[k++] = a[p1++];
            while(p2 <= right) tmp[k++] = a[p2++];//同上
            //复制回原数组
            for (int i = left; i <= right; i++)
                a[i] = tmp[i];
        }

*  **快速排序**

快速排序是一种排序执行效率很高的排序算法，它利用**分治法**来对待排序序列进行分治排序，它的思想主要是通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比关键字小，后面一部分比关键字大，然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序。

// 快速排序    时间复杂度O(nlogn)
    public void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low > high){
            return;
        }
        i = low;
        j = high;
        temp = arr[low];   // 基准位
        while (i < j) {
            while (temp <= arr[j] && i < j) {
                j--;
            }
            while (temp >= arr[i] && i < j) {
                i++;
            }
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        arr[low] = arr[i];
        arr[i] = temp;
        quickSort(arr, low, j-1);
        quickSort(arr, j+1, high);
    }

*  **二分查找**

假设数据是按升序排序的，对于给定值 x，从序列的中间位置开始比较，如果当前位置值等于 x，则查找成功；若 x 小于当前位置值，则在数列的前半段中查找；若 x 大于当前位置值则在数列的后半段中继续查找，直到找到为止。

// 二分法查找  (有序数据集合中不存在重复的数据)  时间复杂度O(logn)
        // 最简单的二分查找实现
        public static int simpleBinarySearch(int[] arr, int key){
            int start=0;
            int end=arr.length-1;
            while (start <= end)
            {
                int mid = (end + start) >> 1;   // >>1相当于除以2、<<2相当于乘4
                if (key < arr[mid])
                {
                    end = mid - 1;
                }else if (key > arr[mid]){
                    start = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    
        // 二分法的递归实现
        public static int binarySearch(int[] a, int val) {
            return bsearchInternally(a, 0, a.length - 1, val);
        }
        private static int bsearchInternally(int[] a, int low, int high, int value) {
            if (low > high)
                return -1;
            int mid = low + ((high - low) >> 1);
            if (a[mid] == value) {
                return mid;
            } else if (a[mid] < value)
                return bsearchInternally(a, mid + 1, high, value);
            else {
                return bsearchInternally(a, low, mid - 1, value);
            }
        }

*  **基数排序**

将整数按位数（个位、十位、百位）切割成不同的数字，然后按每个位数上的数字分别比较。  
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEzMjE0Mw_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEzMjE0Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200621140426211.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEzMjE0Mw==,size_16,color_FFFFFF,t_70