文档章节

Java之排序

思想永无止境
 思想永无止境
发布于 2016/11/04 11:56
字数 538
阅读 19
收藏 0
import java.util.Arrays;
import java.util.Random;

/** * 排序工具类<br> * 冒泡排序/选择排序/快速排序 * * @author tang * */
public class SortUtils {

    public static void main(String[] args) {

        int[] array = new int[10000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(array.length);
        }

        System.out.println("冒泡排序:");
        int[] clone1 = array.clone();
        long begin = System.currentTimeMillis();
        bubbleSort(clone1, true);
        System.out.println("本次排序用时:" + (System.currentTimeMillis() - begin));
        println(Arrays.toString(clone1));

        System.out.println("选择排序:");
        int[] clone2 = array.clone();
        begin = System.currentTimeMillis();
        selectionSort(clone2, true);
        System.out.println("本次排序用时:" + (System.currentTimeMillis() - begin));
        println(Arrays.toString(clone2));

        System.out.println("快速排序:");
        int[] clone3 = array.clone();
        begin = System.currentTimeMillis();
        quickSort(clone3, true);
        System.out.println("本次排序用时:" + (System.currentTimeMillis() - begin));
        println(Arrays.toString(clone3));
    }

    private static void println(String str) {
        System.out.println("排序结果:" + str.substring(0, 20).substring(1) + " ...");
    }

    /** * 冒泡排序 * * @param array * @param isAsc * 是否升序 */
    public static void bubbleSort(int[] array, boolean isAsc) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (isAsc ? (array[j] > array[j + 1]) : (array[j] < array[j + 1])) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    /** * 选择排序 * * @param array * @param isAsc * 是否升序 */
    public static void selectionSort(int[] array, boolean isAsc) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (isAsc ? (array[i] > array[j]) : array[i] < array[j]) {
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
    }

    /** * 快速排序(又称交换排序/exchangeSort)<br> * 参考java.util.DualPivotQuicksort * * @param array * @param isAsc * 是否升序 */
    public static void quickSort(int[] array, boolean isAsc) {
        quickSort(array, 0, array.length - 1, isAsc);
    }

    /** * 快速排序(又称交换排序/exchangeSort)<br> * 参考java.util.DualPivotQuicksort * * @param array * @param startIndex * @param endIndex * @param isAsc * 是否升序 */
    public static void quickSort(int[] array, int startIndex, int endIndex, boolean isAsc) {

        if (startIndex >= endIndex) {
            return;
        }

        int leftIndex = startIndex;
        int rightIndex = endIndex;
        int markValue = array[startIndex];
        int nullValueIndex = startIndex;

        do {
            while (leftIndex < rightIndex && (isAsc ? array[rightIndex] >= markValue : array[rightIndex] < markValue)) {

                rightIndex--;
            }
            if (leftIndex < rightIndex && (isAsc ? array[rightIndex] < markValue : array[rightIndex] >= markValue)) {

                array[nullValueIndex] = array[rightIndex];
                nullValueIndex = rightIndex;
                leftIndex++;
            }
            while (leftIndex < rightIndex && (isAsc ? array[leftIndex] <= markValue : array[leftIndex] > markValue)) {

                leftIndex++;
            }
            if (leftIndex < rightIndex && (isAsc ? array[leftIndex] > markValue : array[leftIndex] <= markValue)) {

                array[nullValueIndex] = array[leftIndex];
                nullValueIndex = leftIndex;
                rightIndex--;
            }
        } while (leftIndex < rightIndex);// ensure last leftIndex less rightIndex, so use do while.

        array[nullValueIndex] = markValue;

        quickSort(array, startIndex, nullValueIndex - 1, isAsc);

        quickSort(array, nullValueIndex + 1, endIndex, isAsc);
    }

}

以下为随机一次10000个数字排序打印结果:
冒泡排序:
本次排序用时:223
排序结果:0, 1, 2, 3, 4, 4, 8 …
选择排序:
本次排序用时:219
排序结果:0, 1, 2, 3, 4, 4, 8 …
快速排序:
本次排序用时:1
排序结果:0, 1, 2, 3, 4, 4, 8 …

© 著作权归作者所有

思想永无止境
粉丝 4
博文 257
码字总数 292814
作品 0
昌平
程序员
私信 提问
Java PriorityQueue && PriorityBlockingQueue

Java PriorityQueue && PriorityBlockingQueue 我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。举个例子,比方说我们有一个每日交易时...

秋风醉了
2015/01/12
218
0
在 Hibernate 中直接操作 JDBC 接口

简介: Hibernate 在处理多表关联及分组排序等复杂数据库查询操作时,其固有的 O-R 映射机制会产生大量冗余 SQL 操作,系统性能比传统的 JDBC 低很多。本文分析了 Hibernate 产生此类问题的原...

红薯
2010/04/16
802
2
JAXB Annotation初步使用

JAXB(Java Architecture for XML Binding简称JAXB)允许Java开发人员将Java类映射为XML表示方式。JAXB提供两种主要特性:将一个Java对象序列化为XML,以及反向操作,将XML解析成Java对象。换...

秋风醉了
2014/07/02
380
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
1K
5
Google Reader订阅排行榜-关于Java

在google reader中,读者可以搜索自己喜欢的供稿,遗憾的是搜索出来的题目并没有按照rss的订阅数量进行排序。这几天写了个小程序,抓取某个关键词下的所有rss,然后按照订阅数量从大到小排序...

红薯
2010/05/04
895
0

没有更多内容

加载失败,请刷新页面

加载更多

Java Varargs 可变参数使用

Java1.5 提供了一个叫varargs的新功能,就是可变长度的参数。 "Varargs"是 “variable number of arguments”的意思。有时候也被简单的称为 “variable arguments”。 定义实参个数可变的方法...

honeymoose
今天
69
0
IDEA 拉取、上传、更新 项目到 Gitee+GitHub_超详细超简单版

注:本人使用的idea是最新版(2019.1.2),要是其他的版本的不要惊慌〜,基本上都一样,没有什么太大的差别的 首先我要说一下,拉取项目分两个,一个,你就没有项目,拉取仓库的整个项目,而...

杨木发
今天
54
0
pyqt5环境搭建(Ubuntu19.10+pycharm+python3)

1.安装pyqt5 sudo apt-get install python3-pyqt5 sudo apt-get install qttools5-dev-tools sudo apt-get install qt5-default 2.安装pycharm 下载pycharm社区版安装包并解压 在桌面新建pyc......

小芯片
今天
54
0
Vue造轮子-tab组件(中)

1. 如果给一个标签一个class,标签本身又有class,vue是默认会合并的。只有两个属性是这样一个是class,一个是style。这样就比较好改样式。 <g-tabs-head class="red"></g-tabs> 2. 组件的...

ories
昨天
59
0
Windows 版本 Anaconda 配置加速源安装软件

C:\Users\lenovo\.condarc 首先安装Anaconda最新版本。 其次添加安装目录到环境变量。文本为 C:\ProgramData\Anaconda3\Library\bin 运行 conda 命令在 Windows 用户下生成文件 .conda...

白豆腐徐长卿
昨天
232
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部