0
이 앱에서 피벗 (median)을 피벗으로 선택하려고하지만 잘못된 것 같습니다. 어떤 도움이라도 대단히 감사하겠습니다.중간 점을 피벗으로 선택하는 경우
나는 처음 몇 개의 숫자를 순서대로 얻은 다음 끝쪽으로 가져옵니다.
public class QuickSort {
public static void main(String[] args) {
int [] list = {1,3,2,4,6,5,8,7,9,0};
quickSort (list);
for (int i=0; i < list.length; i++)
System.out.print(list[i] + " ");
}
public static void quickSort(int [] list)
{
quickSort(list, 0, list.length - 1);
}
public static void quickSort (int[] list, int first, int last)
{
int size = last - first + 1;
if (size > 3){
int median1 = median(list, first, last);
int partition1 = partition(list, first, last, median1);
quickSort(list, first, partition1 - 1);
quickSort(list, partition1 + 1, last);
}
}
public static int median(int [] list, int first1, int last1){
int middle = (first1 + last1)/2;
if (list[first1] > list[middle])
swap(list, first1, middle);
if (list[first1] > list[last1])
swap(list, first1, last1);
if (list[middle] > list[last1])
swap(list, middle, last1);
swap(list, middle, last1 - 1);
return list[last1 - 1 ];
}
public static int partition(int [] list, int left, int right, long pivot) {
int leftPtr = left;
int rightPtr = right - 1;
while (true) {
while (list[++leftPtr] < pivot);
while (list[--rightPtr] > pivot);
if (leftPtr >= rightPtr)
break;
else
swap(list, leftPtr, rightPtr);
}
swap(list, leftPtr, right - 1);
return leftPtr;
}
public static void swap(int []list, int dex1, int dex2) {
int temp = list[dex1];
list[dex1] = list[dex2];
list[dex2] = temp;
}
일부 순서대로 번호가 있지만 전부는 아닙니다.