java 算法基础之二快速排序算法

http://www.cnblogs.com/hexiaochun/archive/2012/09/03/2668324.html

java 算法基础之二快速排序算法

所谓的快速排序的思想就是,首先把数组的第一个数拿出来做为一个key,在前后分别设置一个i,j做为标识,然后拿这个key对这个数组从后面往前遍历,及j--,直到找到第一个小于这个key的那个数,然后交换这两个值,交换完成后,我们拿着这个key要从i往后遍历了,及i++;一直循环到i=j结束,当这里结束后,我们会发现大于这个key的值都会跑到这个key的后面,不是的话就可能你写错了,小于这个key的就会跑到这个值的前面;然后我们对这个分段的数组再时行递归调用就可以完成整个数组的排序。

用图形法表示由下:

这样就以key分为了两个段,我们把这两个段再递进去就可以解决问题了

实现代码由下:

 1 package com.quick;
 2
 3 public class quick {
 4     public void quick_sort(int[] arrays, int lenght) {
 5         if (null == arrays || lenght < 1) {
 6             System.out.println("input error!");
 7             return;
 8         }
 9         _quick_sort(arrays, 0, lenght - 1);
10     }
11
12     public void _quick_sort(int[] arrays, int start, int end) {
13         if(start>=end){
14             return;
15         }
16
17         int i = start;
18         int j = end;
19         int value = arrays[i];
20         boolean flag = true;
21         while (i != j) {
22             if (flag) {
23                 if (value > arrays[j]) {
24                     swap(arrays, i, j);
25                     flag=false;
26
27                 } else {
28                     j--;
29                 }
30             }else{
31                 if(value<arrays[i]){
32                     swap(arrays, i, j);
33                     flag=true;
34                 }else{
35                     i++;
36                 }
37             }
38         }
39         snp(arrays);
40         _quick_sort(arrays, start, j-1);
41         _quick_sort(arrays, i+1, end);
42
43     }
44
45     public void snp(int[] arrays) {
46         for (int i = 0; i < arrays.length; i++) {
47             System.out.print(arrays[i] + " ");
48         }
49         System.out.println();
50     }
51
52     private void swap(int[] arrays, int i, int j) {
53         int temp;
54         temp = arrays[i];
55         arrays[i] = arrays[j];
56         arrays[j] = temp;
57     }
58
59     public static void main(String args[]) {
60         quick q = new quick();
61         int[] a = { 49, 38, 65,12,45,5 };
62         q.quick_sort(a,6);
63     }
64
65 }

找一个博客做自己的女朋友,不管你跟她说什么她都帮你记录,这是多么幸福的一件事啊。如果有女生能做到这点,赶尽娶回家吧!

分类: 数据结构与算法

时间: 2024-11-17 21:48:28

java 算法基础之二快速排序算法的相关文章

详解Java中使用泛型实现快速排序算法的方法_java

快速排序算法概念快速排序一般基于递归实现.其思路是这样的: 1.选定一个合适的值(理想情况中值最好,但实现中一般使用数组第一个值),称为"枢轴"(pivot). 2.基于这个值,将数组分为两部分,较小的分在左边,较大的分在右边. 3.可以肯定,如此一轮下来,这个枢轴的位置一定在最终位置上. 4.对两个子数组分别重复上述过程,直到每个数组只有一个元素. 5.排序完成. 基本实现方式: public static void quickSort(int[] arr){ qsort(arr,

Java语法基础(二)----运算符

一.运算符: 运算符包括下面几种: 算术运算符 赋值运算符 比较运算符 逻辑运算符 位运算符 三目运算符 最不常用的是位运算符,但也是最接近计算机底层的. 1.算术运算符 (1)+的几种用法:加法.正数.字符串连接符 (2)除法的时候要注意一个问题:整数相除,只能得到整数.要想得到小数,可以将数据自身*1.0,即将数据自身先转换为浮点型.   2.赋值运算符 符号     =    +=  -=   *=  /=   %= 注:=为基本的赋值运算符,其他的为扩展的赋值运算符 面试题: (1)sh

Java多线程基础总结二: Thread

对于Thread来说只想说两个方法,一个是setDaemon(false|true),另一个是join().首先说说守护线程,这么东西是干什么用的?对于 Java应用我们都知道main方法是入口,它的运行代表着主线程开始工作了,我们也知道JVM里面有垃圾回收器的存在使得我们放心让main飞 奔,然而这背后的故事是垃圾回收线程作为守护着主线程的守护线程默默的付出着.很像那个啥啊,呵呵.令人发指的是main这个畜生背后 其实有好几个守护线程默默的付出!当然如果硬是要把守护线程比做女人,非守护线程比做

图文讲解Java中实现quickSort快速排序算法的方法_java

相对冒泡排序.选择排序等算法而言,快速排序的具体算法原理及实现有一定的难度.为了更好地理解快速排序,我们仍然以举例说明的形式来详细描述快速排序的算法原理.在前面的排序算法中,我们以5名运动员的身高排序问题为例进行讲解,为了更好地体现快速排序的特点,这里我们再额外添加3名运动员.实例中的8名运动员及其身高信息详细如下(F.G.H为新增的运动员): A(181).B(169).C(187).D(172).E(163).F(191).G(189).H(182) 在前面的排序算法中,这些排序都是由教练主

java实现快速排序算法_java

1.算法概念. 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出. 2.算法思想. 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 3.实现思路. ①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,-,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于

Java对数组实现选择排序算法的实例详解_java

一. 算法描述    选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成. 以下面5个无序的数据为例: 56 12 80 91 20(文中仅细化了第一趟的选择过程) 第1趟:12 56 80 91 20 第2趟:12 20 80 91 56 第3趟:12 20 56 91 80 第4趟:

快速排序算法的C++实现

快速排序基本特性 时间复杂度:O(n*lgn) 最坏:O(n^2) 空间复杂度:最好情况下:O(lgn),最坏情况:O(n),平均情况:O(lgn) 不稳定. 关于快速排序的空间复杂度,谢谢@命运他爹 同学指正.详述一下. 快速排序由于每次递归的时候会占用一个空间返回中间数位置,所以一次递归的空间复杂度为O(1). 最好情况和最坏情况下的递归深度为O(lgn),相应的空间复杂度就是O(lgn) 最坏情况下的递归深度为O(n),空间复杂度为O(n). 算法 QUICKSORT(A, p, r) i

go语言实现并行的快速排序算法?

问题描述 go语言实现并行的快速排序算法? 如题所示,使用go语言编程实现并行的快速排序算法,请大神们帮帮忙~ 解决方案 使用go实现快速排序在Google已经找到答案. 解决方案二: 快速排序算法的C++实现快速排序算法C++实现快速排序算法的非递归实现 解决方案三: 并行,快排本身就是拆开成一个个子任务.然后子任务放到各个go中

逐步讲解快速排序算法及C#版的实现示例_C#教程

算法思想快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序.它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod). 该方法的基本思想是: 1.先从数列中取出一个数作为基准数. 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边. 3.再对左右区间重复第二步,直到各区间只有一个数. 虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤.因此我的对快速排序作了进一步的说明:挖坑填数+分治法: 先