文档章节

快速排序

无名猪
 无名猪
发布于 2017/01/18 16:02
字数 1058
阅读 1
收藏 0

快速排序(Quicksort)是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。(摘自百度)

不难看出,快速排序也是一种分治算法(divide and conquer),将问题分解成两部分,然后再分别使用递归解决两小部分。下面就来演示快速排序是如何排序的(升序排列):

假定待排序数组a[]如下:

0 1 2 3 4 5 6 7 8
66 45 67 23 77 3 55 88 78

 

1.选取一个数为基准数Key(一般选择数组第一个数,本处为66)

2.将大于Key(66)的数放到Key右边,小于它的放到左边。

  i=0;j=8,Key=a[0]=66

(1)从右往左,找到比Key小的数,放入a[i]的位置,并将i加1。当j=6时,55<66,执行a[0]=a[6],i++;

0 1 2 3 4 5 6 7 8
55 45 67 23 77 3 55 88 78

(2)从左往右,找到比Key大的数,放入a[j]的位置,并将j减1。当i=2时,67>66,执行a[6]=a[2],j--;

0 1 2 3 4 5 6 7 8
55 45 67 23 77 3 67 88 78

(3).重复(1),(2)步,从右往左,找到比Key小的数,放入a[i]的位置,并将i加1。当j=5时,3<66,执行a[2]=a[6],i++;

0 1 2 3 4 5 6 7 8
55 45 3 23 77 3 67 88 78

从左往右,找到比Key大的数,放入a[j]的位置,并将j减1。当i=4时,77>66,执行a[5]=a[4],j--;(完成后i=4,j=4)

0 1 2 3 4 5 6 7 8
55 45 3 23 77 77 67 88 78

(4)当i==j时终止循环,并将Key放入a[i]中,a[i]=Key;

0 1 2 3 4 5 6 7 8
55 45 3 23 66 77 67 88 78

完成后,发现在Key左边的数都比Key小,右边的数都比Key大。

3.进行递归,分别递归a[0]到a[3],以及a[5]到a[8]的数组。如有必要可以再次进行递归,直到数组中只有一个整数,此时大功告成。

 

JAVA代码简单示意如下:

package algorithm;
//divide and conquer
//快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
//该方法的基本思想是:
//1.先从数列中取出一个数作为基准数。
//2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
//3.再对左右区间重复第二步,直到各区间只有一个数。
public class QuickSort {
   public static void main(String [] args){
	   int arr[]=new int[]{66,45,67,23,77,3,55,88,78};	   
	   quick_sort1(arr,0,arr.length-1);
	   for(int i=0;i<arr.length;i++){
    	   System.out.println(arr[i]);
       }
   }
   
   static void quick_sort1(int s[], int l, int r)  
   {  
       if (l < r)  
       {  
           int i = AdjustArray(s, l, r);//调整s[]  
           quick_sort1(s, l, i - 1); // 递归调用   
           quick_sort1(s, i + 1, r);  
       }     
   }  
   
 static   int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置  
   {  
       int i = l, j = r;  
       int x = s[l]; //s[l]即s[i]就是本次的Key
       while (i < j)  
       {  
           // 从右向左找小于x的数来放入s[i]  
           while(i < j && s[j] >= x)   
               j--;    
           if(i < j)   
           {  
               s[i] = s[j];
               i++;
           }
           // 从左向右找大于或等于x的数来放入s[j]  
           while(i < j && s[i] < x)  
               i++;    
           if(i < j)   
           {  
               s[j] = s[i]; 
               j--;  
           }  
       }  
       //退出时,i等于j。将x填到Key位置中。  
       s[i] = x;  
     
       return i;  
   }  
}

以上代码还有优化空间。

可以发现以上排序算法存在几个不确定因素,可以自己思考思考。

1、如果选取的第一个数即Key是数组中最大的,或者最小的会怎么样?是不是该随机选取一个Key?

2、如果数组中有几个相同的数字,它们的位置会不会发生变化?

 

© 著作权归作者所有

上一篇: 堆排序
下一篇: ThreadLocal详解
无名猪
粉丝 1
博文 17
码字总数 9618
作品 0
南京
程序员
私信 提问

暂无文章

Java 文件类操作API与IO编程基础知识

阅读目录: https://www.w3cschool.cn/java/java-io-file.html Java 文件 Java 文件 Java 文件操作 Java 输入流 Java 输入流 Java 文件输入流 Java 缓冲输入流 Java 推回输入流 Java 数据输入...

boonya
44分钟前
5
0
SDKMAN推荐一个好

是在大多数基于Unix的系统上管理多个软件开发工具包的并行版本的工具。它提供了一个方便的命令行界面(CLI)和API来安装,切换,删除和列出sdk相关信息。以下是一些特性: By Developers, fo...

hotsmile
今天
9
0
什么是 HDFS

是什么? HDFS 是基于 Java 的分布式文件系统,允许您在 Hadoop 集群中的多个节点上存储大量数据。 起源: 单机容量往往无法存储大量数据,需要跨机器存储。统一管理分布在集群上的文件系统称...

Garphy
今天
7
0
一起来学Java8(四)——复合Lambda

在一起来学Java8(二)——Lambda表达式中我们学习了Lambda表达式的基本用法,现在来了解下复合Lambda。 Lambda表达式的的书写离不开函数式接口,复合Lambda的意思是在使用Lambda表达式实现函...

猿敲月下码
今天
11
0
debian10使用putty配置交换机console口

前言:Linux的推广普及,需要配合解决实际应用方能有成效! 最近强迫自己用linux进行实际工作,过程很痛苦,还好通过网络一一解决,感谢各位无私网友博客的帮助! 系统:debian10 桌面:xfc...

W_Lu
今天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部