比特币中国平台,话不投机三句多,千江人力
快速排序算法概念
快速排序一般基于递归实现。其思路是这样的：
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<high){
while (low<high && arr[high]>=pivot) --high;
arr[low]=arr[high]; //交换比枢轴小的记录到左端
while (low<high && arr[low]<=pivot) ++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<object>)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 <t extends comparable<? super t>> void sort(t[] input){
quicksort(input,0,input.length);
}
//添加对list对象进行排序的功能，参考了java中的java.util.collections类的sort()函数
public static <t extends comparable<? super t>> void sort(list<t> list){
object[] t = list.toarray();//将列表转换为数组
quicksort(t,0,t.length); //对数组进行排序
//数组排序完成后再写回到列表中
listiterator<t> i = list.listiterator();
for (int j=0; j<t.length; 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<string> l = new linkedlist<string>();
s = new string[]{"b","a","e","d","f","c"};
system.out.print("linkedlist<string> before sorting: ");
for (int j=0; j<s.length; j++) {
l.add(s[j]);
system.out.print(s[j] + " ");
}
system.out.println();
sort(l);
system.out.print("linkedlist<string> after sorting: ");
for (string ts : l) {
system.out.print(ts + " ");
}
system.out.println();
}
}
运行main函数测试，从输出可以看出quicksort类工作正常：
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<string> before sorting: b a e d f c linkedlist<string> after sorting: a b c d e f
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
apollo与springboot集成实现动态刷新配置的教程详解
网友评论