黑马程序员技术交流社区

标题: 【Java】快排Demo [打印本页]

---

作者: 残梦共飞雪    时间: 2014-3-26 12:41
标题: 【Java】快排Demo
自己写的，有需要的可以参考一下。

        public static void main(String[] args) {
                String s[] = {"think","ice","nice","devil","Aiur","win","EveryThing","Cain"};
                quickSortAsc(s, 0, s.length-1);
                System.out.println("正序："+Arrays.toString(s));
                quickSortDesc(s, 0, s.length-1);
                System.out.println("倒序："+Arrays.toString(s));
        }

       
        /**快速排序——正序
         * @param arr                数组
         * @param fromIndex        开始位置
         * @param toIndex        结束位置
         */
        public static<T extends Comparable<? super T>> void quickSortAsc(T arr[],int fromIndex,int toIndex){
                int s = fromIndex;        //s，start开始位置
                int e = toIndex;        //e，end截止位置
                T temp = arr[s];
                while(s < e){
                        //从后往前遍历，若找到比temp小的值，则将此值赋值到当前的开始位置。（temp保存着开始位置最初的值）
                        while (s < e && arr[e].compareTo(temp) >= 0) {
                                e--;
                        }
                        if(s < e){        //避免s>=e时不需要的操作
                                arr[s] = arr[e];
                        }
                        //从前往后遍历，若找到比temp大的值，则将此值赋值到当前的结束位置。
                        while (s < e && arr[s].compareTo(temp) < 0) {
                                s++;
                        }
                        if(s < e){        //避免s>=e时不需要的操作
                                arr[e] = arr[s];
                        }
                }
                arr[s] = temp;  //while循环之后，获得temp在排序后的正确位置
                if (s - fromIndex > 1) {
                        //本方法递归，完成temp之前的排序
                        quickSortAsc(arr, fromIndex, s - 1);
                }
                if (toIndex - e > 1) {
                        //本方法递归，完成temp之后的排序
                        quickSortAsc(arr, e + 1, toIndex);
                }
        }
        /**快速排序——倒序
         * @param arr                数组
         * @param fromIndex        开始位置
         * @param toIndex        结束位置
         */
        public static<T extends Comparable<? super T>> void quickSortDesc(T arr[],int fromIndex,int toIndex){
                int s = fromIndex;        //s，start开始位置
                int e = toIndex;        //e，end截止位置
                T temp = arr[s];
                while(s < e){
                        //从后往前遍历，若找到比temp大的值，则将此值赋值到开始位置。（temp保存着开始位置最初的值）
                        while (s < e && arr[e].compareTo(temp) < 0) {
                                e--;
                        }
                        if(s < e){        //避免s>=e时不需要的操作
                                arr[s] = arr[e];
                        }
                        //从前往后遍历，若找到比temp小的值，则将此值赋值到结束位置。
                        while (s < e && arr[s].compareTo(temp) >= 0) {
                                s++;
                        }
                        if(s < e){        //避免s>=e时不需要的操作
                                arr[e] = arr[s];
                        }
                }
                arr[s] = temp;  //while循环之后，获得temp在排序后的正确位置
                if (s - fromIndex > 1) {
                        //本方法递归，完成temp之前的排序
                        quickSortDesc(arr, fromIndex, s - 1);
                }
                if (toIndex - e > 1) {
                        //本方法递归，完成temp之后的排序
                        quickSortDesc(arr, e + 1, toIndex);
                }
        }

---

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

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