Question

求一个java算法

例如sequence是 1,2,3,4,5,6,7
则对应的rn是 6,4,2,0,1,3,5
例如sequence是 1,2,3,4,5,6,7,8
则对应rn是 8,6,4,2,1,3,5,7

Answer 1

输出结果

main方法

sort递归

.partition方法

fd一个判断，一个交换

package com.kangyong.demo11;

public class QuicksortExtra<T extends Comparable<T>> {
//快速排序
//直接拆成两段，左边排序，右边排序然后组合。
//使整个集合有序
public static void sort(Comparable[] a){
int low = 0;
int high = a.length-1;
sort(a,low,high);
}
//是数组a中从low到high处有序
private static void sort(Comparable[] a, int low, int high) {
//出口当low>=high
if(low>=high)
{
return;
}
//使用partition方法排序
int partition = partition(a,low,high);
//让左子组有序
sort(a,low,partition-1);
//让右子组有序
sort(a,partition+1,high);
}
private static int partition(Comparable[] a, int low, int high) {
//确定分界值,分界值不是0是low
Comparable key = a[low];
//定义两个指针，分别指向第一个位置，和最后一个位置+1
int left = low;
int right = high+1;
while (true){
//从右往左，移动right指针时
while (true){
right--;
//如果key分界值是奇数，（1.找到一个偶数停住，2.找到奇数并且&&比key小停住）
if((Integer)key%2==1){
if((Integer)a[right]%2==0)break;
if((Integer)a[right]%2==1&&less(a[right],key))break;
if(right==low)break;//走到头跳出
}else {
//如果key分解值是偶数，（1.找到一个偶数并且&&比分解值大的停住，2.找到奇数不停）
if((Integer)a[right]%2==0&&!less(a[right],key))break;
if(right==low)break;
}
}
//然后在从左往右，移动left指针
while (true){
left++;
//如果key分解值是奇数，（1.找到一个奇数并且&& 比key大的停住，2.找到一个偶数停住并且）
if((Integer)key%2==1){
if(less(key,a[left])&&(Integer)a[left]%2==1)break;
if(left==high)break;
}else {//如果key分解值是偶数，（1.找到一个奇数停住，找到一个偶数并且&& 比key小的停住）
if((Integer)a[left]%2==1)break;
if((Integer)a[left]%2==0&&less(a[left],key))break;
if(left==high)break;//走到头跳出。
}
}
//交换元素，出口是如果两个指针相遇
if(left>=right){
break;
}else {
exchange(a,left,right);
}
}//while结束标记
//交换分解值,分界值所在的索引不是0，是low
exchange(a,low,right);
//返回人分界值索引
return right;
}
public static boolean less(Comparable a,Comparable b){
return a.compareTo(b)<0;
}
public static void exchange(Comparable[]a,int i,int j){
Comparable temp = a[i];
a[i]=a[j];
a[j]=temp;
}
}
//指针停住的条件：
//从右往左，移动right指针时
//如果key分界值是奇数，（1.找到一个偶数停住，2.找到奇数并且比key小停住）
//如果key分解值是偶数，（1.找到一个偶数并且比分解值小的停住，2.找到奇数不停）
//然后在从左往右，移动left指针
//如果key分解值是奇数，（1.找到一个奇数并且比key大的停住，2.找到一个偶数停住）
//如果key分解值是偶数，（1.找到一个奇数停住，找到一个偶数并且比key小的停住）