龙书的P431中有一个quicksort的不含嵌套函数及高阶函数的例子,我实现的时候居然错了,真的太菜了。虽然整体的思想都是让问题退化为解决枢轴两边的快排问题,但是在处理细节上是不同的。虽然基础,但是好记性不如烂笔头,还是硬着头皮写下吧>_<
方法一
public class Qs { private int[] numbers; private int number; public void sort(int[] values) { if (values == null || values.length < 2) { return; } this.numbers = values; number = values.length; quicksort(0, number - 1); } int partition(int low, int high) { int pivotKey = numbers[low]; while (low <= high) { while (numbers[low] < pivotKey) { low++; } while (numbers[high] > pivotKey) { high--; } if (low <= high) { exchange(low, high); low++; high--; } } return low; } private void quicksort(int low, int high) { int i = partition(low, high); if (low < i - 1) { quicksort(low, i - 1); } if (high > i) { quicksort(i, high); } } private void exchange(int i, int j) { int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } public static void main(String[] args) { int[] arr = { -4, 4, 3, -1, 2, 1, -3, -2, 0 }; Qs qs = new Qs(); qs.sort(arr); for (int ele : arr) System.out.print(ele + " "); } }
方法二(修改方法一中的partition和quicksort)
int partition(int low, int high) { int pivotKey = numbers[low]; while (low < high) { while (low < high && numbers[high] >= pivotKey) high--; exchange(low, high); while (low < high && numbers[low] <= pivotKey) low++; exchange(low, high); } return low; } private void quicksort(int low, int high) { if (low < high) { int pivotKey = partition(low, high); quicksort(low, pivotKey - 1); quicksort(pivotKey + 1, high); } }
注意细节即可,这里就不演示了。想了解一下细节的话可以加断点细细分析;或者加些aspect的信息来看一下。下面是直接用aspectj插入的一些信息:
public aspect QsAspectj { private int callDepth = -1; pointcut MethodInfo(int low,int high):call (* *(..))&&this(Qs)&&args(low,high); before(int low,int high):MethodInfo(low,high){ callDepth++; System.out.print(callDepth); for(int i = 0; i< callDepth;i++) System.out.print(" "); System.out.println(thisJoinPointStaticPart.getSignature().getName()+"("+low+", "+high+")"); } after(int low,int high):MethodInfo(low,high){ System.out.print(callDepth); for(int i = 0; i< callDepth;i++) System.out.print(" "); System.out.println(thisJoinPointStaticPart.getSignature().getName()+"("+low+", "+high+")"); callDepth--; } pointcut sortInfo():call(public void sort(int[]))&&within(Qs); Object around():sortInfo(){ long begin = System.nanoTime(); Object result = proceed(); long end = System.nanoTime(); System.out.println("total time: "+(end-begin)); return result; } before():sortInfo(){ System.out.println("*** "+thisJoinPointStaticPart.getSignature().getName()+" ***"); } after():sortInfo(){ System.out.println("*** "+thisJoinPointStaticPart.getSignature().getName()+" ***"); } }
class Quicksort { def sort(a: Array[Int]): Array[Int] = if (a.length < 2) a else { val pivot = a(a.length / 2) sort(a filter (pivot >)) ++ (a filter (pivot ==)) ++ sort(a filter (pivot <)) } } object Quicksort extends Application { val qs = new Quicksort val a = Array(-4, 4, 3, -1, 2, 1, -3, -2, 0) // val start = System.nanoTime() val sorted = qs.sort(a) // val end = System.nanoTime() // println("total time: " + (end - start)) sorted.foreach(n => (print(n), print(" "))) }
貌似这样的做法不怎么高效(不妨看看运行时间),但鉴于我的scala还只勉强达到入门级,如何改进还得以后再说。
Tue, 17 Jul 2012 23:09:12 +0800
好长。。。。。。。。
Fri, 03 Aug 2012 10:24:55 +0800
"不含嵌套函数及高阶函数"这是什么意思? 快排不就是10行的事么= =
Fri, 17 Aug 2012 17:49:29 +0800
@Craynic: 那句话不是重点,这篇文章没写完呢,另外我只打算写成科普文;和行数没关系,一行也可以搞定嘛>.<
Wed, 03 Jan 2024 01:40:24 +0800
Manufacturers should focus on improving the durability of slots. เว็บตรง แตกง่าย
Thu, 04 Jan 2024 14:25:42 +0800
Whoa! These web slots are on another level. What's the secret behind their success. สล็อตเว็บใหญ่ สุด
Mon, 15 Jan 2024 14:20:31 +0800
Benefit basically prime quality things - you can comprehend them all inside: รวมสล็อตทุกค่าย
Tue, 16 Jan 2024 19:31:10 +0800
Good subject, comparative writings are I don't know whether they are on a par with your work out. เกมส์ไพ่ป๊อกเด้ง
Wed, 17 Jan 2024 01:42:50 +0800
This is a great article, Given such a great amount of information in it, These kind of articles keeps the clients enthusiasm for the site, and continue sharing more ... good fortunes. เว็บสล็อตโรม่า
Thu, 01 Feb 2024 23:27:31 +0800
I comprehend this section. I understand You put an a large number of battle to establish this story. I appreciate your procedure. concierge doctor