جافا دمج الفرز (دمج الفرز)

يعد Merge Sort خوارزمية فرز فعالة ومستقرة تعتمد على عمليات الدمج. تعد هذه الخوارزمية تطبيقًا نموذجيًا جدًا لطريقة فرق تسد .

يجمع فرز الدمج بين تسلسلين فرعيين مرتبين للحصول على تسلسل مرتب بالكامل، أي أنه يتم فرز كل تسلسل فرعي أولاً، ثم يتم فرز الأجزاء اللاحقة. إذا تم دمج قائمتين مرتبة في قائمة مرتبة واحدة، فإننا نسمي ذلك دمجًا ثنائي الاتجاه .

سرعة الفرز المدمج تأتي في المرتبة الثانية بعد الفرز السريع، والتعقيد الزمني هو O(nlogn). تستخدم عملية التقسيم فكرة الانقسام، وهي عملية متكررة، ومن أجل تقليل مشكلة فتح المساحة بشكل مستمر أثناء العملية العودية، يمكننا أولاً فتح مساحة مؤقتة قبل الدمج والفرز، واستخدام هذه المساحة. بشكل موحد أثناء العملية العودية فقط قم بالدمج.

على سبيل المثال:

 importjava.util.Arrays;publicclassMain{publicstaticvoidmain(String[]args){int[]arr=newint[]{86,23,7,45,19,10};intleft=0;intright=arr.length-1; int[]tem=Arrays.copyOf(arr,arr.length);print(arr);mergeSort(arr,left,right,tem);print(arr);}publicstaticvoidmergeSort(int[]arr,intleft,intright,int []tem){if(right-left<1){return;}intmid=left+(right-left)/2;mergeSort(arr,left,mid,tem);mergeSort(arr,mid+1,right,tem );merge(arr,left,mid,right,tem);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]tem){intindex=0;intl=left,r=mid+1;while (l<=mid&&r<=right){if(arr[l]<arr[r]){tem[index++]=arr[l++];}else{tem[index++]=arr[r++];}}while( l<=mid){tem[index++]=arr[l++];}while(r<=right){tem[index++]=arr[r++];}for(inti=0;i<(right-left+1 );i++){arr[left+i]=tem[i];}}privatestaticvoidprint(int[]arr){for(inti:arr){System.out.print(i+t);}System.out. برينتلن ()؛}} 

نتائج التشغيل هي كما يلي:

 8623745191071019234586