دمج فرز جاوة
https://stackoverflow.com/questions/1735863
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أحاول تقديم طريقة فرز دمج، لكنها تستمر في إعطاء أنواع خاطئة. أين أتغير لجعلها فعلا فرز الصفيف؟ أي جزء من الكود يجب أن يكون مختلفا؟ شكرا لوقتك.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
int elements = (rHigh - lHigh +1) ;
int[] temp = new int[elements];
int num = left;
while ((left <= lHigh) && (right <= rHigh)){
if (a[left] <= array[right]) {
temp[num] = array[left];
left++;
}
else {
temp[num] = array[right];
right++;
}
num++;
}
while (left <= right){
temp[num] = array[left]; // I'm getting an exception here, and is it because of the num???
left += 1;
num += 1;
}
while (right <= rHigh) {
temp[num] = array[right];
right += 1;
num += 1;
}
for (int i=0; i < elements; i++){
array[rHigh] = temp[rHigh];
rHigh -= 1;
}
تحرير: الآن لا تقوم Mergesort بفرز الأرقام، هل يمكن لأي شخص أن يقول لي أين هو على وجه التحديد؟ خاصة عندما طباع جزء "فرز دمج الاختبار".
المحلول
بادئ ذي بدء، أنا أفترض أن هذا أكاديمي بدلا من العملي، لأنك لا تستخدم وظيفة فرز مدمجة. ومع ذلك، إليك بعض المساعدة في التحرك في الاتجاه الصحيح:
عادة، يمكن للمرء أن يفكر في دمج فرز كطريقين مختلفين: وظيفة دمج () تدمج قوائم اثنين مرتبة في قائمة فرز واحدة، و mergesort () التي تنفصل بشكل متكرر القائمة في قوائم عنصر واحد. نظرا لأن قائمة عنصر عنصر واحد تم فرزها بالفعل، فأنت تقوم بدمج جميع القوائم معا في قائمة فرزها واحدة كبيرة.
إليك بعض الكود الزائف خارجيا:
merge(A, B):
C = empty list
While A and B are not empty:
If the first element of A is smaller than the first element of B:
Remove first element of A.
Add it to the end of C.
Otherwise:
Remove first element of B.
Add it to the end of C.
If A or B still contains elements, add them to the end of C.
mergeSort(A):
if length of A is 1:
return A
Split A into two lists, L and R.
Q = merge(mergeSort(L), mergeSort(R))
return Q
ربما هذا سوف يساعد في توضيح المكان الذي تريد الذهاب إليه.
إذا لم يكن كذلك، فهناك دائما مدمجة في ويكيبيديا.
إضافي:
لمساعدتك في الخروج، فيما يلي بعض التعليقات مضمنة في التعليمات البرمجية الخاصة بك.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
// what do lHigh and rHigh represent?
int elements = (rHigh - lHigh +1) ;
int[] temp = new int[elements];
int num = left;
// what does this while loop do **conceptually**?
while ((left <= lHigh) && (right <= rHigh)){
if (a[left] <= a[right]) {
// where is 'pos' declared or defined?
temp[pos] = a[left];
// where is leftLow declared or defined? Did you mean 'left' instead?
leftLow ++;
}
else {
temp[num] = a[right];
right ++;
}
num++;
}
// what does this while loop do **conceptually**?
while (left <= right){
// At this point, what is the value of 'num'?
temp[num] = a[left];
left += 1;
num += 1;
}
while (right <= rHigh) {
temp[num] = a[right];
right += 1;
num += 1;
}
// Maybe you meant a[i] = temp[i]?
for (int i=0; i < elements; i++){
// what happens if rHigh is less than elements at this point? Could
// rHigh ever become negative? This would be a runtime error if it did
a[rHigh] = temp[rHigh];
rHigh -= 1;
}
أنا غالب أن أكون غامضا حتى تفكر في الخوارزمية. حاول إدخال تعليقاتك الخاصة في التعليمات البرمجية. إذا كنت تستطيع كتابة ما يحدث من الناحية المعنية، فقد لا تحتاج إلى تجاوز مكدس :)
أفكاري هنا هي أنك لا تنفذ هذا بشكل صحيح. هذا لأنه يبدو أنك تمس فقط عناصر الصفيف مرة واحدة فقط (أو بالقرب من مرة واحدة فقط). هذا يعني أن لديك سيناريو أسوأ حالة تشغيل) الفرز عادة ما يستغرق على الأقل O(N * log N) ومن ما أعرفه، الإصدارات أبسط من دمج فرز هي في الواقع O(N^2).
أكثر:
في التنفيذ الأكثر تباطؤ لدمج الترتيب، أتوقع أن أرى نوعا من العودية في طريقة mergesort (). هذا لأن دمج فرز محدد عموما بشكل متكرر. هناك طرق للقيام بهذا يستخدم بشكل دائري وأراد الحلقات، لكنني بالتأكيد لا أوصي به كأداة تعليمية حتى تحصل عليه بشكل متكرر.
بصراحة، أقترح تناول أي رمز الزائفة أو الرمز الزائفي الذي قد تجده في مقالة ويكيبيديا لتنفيذ هذا وتبدأ في التعليمات البرمجية الخاصة بك. إذا قمت بذلك، فهذا لا يعمل بشكل صحيح، ونشره هنا وسنساعدك في العمل من المفكرة.
هتافات!
وأخيرا:
// Precondition: array[left..lHigh] is sorted and array[right...rHigh] is sorted.
// Postcondition: array[left..rHigh] contains the same elements of the above parts, sorted.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
// temp[] needs to be as large as the number of elements you're sorting (not half!)
//int elements = (rHigh - lHigh +1) ;
int elements = rHigh - left;
int[] temp = new int[elements];
// this is your index into the temp array
int num = left;
// now you need to create indices into your two lists
int iL = left;
int iR = right;
// Pseudo code... when you code this, make use of iR, iL, and num!
while( temp is not full ) {
if( left side is all used up ) {
copy rest of right side in.
make sure that at the end of this temp is full so the
while loop quits.
}
else if ( right side is all used up) {
copy rest of left side in.
make sure that at the end of this temp is full so the
while loop quits.
}
else if (array[iL] < array[iR]) { ... }
else if (array[iL] >= array[iR]) { ... }
}
}
نصائح أخرى
public class MergeSort {
public static void main(String[] args) {
int[] arr = {5, 4, 7, 2, 3, 1, 6, 2};
print(arr);
new MergeSort().sort(arr, 0, arr.length - 1);
}
private void sort(int[] arr, int lo, int hi) {
if (lo < hi) {
int mid = (lo + hi) / 2;
sort(arr, lo, mid); // recursive call to divide the sub-list
sort(arr, mid + 1, hi); // recursive call to divide the sub-list
merge(arr, lo, mid, hi); // merge the sorted sub-lists.
print(arr);
}
}
private void merge(int[] arr, int lo, int mid, int hi) {
// allocate enough space so that the extra 'sentinel' value
// can be added. Each of the 'left' and 'right' sub-lists are pre-sorted.
// This function only merges them into a sorted list.
int[] left = new int[(mid - lo) + 2];
int[] right = new int[hi - mid + 1];
// create the left and right sub-list for merging into original list.
System.arraycopy(arr, lo, left, 0, left.length - 1);
System.arraycopy(arr, mid + 1, right, 0, left.length - 1);
// giving a sentinal value to marking the end of the sub-list.
// Note: The list to be sorted is assumed to contain numbers less than 100.
left[left.length - 1] = 100;
right[right.length - 1] = 100;
int i = 0;
int j = 0;
// loop to merge the sorted sequence from the 2 sub-lists(left and right)
// into the main list.
for (; lo <= hi; lo++) {
if (left[i] <= right[j]) {
arr[lo] = left[i];
i++;
} else {
arr[lo] = right[j];
j++;
}
}
}
// print the array to console.
private static void print(int[] arr) {
System.out.println();
for (int i : arr) {
System.out.print(i + ", ");
}
}
}
هنا آخر!
private static int[] mergeSort(int[] input){
if (input.length == 1)
return input;
int length = input.length/2;
int[] left = new int[length];
int[] right = new int[input.length - length];
for (int i = 0; i < length; i++)
left[i] = input[i];
for (int i = length; i < input.length; i++)
right[i-length] = input[i];
return merge(mergeSort(left),mergeSort(right));
}
private static int[] merge(int[] left, int[] right){
int[] merged = new int[left.length+right.length];
int lengthLeft = left.length;
int lengthRight = right.length;
while (lengthLeft > 0 && lengthRight > 0){
if (left[left.length - lengthLeft] < right[right.length - lengthRight]){
merged[merged.length -lengthLeft-lengthRight] = left[left.length - lengthLeft];
lengthLeft--;
}else{
merged[merged.length - lengthLeft-lengthRight] = right[right.length - lengthRight];
lengthRight--;
}
}
while (lengthLeft > 0){
merged[merged.length - lengthLeft] = left[left.length-lengthLeft];
lengthLeft--;
}
while (lengthRight > 0){
merged[merged.length - lengthRight] = right[right.length-lengthRight];
lengthRight--;
}
return merged;
}
static void mergeSort(int arr[],int p, int r) {
if(p<r) {
System.out.println("Pass "+k++);
int q = (p+r)/2;
mergeSort(arr,p,q);
mergeSort(arr,q+1,r);
//System.out.println(p+" "+q+" "+r);
merge(arr,p,q,r);
}
}
static void merge(int arr[],int p,int q,int r) {
int temp1[],temp2[];
//lower limit array
temp1 = new int[q-p+1];
//upper limit array
temp2 = new int[r-q];
for(int i=0 ; i< (q-p+1); i++){
temp1[i] = arr[p+i];
}
for(int j=0; j< (r-q); j++){
temp2[j] = arr[q+j+1];
}
int i = 0,j=0;
for(int k=p;k<=r;k++){
// This logic eliminates the so called sentinel card logic mentioned in Coreman
if(i!= temp1.length
&& (j==temp2.length || temp1[i] < temp2[j])
) {
arr[k] = temp1[i];
// System.out.println(temp1[i]);
i++;
}
else {
//System.out.println(temp2[j]);
arr[k] = temp2[j];
j++;
}
}
}
>
دمج فرز باستخدام الحارس
هذه الرموز تعمل بشكل جيد تماما.
public void mergeSort(int a[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
public void merge(int a[], int low, int mid, int high) {
int n1 = mid - low + 1;// length of an array a1
int n2 = high - mid; // length of an array a2
int a1[] = new int[n1 + 1];
int a2[] = new int[n2 + 1];
int lowRange = low;
for (int i = 0; i < n1; i++) {
a1[i] = a[lowRange];
lowRange++;
}
for (int j = 0; j < n2; j++) {
a2[j] = a[mid + j + 1];
}
a1[n1] = Integer.MAX_VALUE; // inserting sentinel at the end of array a1
a2[n2] = Integer.MAX_VALUE; // inserting sentinel at the end of array a2
int i = 0;
int j = 0;
int k = low;
for (k = low; k <= high; k++) {
if (a1[i] >= a2[j]) {
a[k] = a2[j];
j++;
} else {
a[k] = a1[i];
i++;
}
}
if (a2.length >= a1.length) {
for (int ab = k; ab < a2.length; ab++) {
a[k] = a2[ab];
k++;
}
} else if (a1.length >= a2.length) {
for (int ab = k; ab < a1.length; ab++) {
a[k] = a1[ab];
k++;
}
}
}
هنا بديل آخر:
public class MergeSort {
public static void merge(int[]a,int[] aux, int f, int m, int l) {
for (int k = f; k <= l; k++) {
aux[k] = a[k];
}
int i = f, j = m+1;
for (int k = f; k <= l; k++) {
if(i>m) a[k]=aux[j++];
else if (j>l) a[k]=aux[i++];
else if(aux[j] > aux[i]) a[k]=aux[j++];
else a[k]=aux[i++];
}
}
public static void sort(int[]a,int[] aux, int f, int l) {
if (l<=f) return;
int m = f + (l-f)/2;
sort(a, aux, f, m);
sort(a, aux, m+1, l);
merge(a, aux, f, m, l);
}
public static int[] sort(int[]a) {
int[] aux = new int[a.length];
sort(a, aux, 0, a.length-1);
return a;
}
}
فيما يلي خوارزمية ترتيب بسيطة في Java:
نصيحة جيدة: دائما استخدام int middle = low + (high-low)/2 بدلاً من int middle = (low + high)/2.
public static int[] mergesort(int[] arr) {
int lowindex = 0;
int highindex = arr.length-1;
mergesort(arr, lowindex, highindex);
return arr;
}
private static void mergesort(int[] arr, int low, int high) {
if (low == high) {
return;
} else {
int midIndex = low + (high-low)/2;
mergesort(arr, low, midIndex);
mergesort(arr, midIndex + 1, high);
merge(arr, low, midIndex, high);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] left = new int[mid-low+2];
for (int i = low; i <= mid; i++) {
left[i-low] = arr[i];
}
left[mid-low+1] = Integer.MAX_VALUE;
int[] right = new int[high-mid+1];
for (int i = mid+1; i <= high; i++) {
right[i-mid-1] = arr[i];
}
right[high - mid] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for (int k = low; k <= high; k++) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
}
}
حزمة كوم؛
public class Test {
int count = 0;
public static void main(String[] args) {
int a[] = {1,3,5,7,9,10,14,15,16};
int b[] = {2,4,6,8,11,12,13,17,18};
int sizec = a.length+b.length;
int c[] = new int[sizec];
int i=0;int j=0;int k=0;
while(k<sizec)
{
if(i == a.length || j == b.length)
{
int sizeDifference = 0;
if(i==a.length)
{
sizeDifference = b.length-j;
for (int m =0;m<sizeDifference;m++)
{
c[k] = b[m+j];
if(k<sizec)
k++;
}
break;
}
else if(j== b.length)
{
sizeDifference = a.length-i;
for (int m =0;m<sizeDifference;m++)
{
c[k] = a[m+i];
if(k<sizec)
k++;
}
break;
}
else
{
c[k] = b[j];
j++;
}
}
if(i < a.length || j < b.length )
{
if(a[i]>b[j] )
{
c[k]=b[j];
j++;
}
else if(a[i]<b[j])
{
c[k]=a[i];
i++;
}
}
k++;
}
for(int l=0;l<sizec;l++)
{
System.out.println(c[l]);
}
}
}
لا تنتمي إلى StackOverflow
