黑马程序员技术交流社区

标题: 关于快速排序的代码及原理 [打印本页]

---

作者: 杨志男    时间: 2012-9-25 15:01
标题: 关于快速排序的代码及原理
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);
        }

}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2