黑马程序员技术交流社区

标题: Java实现的快速排序---QuickSort [打印本页]

---

作者: hydrogen11    时间: 2015-5-23 12:30
标题: Java实现的快速排序---QuickSort

快速排序的基本思想：

         通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。

       先看一下这幅图：（图是网上找的,方便大家理解!）

把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比，比它小不交换，比他大交换。这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。

编写排序方法：

private static void quickSort ( Integer[] array, int start, int end )
    {
        if (start < end)
        {
            int key = array[start];
            int i = start;
            for ( int j = start + 1; j < end + 1; j++ )
            {
                if (key > array[j])
                {
                    int temp = array[j];
                    array[j] = array[i + 1];
                    array[i + 1] = temp;
                    i++;
                }
            }
            array[start] = array;
            array = key;
            quickSort (array, start, i - 1);
            quickSort (array, i + 1, end);
        }

    }

编写测试方法：

public static void main(String[] args) {

                // TODO Auto-generated method stub

                Integer[] list={36,6,53,1,29,7,15,11};

                quickSort(list,0,7);

                for (Integer integer : list) {

                        System.out.print(integer+"   ");

                }

        }      

输出的结果是：1   6   7   11   15   29   36   53

这样就排序好了，快速排序是对冒泡排序的一种改进形式，在千条数据以下排序效率可能还没有冒泡、插入来的效率，但是在对更大的数据量进行排序它的效率就显而易见了。

---

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

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