文档章节

快速排序

_
 _OUTMAN_
发布于 2017/07/07 16:07
字数 550
阅读 16
收藏 0

快速排序(Quicksort)是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

    设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

   /**
     * 快速排序
     * @param arr
     * @param low
     * @param high
     */
    private void quickSort(int[] arr, int low, int high) {
        // 递归,需要有跳出递归的条件
        if (low < high) {
            int divide = divideArray(arr, low, high);
            quickSort(arr, low, divide - 1);
            quickSort(arr, divide + 1, high);
        }
    }

    /**
     * 快速排序分割数组,使前面的都比后面的小
     * @param arr
     * @param low
     * @param high
     * @return 返回调整后基准数的位置
     */
    private int divideArray(int[] arr, int low, int high) {
        // 设置下标
        int i = low, j = high;
        // 选择分割数组的值,默认选择数组中的第一个
        int key = arr[low];

        while (i < j) {
            // 从后往前和分割的元素比较。
            while (i < j && arr[j] >= key) {
                // 后面的下标往前移动
                j--;
            }
            // 如果从后面找到比分割元素小的,则赋值到数组前面
            if (i < j) {
                arr[i] = arr[j];// 此时j的位置,就可以存放新的元素
                // 前面的下标向后移动
                i++;
            }

            // 从前往后和分割元素比较,查找比较分割元素大的
            while (i < j && arr[i] <= key) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        // 将分割元素放到中间合适位置,此时,分割元素前是小的,分割元素后是大的
        arr[i] = key;
        return i;
    }

 

© 著作权归作者所有

_
粉丝 22
博文 133
码字总数 63959
作品 0
海淀
程序员
私信 提问

暂无文章

【0918】正则介绍_grep

【0918】正则介绍_grep 9.1 正则介绍_grep上 9.2 grep中 9.3 grep下 一、正则介绍 正则是一串有规律的字符串,它使用单个字符串来描述或匹配一系列符合某个语法规则的字符串。 二、grep工具 ...

飞翔的竹蜻蜓
11分钟前
4
0
为什么要在网站中应用CDN加速?

1. 网页加载速度更快 在网站中使用CDN技术最直接的一个好处就是它可以加快网页的加载速度。首先,CDN加速的内容分发是基于服务器缓存的,由于CDN中缓存了不少数据,它能够给用户提供更快的页...

云漫网络Ruan
49分钟前
8
0
亚玛芬体育(Amer Sports)和信必优正式启动合作开发Movesense创新

亚玛芬体育和信必优正式启动合作开发Movesense创新,作为亚玛芬体育的完美技术搭档,信必优利用Movesense传感器技术为第三方开发移动应用和服务。 Movesense基于传感器技术和开放的API,测量...

symbiochina88
今天
4
0
创龙TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA核心板规格书

SOM-TL437xF是一款广州创龙基于TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA芯片设计的核心板,采用沉金无铅工艺的10层板设计,适用于高速数据采集和处理系统、汽车导航、工业自动化等领...

Tronlong创龙
今天
4
0
好程序员Java学习路线分享MyBatis之线程优化

  好程序员Java学习路线分享MyBatis之线程优化,我们的项目存在大量用户同时访问的情况,那么就会出现大量线程并发访问数据库,这样会带来线程同步问题,本章我们将讨论MyBatis的线程同步问...

好程序员官方
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部