排序算法进阶(一)——快速排序算法(基本类型与复杂类型)

发表于

      一个好的算法，不仅要高效的解决实际问题，还要以代码简介、冗余少为荣！

      排序算法进阶(一)中介绍了快速排序算法，但_它只适用于int类型的数组_，当我们实际使用中往往会设计到多种数据类型，如浮点类型、字符串类型，难道需要再为这些类型重写一个除了类型以外其他都一样的方法吗？

      不用，java的泛型类型给了我们这个便利。像我们平时经常用的List、Map、Vector，它的内部实现并不会对每一种数据类型进行适配，因为它们都使用了泛型。

      关于泛型的介绍，这里就不罗嗦了，网上多的是，这里附一篇，读者自己研究吧。

      为了将我们的排序方法改造为一个实用性更广的泛型方法，我们只需要在该方法的返回类型之前加一个<T>，将方法里的int类型换成T泛型类型即可。

      如QuickSort方法：

      改造前：

1
2
3
4
5
6
7
8
public static void QuickSort(int n[], int left, int right) {
	int mid;
	if (left < right) {
		mid = Partion(n, left, right);
		QuickSort(n, left, mid - 1);
		QuickSort(n, mid + 1, right);
	}
}

      改造后：

1
2
3
4
5
6
7
8
public static <T> void QuickSort(T n[],int left,int right){
	int mid;
	if (left < right) {
		mid = Partion(n, left, right);
		QuickSort(n, left, mid - 1);
		QuickSort(n, mid + 1, right);
	}
}

      为了让T类型之间进行比较，需要实现Comapable接口，因此上述方法得改为：

1
2
3
4
5
6
7
8
public static <T extends Comparable<T>> void QuickSort(T n[],int left,int right){
	int mid;
	if (left < right) {
		mid = Partion(n, left, right);
		QuickSort(n, left, mid - 1);
		QuickSort(n, mid + 1, right);
	}
}

      同样，Partion方法也类似改造：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static <T extends Comparable<T>> int Partion(T n[], int left, int right) {
	T pivot = n[left];// 也可以从n[right]开始
	while (left < right) {
		while (left < right && n[right].compareTo(pivot)>=0)
			right--;
		if (left < right) {
			n[left++] = n[right];
		}
		while (left < right && n[left].compareTo(pivot)<=0)
			left++;
		if (left < right) {
			n[right--] = n[left];
		}
		System.out.println();
	}
	n[left] = pivot;
	return left;
}

      仅仅是稍微改改，这个方法就可以应用于String类型的数组的排序了   。

1
2
String s[]={"7.0", "8.0", "1.0", "9.0", "5.0", "10.0", "3.0", "2.0", "11.0"};
QuickSort(s, 0, n.length - 1);

      然而，在实际使用过程中，并非总是那么顺心如意   。       虽然上面的String类型数组可以成功应用该排序方法，但之前传入的int[]数组在这时却不能用了   。

      如上图，该方法不识别int类型了，怎么回事？？？   
百思不得其解，只能网上去搜咯~
      一开始还以为自己泛型用得不对，以为不是那么回事。
      可是这篇文章里用得很好的，其中的display方法可以传入int、String、float类型参数，为什么我的不行呢？   
      回过头来自习对比一下两者的用法，不难看出我们这里多了一点：extends Comparable<T>，会不会是它在搞鬼呢？   
      顿时间突然记起来我们平时使用List、ArrayList时，如果要创建整型数组，是不能用List<int>的，必须用List<Integer>才行，同理List <float>、List <double>都必须用List<Float>、List<Double>。
      为啥呢？
      网上搜了一下“java中的int与Integer的区别”，果然发现有猫腻   ，见这里，讲得很详细，只恨自己java基础掌握得不牢啊！！！   
      还有一点就是，基本数据类型是不需要实现comparable接口就可以直接进行比较的，而复杂类都实现了该接口，不信可以试一试，这里有个方法可以验证一个类是否实现了某个类接口，可以拿来判断一下Integer、Double、Float、String。（注：传递的接口名需要包括接口的全名，即包括包名的，这里应该是：java.lang.Comparable，而不是Comparable）

      到了这里，终于搞明白了，扩展的排序方法在使用时，传入的参数只能是复杂类型，基本类型就没办法了咯~