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

网友投稿 249 2023-07-18


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

快速排序算法概念

快速排序一般基于递归实现。其思路是这样的：

1.选定一个合适的值（理想情况中值最好，但实现中一般使用数组第一个值）,称为“枢轴”(pivot)。

2.基于这个值，将数组分为两部分，较小的分在左边，较大的分在右边。

3.可以肯定，如此一轮下来，这个枢轴的位置一定在最终位置上。

4.对两个子数组分别重复上述过程，直到每个数组只有一个元素。

5.排序完成。

基本实现方式：

public static void quickSort(int[] arr){

qsort(arr, 0, arr.length-1);

}

private static void qsort(int[] arr, int low, int high){

if (low < high){

int pivot=partition(arr, low, high); //将数组分为两部分

qsort(arr, low, pivot-1); //递归排序左子数组

qsort(arr, pivot+1, high); //递归排序右子数组

}

}

private static int partition(int[] arr, int low, int high){

int pivot = arr[low]; //枢轴记录

while (low

while (low=pivot) --high;

arr[low]=arr[high]; //交换比枢轴小的记录到左端

while (low

arr[high] = arr[low]; //交换比枢轴小的记录到右端

}

//扫描完成，枢轴到位

arr[low] = pivot;

//返回的是枢轴的位置

return low;

}

使用泛型实现快排算法

下面设计一个QuickSort类，包含了静态函数sort()，可以对任意类型数组进行排序。如果为对象类型数组，则该对象类型必须实现Comparable接口，这样才能使用compareTo函数进行比较。

使用了最基本的快排算法，没有进行优化处理。

源代码如下：

import java.util.LinkedList;

import java.util.List;

import java.util.ListIterator;

import java.util.Random;

public class QuickSort {

@SuppressWarnings("unchecked")

//对上述快排函数原型修改，使其可以对任意对象类型数组进行排序。这个函数为内部使用，外部排序函数接口为sort()，sort函数要求对象必须实现Comparable接口，可以提供编译时类型检测，见后文。

private static void quickSort(Object[] in,int begin, int end) {

if( begin == end || begin == (end-1) ) return;

Object p = in[begin];

int a = begin +1;

int b = a;

for( ; b < end; b++) {

//该对象类型数组必须实现Comparable接口，这样才能使用compareTo函数进行比较

if( ((Comparable)in[b]).compareTo(p) < 0) {

if(a == b){a++; continue;}

Object temp = in[a];

in[a] = in[b];

in[b] = temp;

a++;

}

}

in[begin] = in[a-1];

in[a-1] = p;

if( a-1 > begin){

quickSort(in,begin, a);

}

if( end-1 > a ) {

quickSort(in,a, end);

}

return;

}

//使用泛型，对任意对象数组排序，该对象类型数组必须实现Comparable接口

public static > void sort(T[] input){

quickSort(input,0,input.length);

}

//添加对List对象进行排序的功能，参考了Java中的Java.util.Collections类的sort()函数

public static > void sort(List list){

Object[] t = list.toArray();//将列表转换为数组

quickSort(t,0,t.length); //对数组进行排序

//数组排序完成后再写回到列表中

ListIterator i = list.listIterator();

for (int j=0; j

i.next();

i.set((T)t[j]);

}

}

//由于Java中原始数据类型（int、double、byte等）无法使用泛型，所以只能使用函数重载机制实现对这些原始类型数组（int[]、double[]、byte[]等）的排序。这里为了共用同一个排序函数，利用原始类型的(AutoBoxing，UnBoxing)机制将其封装为对应对象类型，组成新的对象数组，排序后再解封装，这样的缺点是需要额外的转换步骤、额外的空间保存封装后的数组。另一种方式是将排序代码复制到各个重载函数中，官方API中的Java.util.Arrays这个类中的sort()函数就是使用这种方法，可以从Arrays类的源代码看出。

public static void sort(int[] input){

Integer[] t = new Integer[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];//封装

}

quickSort(t,0,t.length);//排序

for(int i = 0; i < input.length; i++){

input[i] = t[i];//解封装

}

}

//double[]数组的重载函数

public static void sort(double[] input){

Double[] t = new Double[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//byte[]数组的重载函数

public static void sort(byte[] input){

Byte[] t = new Byte[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//short[]数组的重载函数

public static void sort(short[] input){

Short[] t = new Short[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//char[]数组的重载函数

public static void sort(char[] input){

Character[] t = new Character[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//float[]数组的重载函数

public static void sort(float[] input){

Float[] t = new Float[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//测试用的main函数

public static void main(String[] args) {

//生产一个随机数组成的int[]数组，用来测试

int LEN = 10;

int[] input = new int[LEN];

Random r = new Random();

System.out.print("int[] before sorting: ");

for(int i = 0; i < input.length; i++) {

input[i] = r.nextInt(10*LEN);

System.out.print(input[i] + " ");

}

System.out.println();

System.out.print("int[] after sorting: ");

sort(input);

for(int i : input) {

System.out.print(i + " ");

}

System.out.println();

//生成一个字符串数组，用来测试

String[] s = new String[]{"b","a","e","d","f","c"};

System.out.print("String[] before sorting: ");

for(int i = 0; i < s.length; i++) {

System.out.print(s[i] + " ");

}

System.out.println();

System.out.print("String[] after sorting: ");

sort(s);

for(int i = 0; i < s.length; i++) {

System.out.print(s[i] + " ");

}

System.out.println();

//生成一个字符串列表，用来测试

List l = new LinkedList();

s = new String[]{"b","a","e","d","f","c"};

System.out.print("LinkedList before sorting: ");

for (int j=0; j

l.add(s[j]);

System.out.print(s[j] + " ");

}

System.out.println();

sort(l);

System.out.print("LinkedList after sorting: ");

for (String ts : l) {

System.out.print(ts + " ");

}

System.out.println();

}

}

运行main函数测试，从输出可以看出QuicsGTkmxsTLkSort类工作正常：

int[] before sorting: 65 48 92 26 3 8 59 21 16 45

int[] after sorting: 3 8 16 21 26 45 48 59 65 92

String[] before sorting: b a e d f c

String[] after sorting: a b c d e f

LinkedList before sorting: b a e d f c

LinkedList after sorting: a b c d e f

while (low=pivot) --high;

arr[low]=arr[high]; //交换比枢轴小的记录到左端

while (low

arr[high] = arr[low]; //交换比枢轴小的记录到右端

}

//扫描完成，枢轴到位

arr[low] = pivot;

//返回的是枢轴的位置

return low;

}

使用泛型实现快排算法

下面设计一个QuickSort类，包含了静态函数sort()，可以对任意类型数组进行排序。如果为对象类型数组，则该对象类型必须实现Comparable接口，这样才能使用compareTo函数进行比较。

使用了最基本的快排算法，没有进行优化处理。

源代码如下：

import java.util.LinkedList;

import java.util.List;

import java.util.ListIterator;

import java.util.Random;

public class QuickSort {

@SuppressWarnings("unchecked")

//对上述快排函数原型修改，使其可以对任意对象类型数组进行排序。这个函数为内部使用，外部排序函数接口为sort()，sort函数要求对象必须实现Comparable接口，可以提供编译时类型检测，见后文。

private static void quickSort(Object[] in,int begin, int end) {

if( begin == end || begin == (end-1) ) return;

Object p = in[begin];

int a = begin +1;

int b = a;

for( ; b < end; b++) {

//该对象类型数组必须实现Comparable接口，这样才能使用compareTo函数进行比较

if( ((Comparable)in[b]).compareTo(p) < 0) {

if(a == b){a++; continue;}

Object temp = in[a];

in[a] = in[b];

in[b] = temp;

a++;

}

}

in[begin] = in[a-1];

in[a-1] = p;

if( a-1 > begin){

quickSort(in,begin, a);

}

if( end-1 > a ) {

quickSort(in,a, end);

}

return;

}

//使用泛型，对任意对象数组排序，该对象类型数组必须实现Comparable接口

public static > void sort(T[] input){

quickSort(input,0,input.length);

}

//添加对List对象进行排序的功能，参考了Java中的Java.util.Collections类的sort()函数

public static > void sort(List list){

Object[] t = list.toArray();//将列表转换为数组

quickSort(t,0,t.length); //对数组进行排序

//数组排序完成后再写回到列表中

ListIterator i = list.listIterator();

for (int j=0; j

i.next();

i.set((T)t[j]);

}

}

//由于Java中原始数据类型（int、double、byte等）无法使用泛型，所以只能使用函数重载机制实现对这些原始类型数组（int[]、double[]、byte[]等）的排序。这里为了共用同一个排序函数，利用原始类型的(AutoBoxing，UnBoxing)机制将其封装为对应对象类型，组成新的对象数组，排序后再解封装，这样的缺点是需要额外的转换步骤、额外的空间保存封装后的数组。另一种方式是将排序代码复制到各个重载函数中，官方API中的Java.util.Arrays这个类中的sort()函数就是使用这种方法，可以从Arrays类的源代码看出。

public static void sort(int[] input){

Integer[] t = new Integer[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];//封装

}

quickSort(t,0,t.length);//排序

for(int i = 0; i < input.length; i++){

input[i] = t[i];//解封装

}

}

//double[]数组的重载函数

public static void sort(double[] input){

Double[] t = new Double[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//byte[]数组的重载函数

public static void sort(byte[] input){

Byte[] t = new Byte[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//short[]数组的重载函数

public static void sort(short[] input){

Short[] t = new Short[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//char[]数组的重载函数

public static void sort(char[] input){

Character[] t = new Character[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//float[]数组的重载函数

public static void sort(float[] input){

Float[] t = new Float[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//测试用的main函数

public static void main(String[] args) {

//生产一个随机数组成的int[]数组，用来测试

int LEN = 10;

int[] input = new int[LEN];

Random r = new Random();

System.out.print("int[] before sorting: ");

for(int i = 0; i < input.length; i++) {

input[i] = r.nextInt(10*LEN);

System.out.print(input[i] + " ");

}

System.out.println();

System.out.print("int[] after sorting: ");

sort(input);

for(int i : input) {

System.out.print(i + " ");

}

System.out.println();

//生成一个字符串数组，用来测试

String[] s = new String[]{"b","a","e","d","f","c"};

System.out.print("String[] before sorting: ");

for(int i = 0; i < s.length; i++) {

System.out.print(s[i] + " ");

}

System.out.println();

System.out.print("String[] after sorting: ");

sort(s);

for(int i = 0; i < s.length; i++) {

System.out.print(s[i] + " ");

}

System.out.println();

//生成一个字符串列表，用来测试

List l = new LinkedList();

s = new String[]{"b","a","e","d","f","c"};

System.out.print("LinkedList before sorting: ");

for (int j=0; j

l.add(s[j]);

System.out.print(s[j] + " ");

}

System.out.println();

sort(l);

System.out.print("LinkedList after sorting: ");

for (String ts : l) {

System.out.print(ts + " ");

}

System.out.println();

}

}

运行main函数测试，从输出可以看出QuicsGTkmxsTLkSort类工作正常：

int[] before sorting: 65 48 92 26 3 8 59 21 16 45

int[] after sorting: 3 8 16 21 26 45 48 59 65 92

String[] before sorting: b a e d f c

String[] after sorting: a b c d e f

LinkedList before sorting: b a e d f c

LinkedList after sorting: a b c d e f

arr[high] = arr[low]; //交换比枢轴小的记录到右端

}

//扫描完成，枢轴到位

arr[low] = pivot;

//返回的是枢轴的位置

return low;

}

使用泛型实现快排算法

下面设计一个QuickSort类，包含了静态函数sort()，可以对任意类型数组进行排序。如果为对象类型数组，则该对象类型必须实现Comparable接口，这样才能使用compareTo函数进行比较。

使用了最基本的快排算法，没有进行优化处理。

源代码如下：

import java.util.LinkedList;

import java.util.List;

import java.util.ListIterator;

import java.util.Random;

public class QuickSort {

@SuppressWarnings("unchecked")

//对上述快排函数原型修改，使其可以对任意对象类型数组进行排序。这个函数为内部使用，外部排序函数接口为sort()，sort函数要求对象必须实现Comparable接口，可以提供编译时类型检测，见后文。

private static void quickSort(Object[] in,int begin, int end) {

if( begin == end || begin == (end-1) ) return;

Object p = in[begin];

int a = begin +1;

int b = a;

for( ; b < end; b++) {

//该对象类型数组必须实现Comparable接口，这样才能使用compareTo函数进行比较

if( ((Comparable)in[b]).compareTo(p) < 0) {

if(a == b){a++; continue;}

Object temp = in[a];

in[a] = in[b];

in[b] = temp;

a++;

}

}

in[begin] = in[a-1];

in[a-1] = p;

if( a-1 > begin){

quickSort(in,begin, a);

}

if( end-1 > a ) {

quickSort(in,a, end);

}

return;

}

//使用泛型，对任意对象数组排序，该对象类型数组必须实现Comparable接口

public static > void sort(T[] input){

quickSort(input,0,input.length);

}

//添加对List对象进行排序的功能，参考了Java中的Java.util.Collections类的sort()函数

public static > void sort(List list){

Object[] t = list.toArray();//将列表转换为数组

quickSort(t,0,t.length); //对数组进行排序

//数组排序完成后再写回到列表中

ListIterator i = list.listIterator();

for (int j=0; j

i.next();

i.set((T)t[j]);

}

}

//由于Java中原始数据类型（int、double、byte等）无法使用泛型，所以只能使用函数重载机制实现对这些原始类型数组（int[]、double[]、byte[]等）的排序。这里为了共用同一个排序函数，利用原始类型的(AutoBoxing，UnBoxing)机制将其封装为对应对象类型，组成新的对象数组，排序后再解封装，这样的缺点是需要额外的转换步骤、额外的空间保存封装后的数组。另一种方式是将排序代码复制到各个重载函数中，官方API中的Java.util.Arrays这个类中的sort()函数就是使用这种方法，可以从Arrays类的源代码看出。

public static void sort(int[] input){

Integer[] t = new Integer[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];//封装

}

quickSort(t,0,t.length);//排序

for(int i = 0; i < input.length; i++){

input[i] = t[i];//解封装

}

}

//double[]数组的重载函数

public static void sort(double[] input){

Double[] t = new Double[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//byte[]数组的重载函数

public static void sort(byte[] input){

Byte[] t = new Byte[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//short[]数组的重载函数

public static void sort(short[] input){

Short[] t = new Short[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//char[]数组的重载函数

public static void sort(char[] input){

Character[] t = new Character[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//float[]数组的重载函数

public static void sort(float[] input){

Float[] t = new Float[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//测试用的main函数

public static void main(String[] args) {

//生产一个随机数组成的int[]数组，用来测试

int LEN = 10;

int[] input = new int[LEN];

Random r = new Random();

System.out.print("int[] before sorting: ");

for(int i = 0; i < input.length; i++) {

input[i] = r.nextInt(10*LEN);

System.out.print(input[i] + " ");

}

System.out.println();

System.out.print("int[] after sorting: ");

sort(input);

for(int i : input) {

System.out.print(i + " ");

}

System.out.println();

//生成一个字符串数组，用来测试

String[] s = new String[]{"b","a","e","d","f","c"};

System.out.print("String[] before sorting: ");

for(int i = 0; i < s.length; i++) {

System.out.print(s[i] + " ");

}

System.out.println();

System.out.print("String[] after sorting: ");

sort(s);

for(int i = 0; i < s.length; i++) {

System.out.print(s[i] + " ");

}

System.out.println();

//生成一个字符串列表，用来测试

List l = new LinkedList();

s = new String[]{"b","a","e","d","f","c"};

System.out.print("LinkedList before sorting: ");

for (int j=0; j

l.add(s[j]);

System.out.print(s[j] + " ");

}

System.out.println();

sort(l);

System.out.print("LinkedList after sorting: ");

for (String ts : l) {

System.out.print(ts + " ");

}

System.out.println();

}

}

运行main函数测试，从输出可以看出QuicsGTkmxsTLkSort类工作正常：

int[] before sorting: 65 48 92 26 3 8 59 21 16 45

int[] after sorting: 3 8 16 21 26 45 48 59 65 92

String[] before sorting: b a e d f c

String[] after sorting: a b c d e f

LinkedList before sorting: b a e d f c

LinkedList after sorting: a b c d e f

i.next();

i.set((T)t[j]);

}

}

//由于Java中原始数据类型（int、double、byte等）无法使用泛型，所以只能使用函数重载机制实现对这些原始类型数组（int[]、double[]、byte[]等）的排序。这里为了共用同一个排序函数，利用原始类型的(AutoBoxing，UnBoxing)机制将其封装为对应对象类型，组成新的对象数组，排序后再解封装，这样的缺点是需要额外的转换步骤、额外的空间保存封装后的数组。另一种方式是将排序代码复制到各个重载函数中，官方API中的Java.util.Arrays这个类中的sort()函数就是使用这种方法，可以从Arrays类的源代码看出。

public static void sort(int[] input){

Integer[] t = new Integer[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];//封装

}

quickSort(t,0,t.length);//排序

for(int i = 0; i < input.length; i++){

input[i] = t[i];//解封装

}

}

//double[]数组的重载函数

public static void sort(double[] input){

Double[] t = new Double[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//byte[]数组的重载函数

public static void sort(byte[] input){

Byte[] t = new Byte[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//short[]数组的重载函数

public static void sort(short[] input){

Short[] t = new Short[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//char[]数组的重载函数

public static void sort(char[] input){

Character[] t = new Character[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//float[]数组的重载函数

public static void sort(float[] input){

Float[] t = new Float[input.length];

for(int i = 0; i < input.length; i++){

t[i] = input[i];

}

quickSort(t,0,t.length);

for(int i = 0; i < input.length; i++){

input[i] = t[i];

}

}

//测试用的main函数

public static void main(String[] args) {

//生产一个随机数组成的int[]数组，用来测试

int LEN = 10;

int[] input = new int[LEN];

Random r = new Random();

System.out.print("int[] before sorting: ");

for(int i = 0; i < input.length; i++) {

input[i] = r.nextInt(10*LEN);

System.out.print(input[i] + " ");

}

System.out.println();

System.out.print("int[] after sorting: ");

sort(input);

for(int i : input) {

System.out.print(i + " ");

}

System.out.println();

//生成一个字符串数组，用来测试

String[] s = new String[]{"b","a","e","d","f","c"};

System.out.print("String[] before sorting: ");

for(int i = 0; i < s.length; i++) {

System.out.print(s[i] + " ");

}

System.out.println();

System.out.print("String[] after sorting: ");

sort(s);

for(int i = 0; i < s.length; i++) {

System.out.print(s[i] + " ");

}

System.out.println();

//生成一个字符串列表，用来测试

List l = new LinkedList();

s = new String[]{"b","a","e","d","f","c"};

System.out.print("LinkedList before sorting: ");

for (int j=0; j

l.add(s[j]);

System.out.print(s[j] + " ");

}

System.out.println();

sort(l);

System.out.print("LinkedList after sorting: ");

for (String ts : l) {

System.out.print(ts + " ");

}

System.out.println();

}

}

运行main函数测试，从输出可以看出QuicsGTkmxsTLkSort类工作正常：

int[] before sorting: 65 48 92 26 3 8 59 21 16 45

int[] after sorting: 3 8 16 21 26 45 48 59 65 92

String[] before sorting: b a e d f c

String[] after sorting: a b c d e f

LinkedList before sorting: b a e d f c

LinkedList after sorting: a b c d e f

l.add(s[j]);

System.out.print(s[j] + " ");

}

System.out.println();

sort(l);

System.out.print("LinkedList after sorting: ");

for (String ts : l) {

System.out.print(ts + " ");

}

System.out.println();

}

}

运行main函数测试，从输出可以看出QuicsGTkmxsTLkSort类工作正常：

int[] before sorting: 65 48 92 26 3 8 59 21 16 45

int[] after sorting: 3 8 16 21 26 45 48 59 65 92

String[] before sorting: b a e d f c

String[] after sorting: a b c d e f

LinkedList before sorting: b a e d f c

LinkedList after sorting: a b c d e f


版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：方法 算法 Java 函数 接口
上一篇:举例讲解Java设计模式编程中模板方法模式的运用实例
下一篇:Bootstrap嵌入jqGrid，使你的table牛逼起来
相关文章

 发表评论

暂时没有评论，来抢沙发吧~