编译原理学习笔记02
编译原理学习笔记03

quicksort探究1

nonoob posted @ Tue, 17 Jul 2012 21:57:43 +0800 in Programming , 1283 readers

龙书的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()+" ***");
	}
}
为了无聊起见,顺便插一段scala的实现,剽窃自这里
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还只勉强达到入门级,如何改进还得以后再说。

Avatar_small
依云 said:
Tue, 17 Jul 2012 23:09:12 +0800

好长。。。。。。。。

Avatar_small
Craynic said:
Fri, 03 Aug 2012 10:24:55 +0800

"不含嵌套函数及高阶函数"这是什么意思? 快排不就是10行的事么= =

Avatar_small
nonoob said:
Fri, 17 Aug 2012 17:49:29 +0800

@Craynic: 那句话不是重点,这篇文章没写完呢,另外我只打算写成科普文;和行数没关系,一行也可以搞定嘛>.<


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter