A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 杨志男 中级黑马   /  2012-9-25 15:01  /  1104 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

package com.itheima;

public class Test1 {

        /**
         * 第一题:排序有哪几种方法?请列举。并用JAVA实现一个快速排序。(快速排序在自学教程里好像没有讲到)
         * 排序的方法有很多,常见的有:插入排序、冒泡排序、选择排序、 快速排序、堆排序、归并排序、基数排序、希尔排序
         * 快速排序是对,冒泡排序的一种改进,其原理是:将一个数组中的元素分成两部分,其中一部分的所有元素都比另一部分小
         * 再按此方法对这两部分进行排序,以此类推。
         *
         * @author YZN
         */
        public static void main(String[] args) {

                // 声明数组
                int[] arr = { 27, 8, 57, 9, 23, 41, 65, 19, 0, 1, 2, 4, 5 };
                // 应用快速排序方法
                quickSort(arr, 0, arr.length - 1);
                // 显示排序后的数组
                for (int i = 0; i < arr.length; ++i) {
                        if (i != arr.length - 1)
                                System.out.print(arr[i] + ",");
                        else
                                System.out.println(arr[i]);
                }

        }

        /** 快速排序方法 */
        public static void quickSort(int[] arr, int lo0, int hi0) {
                int lo = lo0;
                int hi = hi0;

                if (lo >= hi)
                        return;

                // 确定指针方向的逻辑变量
                boolean transfer = true;

                while (lo != hi) {
                        if (arr[lo] > arr[hi]) {
                                // 交换数字
                                int temp = arr[lo];
                                arr[lo] = arr[hi];
                                arr[hi] = temp;
                                // 决定下标移动,还是上标移动
                                transfer = (transfer == true) ? false : true;
                        }

                        // 将指针向前或者向后移动
                        if (transfer)
                                hi--;
                        else
                                lo++;

                }

                // 将数组分开两半,确定每个数字的正确位置
                lo--;
                hi++;
                quickSort(arr, lo0, lo);
                quickSort(arr, hi, hi0);
        }

}

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马