本帖最后由 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 这样就排序好了,快速排序是对冒泡排序的一种改进形式,在千条数据以下排序效率可能还没有冒泡、插入来的效率,但是在对更大的数据量进行排序它的效率就显而易见了。
|