算法

递归

自己调用自己调用方法时传入不同的参数，使代码更加简洁

递归的调用机制:

• 每次调用方法时，会创建一个新的栈空间(独立的)，以及私有的局部变量(独立不会相互影响)

• 当方法使用的是引用变量时,每个开辟的栈空间共用这一引用变量

• 递归必须无限向递归结束条件靠近，否则会出现StackOverFlowError栈溢出错误

• 当方法执行结束或这遇到返回时，谁调用就返回到那一层中

递归可以解决的问题

• 问题描述是递归的(阶乘，斐波那契数列)

• 问题的解法是递归的(汉诺塔问题)

• 数据结构递归的(树的遍历，图的深度优先搜索)

八大排序算法

分类：

1. 内部排序：使用内存进行排序

2. 外部排序：使用外部存储排序

内部排序分类：

1. 插入排序

   • 直接插入排序

   • 希尔排序

2. 交换排序

   • 冒泡排序

   • 快速排序

3. 选择排序

   • 简单选择排序

   • 堆排序

4. 归并排序

5. 基数排序

冒泡排序-时间复杂度O(n2)

算法规则:

遍历数组如果遇到逆序则进行数据交换

public class BubbleSort
{
    public static void main(String[] args)
    {
        int arr[]= {1,2,3,5,4};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    //arr【】 待排序数组
    public static void bubbleSort(int arr[]) {
        boolean flag=false;//作为标记数组数据是否发生交换
        int temp;//作为交换数据的临时变量
        //外层控制循环次数
        for(int i=0;i<arr.length-1;i++) {
            System.out.println("第"+i+"次排序");
            //内层控制数据排序
            for(int j=0;j<arr.length-1-i;j++) {
                if(arr[j]>arr[j+1]) {
                    //前面大于后面
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag=true;
                }
            }
            if(!flag) {
                break;
            }else {
                flag=false;
            }
        }
        
    }
}

 

冒泡算法优化：

定义一个标记变量flag，判断flag的值是否发生改变，若没改变则数组已经有序则可以提前跳出循环

选择排序-时间复杂度O(2)

算法规则：遍历数组，将每次遍历得到的最小值，与起始位置数据做交换

arr[0]-arr[n-1],找出最小值与arr[0]交换

arr[1]-arr[n-1],找出最小值与arr[1]交换,以此类推

public class SelectSort
{
    public static void main(String[] args)
    {
        int arr[]= {101,34,119,1,-1,90,123};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    //arr[]待排序数组
    public static void selectSort(int arr[]) {
        int min;//最小值记录
        int minIndex;//最小值下标记录
        //外层控制循环次数
        for(int i=0;i<arr.length-1;i++) {
            min=arr[i];
            minIndex=i;
            //内层从i开始遍历数组进行排序
            for(int j=i+1;j<arr.length-1;j++) {
                //存在小于临时最小值则替换最小值并记录下标
                if(arr[j]<min){
                    min=arr[j];
                    minIndex=j;
                }
            }
            //数据交换
            if(minIndex!=i) {
                arr[minIndex]=arr[i];
                arr[i]=min;
                
            }
        }
    }
}

选择排序优化:

判断最小值位置是否发生改变，若没有则不需要进行数据交换

插入排序-时间复杂度O(n2)

算法规则:

假定两个数组，一个是原数组(大小为n-1)，一个是有序数组(大小为1，存放原数组的第一个元素)。将原数组中的数据依次取出放入有序数组中的适当位置，将原数组数据取出完毕后，则排序完毕

public class InsertSort
{
    public static void main(String[] args)
    {
        int arr[]= {101,34,119,1,-1,89};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    //arr[]待排序数组
    public static void insertSort(int arr[]) {
        int value,insertIndex;
        //假定第一个为有序，从下一位开始插入
        for(int i=1;i<arr.length;i++) {
            value=arr[i];
            insertIndex=i-1;
            //循环条件：插入位置没到数组第一位以及插入位置数据大于待插入数据
            while(insertIndex>=0 && arr[insertIndex]>value) {
                arr[insertIndex+1]=arr[insertIndex];//插入位置数据后移
                insertIndex--;//插入位置前移
            }
            //找到插入位置
            if(insertIndex!=i) {
                arr[++insertIndex]=value;
            }
        }
    }
}

算法优化：

判断插入位置是否发生改变决定是否进行数据插入

希尔排序-时间复杂度O(nlog2n)

算法规则:

将数组按照一定增量分组，对每组进行插入排序，继续减少增量，插入排序，当增量减少为1时，则进行最后的插入排序，结果即为有序的

public class ShellSort
{
    public static void main(String[] args)
    {
        int arr[]= {8,9,1,7,2,3,5,4,6,0,11,0,12,3,7};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    //arr[]待排序数组
    public static void shellSort(int arr[]) {
        int value,index;
        //定义增量(组数),每次除以2
        for(int gap=arr.length/2;gap>0;gap/=2) {
            //组内进行插入排序
            for(int i=gap;i<arr.length;i++) {
                value=arr[i];
                    //循环条件：当插入位置(i-gap)>=0并且插入位置的值大于待插入数据
                    while(i-gap>=0&&arr[i-gap]>value) {
                        arr[i]=arr[i-gap];
                        i-=gap;
                    }
                    //找到插入位置
                    arr[i]=value;
            }
        }
    }
}

快速排序-时间复杂度O(nlog2n)

算法规则：

将数组按照大于小于中间值分类，向左向右递归得到有序数组

public class QuickSort
{
    public static void main(String[] args)
    {
        int arr[]= {-9,78,0,23,-567,70};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    
    //arr[]待排序数组，left数组左边索引，right数组右边索引
    public static void quickSort(int arr[],int left,int right) {
        int l=left;//当前数组左索引
        int r=right;//当前数组右索引
        int pivot=arr[(left+right)/2];//中间值用于判断数据
        int temp;
        while(l<r) {
            //找左边大于等于中间值的数据
            while(arr[l]<pivot) {
                l++;
            }
            //找右边大于等于中间值的数据
            while(arr[r]>pivot) {
                r--;
            }
            //判断是否循环结束
            if(l>=r) {
                break;
            }
            //左右数据交换
            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;
            
            //防止存在相同值时死循环
            if(arr[l]==pivot) {
                r--;
            }
            if(arr[r]==pivot) {
                l++;
            }   
        }
        if(l==r) {
            l++;
            r--;
        }
        //向左递归
        if(left<r) {
            quickSort(arr,left,r);
        }
?
        //向右递归
        if(l<right) {
            quickSort(arr, l, right);
        }
    }
}
?

归并排序-时间复杂度O(nlog2n)

算法规则：

采用分治策略，将数组分割值至大小为1的有序数组再依次进行合并，合并到最终的数据即为有序数组

public class MergeSort
{
    public static void main(String[] args)
    {
        int arr[]= {8,4,5,7,1,3,6,2};
        int temp[]=new int[arr.length];
        mergeSort(arr, temp, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    
    //分割
    public static void mergeSort(int arr[],int temp[],int left,int right) {
        if(left<right) {
            //计算两组有序数组间隔索引(中间索引)
            int mid=(left+right)/2;
            mergeSort(arr, temp, left, mid);
            mergeSort(arr, temp, mid+1, right);
            merge(arr, temp, left, right, mid);
            
        }
    }
    
    //归并
    //arr[],待排序数组
    //temp[]临时数组
    //left左边有序数组索引
    //reght右边有序数组索引
    //mid中间索引
    public static void merge(int arr[],int temp[],int left,int right,int mid) {
        int i=left;//左边索引
        int j=mid+1;//右边索引
        int t=0;//临时数组索引
        //1遍历两个有序数组将数据加入临时数组中
        while(i<=mid&&j<=right) {
            //左边小
            if(arr[i]<arr[j]) {
                temp[t]=arr[i];
                t++;
                i++;
            }else {
                temp[t]=arr[j];
                t++;
                j++;
            }
        }
        //2将剩余数组数据加入临时数组中
        while(i<=mid) {
            //左边数组有剩余
            temp[t]=arr[i];
            t++;
            i++;
        }
        while(j<=right) {
            //右边数组有剩余
            temp[t]=arr[j];
            t++;
            j++;
        }
        t=0;
        //3拷贝临时数组数据到数据中
        int innerIndex=left;
        while(innerIndex<=right) {
            arr[innerIndex]=temp[t];
            innerIndex++;
            t++;
        }
    }
}