比较算法

冒泡排序

概述：

实现代码(逆序)：

package com.lin;

public class BubbleSort {
    //排序方法
    public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        for(int i=0; i<arr.length;i++) {
            //如果内循环的索引大于外层的就无法进行排序了
            for(int j=arr.length-1; j>i; j--) {
                if(arr[j]<arr[j-1]) {
                    swap(arr, j-1, j);
                }
            }
        }
    }
    //交换方法
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr;
        arr = new int[]{....};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(" "+i);
        }
    }

}

正序实现代码

package com.lin;
/*
 *@Description:冒泡排序算法实现（正序）
 */
public class BubbleSort2 {
    public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        for(int i=1;i<arr.length;i++) {
           //当内循环小于数组的长度再减去i的时候就退出
            for(int j=0; j<arr.length-i; j++) {
                if(arr[j]>arr[j+1]) {
                    swap(arr, j+1, j);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr;
        arr = new int[]{....};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(" "+i);
        }

    }

}

选择排序

实现代码（正序) ：

package com.lin;
/*
@Description 正序的选择排序算法
 */
public class SelectSort {
    public static void selectSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        //先定义最小的数字

        for(int i=0; i<arr.length;i++){//只需要比较n-1次
            //先定义最小值的索引 从0开始
            int minIndex = i;
            for(int j=i+1; j<arr.length;j++)
            {
            //从i+1开始比较，因为minIndex默认为i了就是0，i就没必要比了。
                //判断前面的值是否小于后面
                if(arr[j]<arr[minIndex])
                {
                    //如果前面的数字 小于后面的值就将后面的索引和之前的交换
                    minIndex = j;
                }
            }
            //当内循环找到最小值的时候才进行一次交换
            if(minIndex != i) { //如果minIndex不为i，说明找到了更小的值，执行交换的方法
                swap(arr, i, minIndex);
            }
    }
}
public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        }

    public static void main(String[] args) {
        int[] arr;
        arr = new int[]{5,4,8,6,3,2,2};
        selectSort(arr);
        for (int i : arr) {
            System.out.print(" "+i);
        }
    }
        }

插入排序

实现代码：

package com.lin;
/**
 *@Description:简单插入排序算法实现(正序)
 */
public class InsertSort {
    public static void insertSort(int[] a) {
        int i, j, insertNote;// 要插入的数据
        for (i = 1; i < a.length; i++) {// 从数组的第二个元素开始循环将数组中的元素插入
            insertNote = a[i];// 设置数组中的第2个元素为第一次循环要插入的数据 依次往后
            j = i - 1;
            //不断的判断插入的元素是否小于前面的所有元素 是的话就循环将元素往右边放
            while (j >= 0 && insertNote < a[j]) {
                a[j + 1] = a[j];// 如果要插入的元素小于第j个元素,就将第j个元素向后移动
                j--;
            }
            a[j + 1] = insertNote;// 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
        }
    }


    public static void main(String[] args) {
        int[] arr;
        arr = new int[]{3,5,4,8,6,3};
        insertSort(arr);
        for (int i : arr) {
            System.out.print(" "+i);
        }
    }

}

希尔排序

实现代码：

package com.lin;

public class ShellSort {


    public static int[] shellSort(int[] array){
        //控制步长，每循环一次就除二
        for (int n = array.length/2; n > 0; n /= 2 ){
            //从下标为步长的元素开始，依次向后循环
            
            //不用担心前面的元素，因为下面j层的循环，会依次和前面的数字进行比较。

            for (int i = n; i < array.length; i++) {
                // 从下标为[步长]的数字开始，向前 隔一个步长 进行比较
                // 如果后一个比前一个小，则交换，如果不是，则返回上一层循环，
                // i+1后再进行【如果后一个比前一个小，则交换】的比较
                // 之后j-n，再和一开始位置的两个步长距离的数字进行比较
                // 如此反复
                for (int j = i; j > 0 && j-n >= 0 && array[j] < array[j-n]; j-=n) {
                    int temp = array[j];
                    array[j] = array[j-n];
                    array[j-n] = temp;
                }
            }
        }
        return array;
    }
    public static void main(String[] args) {
        int[] array = {3,5,4,8,6,3};
        int[] ints = shellSort(array);
        for (int anInt : ints) {
            System.out.print(" "+anInt);
        }
//        int[] array = new int[80000];
//        for (int i = 0; i < array.length; i++) {
//            array[i] = (int)(Math.random()*800000);
//        }
        long startTime=System.currentTimeMillis();
        shellSort(array);
        long endTime=System.currentTimeMillis();
        System.out.println("  程序运行时间： "+(endTime - startTime)+"ms");
        //希尔排序排序80k长度的数组，在我这台电脑上只用了不到0.1秒，而插入排序则需要2秒多
    }
}

