递归应用之快速排序

ゞ浴缸里的玫瑰 2022-05-23 01:53 155阅读 0赞

**递归应用1斐波那契数列**

斐波那契数列满足：1，1，2，3，5，8，13……  
从第三个位置起每个元素的值是前面2个元素的和

代码实现：

public class FeiBo{
        public static void main(){
            int num1=1;
            int num2=1;
            int n=6;
            int numn=0;
            for(int i=3;i<n;i++){
                numn=num1+num2;
                num2=numn;
                num1=num2;
            }
            System.out.println(numn);
        }
    }
    输出：8

递归实现：

package cn.dataStructures.Sort;
    
    public class FeiBo {
        public static void main(String[] args) {
            int res=fun1(6);
            System.out.println(res);
        }
        //递归实现
        public static int fun1(int n){
            if(n==1||n==2){
                return 1;
            }
            return fun1(n-1)+fun1(n-2);
        }
        //正常for循环
        public static void fun2(){
            int num1=1;
            int num2=1;
            int n=6;
            int numn=0;
            for(int i=3;i<n;i++){
                numn=num1+num2;
                num2=numn;
                num1=num2;
            }
            System.out.println(numn);
        }
    }

**递归应用之快速排序**  
**快排思想：**  
快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。

一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

接着分别比较左右两边的序列，重复上述的循环。  
代码实现：

package cn.DataStructures.Sort;
    
    public class QuickSort {
        public static void main(String[] args) {
            int []arr={
       12,20,5,16,22,15,1,2,100,30,45,23,9};
            int low=0;
            int high=arr.length-1;
            quickSort(arr,low,high);
            printSort(arr);
        }
        public static void quickSort(int []arr,int low,int high){
            int start=low;
            int end=high;
            int key=arr[low];
            while(start<end){
                while(start<end&&arr[end]>=key)
                    end--;
                if(arr[end]<=key){
                    int temp=arr[end];
                    arr[end]=arr[start];
                    arr[start]=temp;
                }
                while(start<end&&arr[start]<key)
                    start++;
                if(arr[start]>=key){
                    int temp=arr[start];
                    arr[start]=arr[end];
                    arr[end]=temp;
                }
            }
            if(low<start)
                quickSort(arr,low,start-1);
            if(end<high)
                quickSort(arr,end+1,high);
        }
        public static void printSort(int []arr){
            StringBuilder res=new StringBuilder();
            res.append("[");
            for(int i=0;i<arr.length;i++){
                if(i==arr.length-1)
                    res.append(arr[i]+"]");
                else
                    res.append(arr[i]+",");
            }
            System.out.println(res.toString());
        }
    }
    输出结果：[1,2,5,9,12,15,16,20,22,23,30,45,100]