Java递归思想与快速排序

简介: Java递归思想与快速排序

1 递归思想

  • 以编程的角度来看,递归指的是方法定义中调用方法本身的现象
  • 把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
  • 递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算

2 快速排序

  • 冒泡排序算法中,一次循环结束,就相当于确定了当前的最大值,也能确定最大值在数组中应存入的位置
  • 快速排序算法中,每一次递归时以第一个数为基准数,找到数组中所有比基准数小的.再找到所有比基准数大的.小的全部放左边,大的全部放右边,确定基准数的正确位置
  • 之后分为两边还是无序状态继续套用前面方法也就是递归的过程

3 源码详解

public class QuickSortTest {
    public static void main(String[] args) {
//        1,从右开始找比基准数小的
//        2,从左开始找比基准数大的
//        3,交换两个值的位置
//        4,红色继续往左找,蓝色继续往右找,直到两个箭头指向同一个索引为止
//        5,基准数归位
        int[] arr = {1,2,4,8,5,1};
        //参数 数组和遍历长度
        quiteSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    /**
     *
     * @param arr
     * @param start
     * @param end
     */
    private static void quiteSort(int[] arr, int start, int end) {
      //递归到最后肯定就剩一个了所有数归为  如果判断到不论前后+1 -1就要跳出去这个递归
        if(end < start){
            return;
        }
        //为了基准数归位服务
        int left0 = start;
        //为了递归服务 因为数值不断发生改变  要用到开始和结束时找不到所以临时缓存这两个
        int right0 = end;
        //基准数一般都是左边第一个
        int baseNumber = arr[left0];
        //相等就代表找到了  end > start要控制不能超过基准或者等于后继续空指针异常
        while(start != end){
//        1,从右开始找比基准数小的
//        arr[end] >= baseNumber 如果相等的话但是也不是同一个位置就死循环了
            while(arr[end] >= baseNumber && end > start){
                end--;
            }
//        2,从左开始找比基准数大的
            while(arr[start] <= baseNumber && end > start){
                start++;
            }
//        3,都不满足条件 也就是 end=start 交换两个值的位置
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        //基准数归位 两次交换 一次是分左边右边 然后分完左边右边后就相等到一个位置让基准数归为
        int temp = arr[start];
        arr[start] = arr[left0];
        arr[left0] = temp;
        //最后走这两部都要形成只有一个数需要比较的阶段后肯定要错位 走到出口
        //从0开始到重合位置-1
        quiteSort(arr,left0,start-1);
        //从重合位置+1到末尾
        quiteSort(arr,start +1,right0);
    }
}

4 设计顺序

  应该先写出一次的排序,较为简单,之后再去递归找出口,其实快速排序是对冒泡排序的一种改进。它的基本思想是:分治思想,通过一次排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归或者非递归进行,以此达到整个数据变成有序序列。

目录
相关文章
|
7月前
|
搜索推荐 Java 索引
|
6月前
|
Java
java基础(11)函数重载以及函数递归求和
Java支持函数重载,即在同一个类中可以声明多个同名方法,只要它们的参数类型和个数不同。函数重载与修饰符、返回值无关,但与参数的类型、个数、顺序有关。此外,文中还展示了如何使用递归方法`sum`来计算两个数之间的和,递归的终止条件是当第一个参数大于第二个参数时。
47 1
java基础(11)函数重载以及函数递归求和
|
8月前
|
算法 Java
java使用递归及迭代方式实现前序遍历 中序遍历 后序遍历 以及实现层序遍历
java使用递归及迭代方式实现前序遍历 中序遍历 后序遍历 以及实现层序遍历
111 7
|
9月前
|
Java
蓝桥杯Java组暴力递归搜图
蓝桥杯Java组暴力递归搜图
51 4
|
9月前
|
Java
java实现斐波那契数列(递归、迭代、流)
java实现斐波那契数列(递归、迭代、流)
|
9月前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
68 3
|
9月前
|
算法 前端开发 Java
探讨Java中递归构建树形结构的算法
探讨Java中递归构建树形结构的算法
138 1
|
9月前
|
Java
Java递归:深入理解与应用
Java递归:深入理解与应用
104 1
|
10月前
|
Java
<Java SE> 5道递归计算,创建数组,数组遍历,JVM内存分配...
<Java SE> 5道递归计算,创建数组,数组遍历,JVM内存分配
87 2
|
10月前
|
设计模式 安全 Java
【设计模式】JAVA Design Patterns——Curiously Recurring Template Pattern(奇异递归模板模式)
该文介绍了一种C++的编程技巧——奇异递归模板模式(CRTP),旨在让派生组件能继承基本组件的特定功能。通过示例展示了如何创建一个`Fighter`接口和`MmaFighter`类,其中`MmaFighter`及其子类如`MmaBantamweightFighter`和`MmaHeavyweightFighter`强制类型安全,确保相同重量级的拳手之间才能进行比赛。这种设计避免了不同重量级拳手间的错误匹配,编译时会报错。CRTP适用于处理类型冲突、参数化类方法和限制方法只对相同类型实例生效的情况。

热门文章

最新文章