快速排序

实现代码：

import java.util.Random;
/**
 * 912. 排序数组 快排 三指针
 * https://leetcode.cn/problems/sort-an-array/description/
 */
public class sortArray {
        // 快速排序 3：三指针快速排序
        /**
         * 列表大小等于或小于该大小，将优先于 quickSort 使用插入排序
         */
        private static final int INSERTION_SORT_THRESHOLD = 7;

        private  final Random RANDOM = new Random();

        public int[] sortArray(int[] nums) {
            int len = nums.length;
            quickSort(nums, 0, len - 1);
            return nums;
        }

        private void quickSort(int[] nums, int left, int right) {
            // 小区间使用插入排序
            if (right - left <= INSERTION_SORT_THRESHOLD) {
                insertionSort(nums, left, right);
//                这里记得return掉 否则会抛异常
                return;
            }
            // 产生[left,right]的某个索引
            int randomIndex = left + RANDOM.nextInt(right - left + 1);
            swap(nums, randomIndex, left);

            // 循环不变量：
            // all in [left + 1, lt] < pivot
            // all in [lt + 1, i) = pivot
            // all in [gt, right] > pivot
//            哨兵
            int pivot = nums[left];
            int lt = left;
            int gt = right + 1;

            int i = left + 1;
            //当i==gt的时，第二个数组和第三个数组还没连起来，所以循环还应该继续
            while (i < gt) {
                if (nums[i] < pivot) {
                    lt++;
                    swap(nums, i, lt);
                    i++;
                } else if (nums[i] == pivot) {
                    i++;
                } else {
                    gt--;
                    swap(nums, i, gt);
                }
            }
            swap(nums, left, lt);
            // 注意这里，大大减少了两侧分治的区间
            quickSort(nums, left, lt - 1);
            quickSort(nums, gt, right);
        }

        /**
         * 对数组 nums 的子区间 [left, right] 使用插入排序
         *
         * @param nums  给定数组
         * @param left  左边界，能取到
         * @param right 右边界，能取到
         */
        private void insertionSort(int[] nums, int left, int right) {
            for (int i = left + 1; i <= right; i++) {
                int insertNumber = nums[i];
                int j = i;
                while (j > left && nums[j - 1] > insertNumber) {
                    nums[j] = nums[j - 1];
                    j--;
                }
                nums[j] = insertNumber;
            }
        }

        private void swap(int[] nums, int index1, int index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
}

归并排序

代码实现：

package com.lin;

public class MergeSort {
    //两路归并算法，两个排好序的子序列合并为一个子序列
    //mid为取子序列前面和后面之和的对半索引
    public static void merge(int[] a, int left, int mid, int right){
        int []tmp=new int[a.length];//辅助数组 将改变的子序列复制到a数组当中
        int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针 通过k的索引赋值到temp的数组上面
        //当子序列的索引都小于检测指针进行循环
        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];
    }

    public static void mergeSort(int[] a, int start, int end){
        //递归调用函数 先把子序列分完再开始排序
        if(start<end){//当子序列中只有一个元素时结束递归
            int mid=(start+end)/2;//划分子序列
            mergeSort(a, start, mid);//对左侧子序列进行递归排序
            mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
            merge(a, start, mid, end);//合并 完成一次排序合并就会satrt 和mid 还有end 的值都会增加 两两元素之间发生交交换
        }
    }
}

堆排序

package com.lin;

import java.util.Arrays;

