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基础类库

4336
来自专栏无所事事者爱嘲笑

js小题目(持续更新)

1754
来自专栏Android相关

Kotlin---接口与继承

同样在Kotlin中也有接口的概念,与Java不同的是,Kotlin中的接口可以定义变量,但是不能为变量提供构造函数,也可以实现函数体,如果没有实现的函数,默认...

1623
来自专栏函数式编程语言及工具

Scalaz(18)- Monad: ReaderWriterState-可以是一种简单的编程语言

  说道FP,我们马上会联想到Monad。我们说过Monad的代表函数flatMap可以把两个运算F[A],F[B]连续起来,这样就可以从程序的意义上形成一种串...

2017
来自专栏PHP在线

php的字符串常用函数

1. str_word_count 统计单词个数 2. count_chars 得到字符串里面字符的有关情况 3. str_len 得到字符串长度,就是...

4476
来自专栏三好码农的三亩自留地

关于String你还需要知道这些细节

只要是写Java的,String肯定是经常用的,比如下面这样的代码(可能我们都写烂了)

1113
来自专栏Golang语言社区

【Go 语言社区】POJ 1047 Round and Round We Go 循环数新解

题目描述: 给定一字符串表示的高精度数,判断它是否是可循环的。如果假设字符串num的长为n,则将num从1开始乘到n,如果每次得到的结果包含的字符元素都和a是相...

35711
来自专栏北京马哥教育

Python练手题,敢来挑战吗?

这到题用到了字符串的所有字母大写和所有字母小写和字符串拼接,复制,用到的函数有 json 将列表中的内容按照指定字符连接成一个字符串,

1040
来自专栏Albert陈凯

Scala集合练习题

//创建一个List val list0 = List(1,7,9,8,0,3,5,4,6,2) //将list0中每个元素乘以10后生...

4289
来自专栏算法修养

PAT 甲级 1060 Are They Equal

1060. Are They Equal (25) 时间限制 50 ms 内存限制 65536 kB 代码长度限制 16000 B ...

2995

扫码关注云+社区

领取腾讯云代金券