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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 hydrogen11 于 2015-5-23 12:36 编辑

快速排序的基本思想



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

       先看一下这幅图:(图是网上找的,方便大家理解!)




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



编写排序方法:

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

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








0 个回复

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