黑马程序员技术交流社区

标题: 快速排序不明白的地方 [打印本页]

---

作者: ぺsimon☆    时间: 2013-4-12 00:45
标题: 快速排序不明白的地方
今天搞了一天了,还是不懂快速排序怎么搞的,思想上大概明白是什么意思,但是代码有些看不懂
while循环是怎么跳出来的呢?下面整个代码都不是很懂,希望兄弟们帮帮忙
      //一趟快速排序，并返回用于下次分组的中间值i
        public static int onceSort(int[]arr,int begin,int end){
                int i = begin;
                int j = end;
                int key = arr[i];
               
                while(j>i){
                        while(arr[j]>key&&j>i){
                                j--;
                        }
                        if(j>i){
                                arr[i] = arr[j];
                                arr[j] = key;
                        }
                        while(arr[i]<key&&j>i){
                                i++;
                        }
                        if(j>i){
                                arr[j] = arr[i];
                                arr[i] = key;
                        }
                }
               
                return i;
        }

---

作者: 谢达    时间: 2013-4-12 10:18
快速排序采用的思想是分治思想，用一个数作为key,把数组中比key大的放右边，小的放左边,再把两边进行同样操作直到不满足条件
/**
         * @param array
         * @param p
         * @param q
         * @return 划分位置
         */
        public static int partition(int array[], int p, int q) {
                int x = array[p];

                int i = p;
                for (int j = p + 1; j <= q; j++) {
                        if (array[j] < x) {
                                i += 1;
                                swap(array, i, j);
                        }
                       

                }
                swap(array, p, i);
                return i;
        }

        // 交换数据
        public static void swap(int[] array, int m, int n) {
                int temp = array[m];
                array[m] = array[n];
                array[n] = temp;
        }

        public static void quickSort(int array[], int p, int q) {
                if (p < q) {
                        int r = partition(array, p, q);    //找到划分位置
                        quickSort(array, p, r - 1);   //对左边排序
                        quickSort(array, r + 1, q);  //对右边排序
                }
        }

---

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

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