专栏首页JantiJava基础巩固——排序

Java基础巩固——排序

快速排序

基本思想:

  通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则分别对两部分继续进行排序,直到整个序列有序。

实例:

1.一趟排序的过程:

2.排序的全过程:

把整个序列看做一个数组,把第零个位置看做中轴,和最后一个比,如果比他小,则交换,比它大不做任何处理;

交换了以后再和小的那端比,比它小不交换,比它大交换。这样循环往复,一趟排序完成,左边的就是比中轴小的,

右边的就是比中轴大的,然后再用分治法,分别对这两个独立的数组进行排序。

代码实现

public class QucikSortDemo {
    public static void main(String arg[]) {

        int[] numbers = {10, 89, 87, 76, 56, 46, 11, 75, 32, 35, 98};
        System.out.println("排序前:");
        printArr(numbers);

        quickSort(numbers);
        System.out.println("排序后:");
        printArr(numbers);
    }

    /**
     * 查找出中轴位置(默认是最低为low)的在number数组排序后所在位置
     *
     * @param numbers
     * @param low
     * @param high
     * @return
     */
    public static int getMiddle(int[] numbers, int low, int high) {
        // 数组的第一位作为中轴
        int temp = numbers[low];
        while (low < high) {
            while (low < high && numbers[high] > temp) {
                high--;
            }
            // 比中轴晓得记录移动到低端
            numbers[low] = numbers[high];
            while (low < high && numbers[low] < temp) {
                low++;
            }
            // 比中轴大的记录移到高端
            numbers[high] = numbers[low];

        }
        // 中轴记录到尾
        numbers[low] = temp;
        // 返回中轴的位置
        return low;
    }

    /**
     * 分治排序
     *
     * @param numbers
     * @param low
     * @param high
     */
    public static void quickSort(int[] numbers, int low, int high) {
        if (low < high) {
            // 将numbers数组进行一分为二
            int middle = getMiddle(numbers, low, high);
            // 将低字段表进行递归排序
            quickSort(numbers, low, middle - 1);
            // 将高字段表进行递归排序
            quickSort(numbers, middle + 1, high);
        }
    }

    public static void quickSort(int[] numbers) {
        if (numbers.length > 0) {
            quickSort(numbers, 0, numbers.length - 1);
        }
    }

    public static void printArr(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + ",");
        }
        System.out.println("");
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java基础巩固——反射

    什么是反射 ----    反射机制就是指程序运行时能够获取自身的信息。在Java中,只要给出类的名字,就可以通过反射机制来获取类的信息 哪里用的到反射机制 -...

    Janti
  • JVM活学活用——类加载机制

    类的实例化过程 ---- 有父类的情况 1. 加载父类静态     1.1 为静态属性分配存储空间并赋初始值     1.2 执行静态初始化块和静态初始化...

    Janti
  • redis学习笔记

    Window 下安装 下载地址:https://github.com/MSOpenTech/redis/releases Redis 支持 32 位和 64 位...

    Janti
  • struts2+spring+hibernate整合步骤(1)

    struts2、hibernate、spring所需jar包 struts-core-2.x.x.jar ----struts核心包 xwork-cor...

    奋斗蒙
  • Codeforces Round 618 (Div. 2)C. Anu Has a Function

    定义$f(x, y) = (x|y)-y$,有一个数组$A$可以为$[a_1, a_2, …, a_n]$,重排$A$中的元素使得$f(f(…f(f(a_1,a...

    xiaohejun
  • <b>与<strong> <em>与<i>标签的区别

    windseek
  • Spring和Elasticsearch全文搜索整合详解

    ElasticSearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于RESTful web接口。Elasticsear...

    品茗IT
  • Django 2.1.7 使用富文本编辑器 tinymce

    Django 2.1.7 Admin - 注册模型、自定义显示列表字段 Django 2.1.7 上传图片 - Admin后台管理 https://djan...

    Devops海洋的渔夫
  • SpringBoot | 是如何实现自动配置的?

    相信接触过 SpringBoot 的朋友都知道 SpringBoot 有各种 starter 依赖,想要什么直接勾选加进来就可以了。想要自定义的时候就直接在配置...

    一个优秀的废人
  • Spring Boot 运作原理

    SpringBoot是由Pivotal团队提供的全新框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置,从而使...

    java架构师

扫码关注云+社区

领取腾讯云代金券