public class HeapSort {
        //大函数
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从最后一个非叶子结点开始（arr.length/2-1） 从下至上，从右至左调整结构 一直到找到最后的非叶子结点 最后也就到了0索引为0的那里
            //循环执行调用调大顶堆的函数
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            //j-1 的原因是交换完就最后一个元素后 除去最后一个元素并对剩下的元素进行重新堆积大顶堆
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换

            adjustHeap(arr,0,j);//对重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
            //调整大顶堆函数
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i 也就是父节点 2k+1的原因调整因为交换元素的大顶堆 使其满足大顶堆定义
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            //k为i结点的子节点的第一个结点 也就是左子节点
            //判断找出最大的子节点
            if(k+1<length && arr[k]<arr[k+1]){
                //如果没有右结点的时候直接进行下面的比较
                //如果左子结点小于右子结点，k指向右子结 然后将索引+1
                k++;
            }
            //最后将那个最大的子节点
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换） 并将当前的子节点变为子节点然后回到上面的循环再与其子节点进行比较
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */

        //交换函数
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

非比较算法

比较和非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

计数排序

package com.lin;

public class CountSort {
    public static int[] countSort1(int[] arr){
        if (arr == null || arr.length == 0) {
            return null;
        }
        //定义待排数组中的最大值 先将其最小为为最大的值 这样肯定有比它大的数 然后返回更大的值
        int max = Integer.MIN_VALUE;
        //定义待排数组中的最小值 先将其最小为为最小的值 这样肯定有比它小的数 然后返回更小的值
        int min = Integer.MAX_VALUE;
        //根据Math函数找出数组中的最大最小值
        for(int i = 0; i < arr.length; i++){

            max = Math.max(max, arr[i]);

            min = Math.min(min, arr[i]);
        }
        //辅助计数数组 help该数组大小为待排序数组中的最大值减最小值+1 保证了如果是以步长为1增的数字都能够排在数组当中
        int help[] = new int[max-min+1];
        //找出每个数字出现的次数 从索引为0的开始
        for(int i = 0; i < arr.length; i++){
            //position 为索引的位置
            int position= arr[i] - min;

            //有这个数的话在索引上的值+1
            help[position]++;
        }
        int index = 0;
        for(int i = 0; i < help.length; i++){
            //如果数组上有此值 按照个数依次将他排完
            while(help[i]-- > 0){
                //从最小值开始加起来 因为最小值排在最前面  然后根据出现的位置进行排序 就可以将正确的顺序排放下去了
                //arr[index++]的值为当前的索引值加上最小值 
                arr[index++] = i+min;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr;
        arr = new int[]{3,5,4,8,6,3};
        countSort1(arr);
        for (int i : arr) {
            System.out.print(" "+i);
        }
    }
    }

桶排序

代码实现：

package com.lin;
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
    public static void bucketSort(int[] arr) {

        int max = Integer.MIN_VALUE;

        int min = Integer.MAX_VALUE;
        //找出待排序数组中的最大值max、最小值min
        for (int i = 0; i < arr.length; i++) {

            max = Math.max(max, arr[i]);

            min = Math.min(min, arr[i]);
        }

        //桶数
        int bucketNum = (max - min) / arr.length + 1;
        //创建动态ArrayList数组作为桶 桶里面放的元素也用ArrayList 储存
        //数组当中的元素声明为整形
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }

        //将每个元素放入桶
        for (int i = 0; i < arr.length; i++) {

            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);

        }

        //对每个桶进行排序
        for (int i = 0; i < bucketArr.size(); i++) {
            Collections.sort(bucketArr.get(i));
        }
        System.out.println(bucketArr.toString());

    }

    public static void main(String[] args) {
        int[] arr;
        arr = new int[]{1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
        bucketSort(arr);
    }
}

冒泡排序，插入排序，是稳定的排序算法；

不稳定算法

选择排序，希尔排序，堆排序，归并排序，快速排序不稳定的。

查找顺序速度

顺序 分块 折半 哈希

顺序查找的时间复杂度为o(n)

分块查找的时间复杂度为o(logn)到o(n)之间

二分查找的时间复杂度为o(log n)

哈希查找的时间复杂度为o(1)