我正在尝试在一个整数数组上实现QuickSort。
除分区外,我的所有方法均能正常运行。分区从获取中点开始,然后依次进行排序。
来自{1,6,5,4,3,2,7}
然后在此之后的某个地方,我得到{1、2、5、3、4、7、6}作为最终结果
谁能告诉我在哪里可以进行调整?
预期输出应为{1,2,3,4,5,6,7}
import java.util.Arrays;
public class Test {
public static void main(String[]args) {
int [] a = {7,6,5,4,3,2,1};
quickSort(a);
System.out.println(Arrays.toString(a));
}
public static void quickSort( int [] a) {
quickSort(a,0,a.length - 1);
}
public static void quickSort(int [] a,int start,int end) {
if(start<end) {
int pivotIndex = partition(a, start, end);
quickSort(a,start,pivotIndex-1); // sort left partition
quickSort(a,pivotIndex+1,end); // sort right partition
}
}
public static int partition(int [] a, int start, int end) {
int mid =midpoint(start,end);
sortFirstMiddleLast(a,start,mid,end);
swap(a,start,end-1);
int pivotIndex = end -1;
int pivotValue = pivotIndex;
int indexFromLeft = start +1;
int indexFromRight = end -2;
boolean done = false;
while (!done) {
while (a[indexFromLeft]<a[pivotValue]) {
indexFromLeft++;
}
while (a[indexFromRight]>a[pivotValue]) {
indexFromRight--;
}
if (indexFromLeft < indexFromRight) {
swap(a,indexFromLeft,indexFromRight);
indexFromLeft++;
indexFromRight--;
}
else {
done=true;
}
}
swap(a,pivotIndex,indexFromLeft);
pivotIndex=indexFromLeft;
return pivotIndex;
}
public static void sortFirstMiddleLast(int [] a, int start, int mid, int end) {
if (a[start]>a[mid]) {
swap(a,start,mid);
}
else if (a[mid]>a[end]) {
swap(a,mid,end);
}
else if (a[start]>a[end]) {
swap(a,start,end);
}
else if(a[start] > a[mid]) {
swap (a,start,mid);
}
}
private static void swap(int[] a, int first, int second) {
int temp = a[first];
a[first] = a[second];
a[second] = temp;
}
private static int midpoint(int first, int last) {
return first + (last - first) / 2;
}
}
在行之后进一步执行之前检查是否开始=
int indexFromLeft = start +1;
int indexFromRight = end -2;
终止该条件下的递归。
如果您使用下面创建的类,则不会有任何问题。
class QuickSort{
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1);
for (int j=low; j<high; j++)
{
if (arr[j] <= pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
void sort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] a = {0,9, 7, 3, 4, 8, 6, 1 };
quickSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
public static void quickSort(int[] a, int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
int pivotIndex = partition(a, start, end, a[mid]);
quickSort(a, start, pivotIndex - 1); // sort left partition
quickSort(a, pivotIndex, end); // sort right partition
}
public static int partition(int[] a, int start, int end, int pivot) {
while (start <= end) {
while (a[start] < pivot) {
start++;
}
while (a[end] > pivot) {
end--;
}
if (start <= end) {
swap(a, start, end);
start++;
end--;
}
}
return start;
}
private static void swap(int[] a, int first, int second) {
int temp = a[first];
a[first] = a[second];
a[second] = temp;
}
尝试此一个
swap(a,start,end-1);
int pivotIndex = end -1; // removed -1
int pivotValue = pivotIndex;
int indexFromLeft = start +1; // removed +1
int indexFromRight = end -2; // removed -2
public static int partition(int [] a, int start, int end) {
int mid =midpoint(start,end);
sortFirstMiddleLast(a,start,mid,end);
swap(a,start,end-1);
int pivotIndex = end ;
int pivotValue = pivotIndex;
int indexFromLeft = start ;
int indexFromRight = end;
boolean done = false;
while (!done) {
while (a[indexFromLeft]<a[pivotValue]) {
indexFromLeft++;
}
while (a[indexFromRight]>a[pivotValue]) {
indexFromRight--;
}
if (indexFromLeft < indexFromRight) {
swap(a,indexFromLeft,indexFromRight);
indexFromLeft++;
indexFromRight--;
}
else {
done=true;
}
}
swap(a,pivotIndex,indexFromLeft);
pivotIndex=indexFromLeft;
return pivotIndex;
}