因此，顯然在某些情況下，我的算法需要較少的透視更改來完成列表的排序。實(shí)際上，我的算法確實(shí)對(duì)列表進(jìn)行了正確的排序，但數(shù)據(jù)透視表的數(shù)量小于或等于我所給出的示例。我的賦值中給出的一個(gè)例子是這個(gè)數(shù)組：3 45 12 -3 4 -3 21 0 6 20輸出應(yīng)該是這樣的：樞軸數(shù)： 7第一個(gè)元素： -3最后一個(gè)元素： 45這是我得到的：樞軸數(shù)： 5第一個(gè)元素： -3最后一個(gè)元素： 45在另一個(gè)例子中，它適用于正確數(shù)量的樞軸：9 2 4 7 3 7 10 11 12 13 13 10 13 13我應(yīng)該得到什么，也得到什么：樞軸數(shù)量： 10第一個(gè)元素： 2最后一個(gè)元素： 13我特別困惑的是，它在某些情況下有效，而在其他情況下則不起作用。代碼如下：public static void quickSort(int[] arr, int start, int end, CountObject count){ int partition = partition(arr, start, end, count); //partition will return the position the pivot. The pivot will be at the right place, hence if either side //of the pivot consists of only one element, it should not be sorted //check whether the part left from the pivot should still be sorted if(partition-1>start) { quickSort(arr, start, partition - 1, count); } //check whether the part right from the pivot should still be sorted if(partition+1<end) { quickSort(arr, partition + 1, end, count); }}public static int partition(int[] arr, int start, int end, CountObject count){ int pivot = arr[start]; count.increaseCount(); //checks if left pointer < pivot for(int i=end; i>start; i--){ if(arr[i]>pivot){ int temp= arr[end]; arr[end]=arr[i]; arr[i]=temp; end--; } } int temp = arr[start];//=pivot arr[start] = arr[end]; arr[end] = temp; return end;}}我正在使用 CountObject 類進(jìn)行計(jì)數(shù)。它包含一個(gè)方法增加計(jì)數(shù)和一個(gè)實(shí)例變量計(jì)數(shù)。
1 回答
白衣非少年
TA貢獻(xiàn)1155條經(jīng)驗(yàn) 獲得超0個(gè)贊
所以我終于想通了。我不得不使用另一種技術(shù)來遍歷列表。在我的OP中，我使用第一個(gè)元素作為樞軸，并將其與列表末尾開始的所有元素進(jìn)行比較?，F(xiàn)在我從列表的第二個(gè)元素/當(dāng)前子列表開始。
這是解決我問題的代碼，我希望這將使某人節(jié)省2天的工作，盡管我自己做這件事很有教育意義。
import java.util.Scanner;
public class Quickie {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int temp;
int size = sc.nextInt();
int[] list = new int[size];
for (int i = 0; i < size; i++) {
temp = sc.nextInt();
list[i] = temp;
}
int end = size - 1;
CounterClass count = new CounterClass(0);
quickSort(list, 0, end, count);
int firstElement = list[0];
int lastElement = list[size - 1];
System.out.println("Number of pivots: " + count.getCount());
System.out.println("First Element: " + firstElement);
System.out.println("Last Element: " + lastElement);
}
private static void quickSort (int []arr, int start, int end, CounterClass count){
int partition = partition(arr, start, end, count);
if (partition-1>start){
quickSort(arr, start, partition-1,count);
}
if (partition+1<end){
quickSort(arr, partition+1,end,count);
}
}
private static int partition (int[]arr, int start, int end, CounterClass count){
int pivot = arr[start];
count.count++;
int pointer = start+1;
int i =pointer;
for (int j=pointer; j<=end;j++){
if (arr[j]<pivot){
int temp = arr[j];
arr[j]=arr[i];
arr[i]=temp;
i++;
}
}
i-=1;
int temp=arr[start];
arr[start]=arr[i];
arr[i]=temp;
return (i);
}
}
class CounterClass{
int count;
public CounterClass(int count){
this.count = count;
}
public int getCount() {
return count;
}
}
添加回答
舉報(bào)
0/150
提交
取消