Sắp xếp theo kiểu hòa nhập

Tiếp tục những bài hướng dẫn hoc lap trinh java co ban về các kiểu sắp xếp

1. Sắp xếp hòa nhập 2 đường(two way merge)

- Khái niệm: giả sử A là dãy gồm a phần tử đc sắp xếp săn, B là dãy gồm b phần tử được sắp xếp sẵn. Phép hợp nhất 2 dãy A,B thành 1 dãy được sắp xếp săn là phép hòa nhập 2 đường
- Ý tưởng của phép sắp xếp hòa nhập 2 đường:
So sánh 2 khóa nhỏ nhất của A,B chọn khóa nhỏ hơn để đưa vào miền sắp xếp trong bộ nhớ, và đồng thời loại bỏ khóa đó ra khỏi dãy, quá trình cú như vậy cho tới khi một trong 2 mạch đã hết phần tử. Cuối cùng chỉ cần đưa nốt phần còn lại của mạch còn lại xếp vào.

2. Sắp xếp hòa nhập 2 đường trực tiếp(straight two way merge)

Từ phép hòa nhập ta sẽ có phương pháp sắp xếp mới:
- Coi mỗi phần tử trong dãy là một dãy con và ta sẽ hoà nhập đôi một từng dãy. Ta sẽ được một mạch mới mỗi mạch là 2 phần tử.
- Tiếp tục hòa nhập mỗi mạch con lại được mạch mới gồm 4 phần tử và cứ như thế đến hết ta sẽ được một dãy đã sắp xếp hoàn toàn có độ dài là n.

- Khi thực hiện thì ta sẽ thực hiện ngược lại, chia đôi dãy ban đầu ra thành 2 phần và mỗi phần lại cứ chia đôi, chia đôi dần cuối cùng còn 1 phần tử và bắt đầu gộp chúng lại:
MergeSort(int low, int high)

PHP:

MergeSort(int low, int high)



{
if (low < high) {int mid = (low + high)/2;MergeSort(low, mid);MergeSort(mid + 1, high);Merge(low, mid, high);
}
}
 void Merge(int low, int mid, int high)

{int h = low, i = low, j = mid+1, k;
while ((h <= mid) && (j <= high)) {
if (a[h] <= a[j]) { b[i] = a[h]; h++; }
else { b[i] = a[j]; j++; } i++;
}
if (h > mid) for (k=j; k<=high; k++) {b[i] = a[k]; i++;
}
else for (k=h; k<=mid; k++) {b[i] = a[k]; i++;
}
for (k=low; k<=high; k++) a[k] = b[k];
}

Code jav ví dụ:

PHP:

import java.util.*;

public class MergeSort{
    public int a[]=new int[50];
public void merge_sort(int low,int high)
{
 int mid;
 if(low<high)
 {
  mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}
public void merge(int low,int mid,int high)
{
 int h,i,j,k;
 int b[]=new int[50];
 h=low;
 i=low;
 j=mid+1;

 while((h<=mid)&&(j<=high))
 {
  if(a[h]<=a[j])
  {
   b[i]=a[h];
   h++;
  }
  else
  {
   b[i]=a[j];
   j++;
  }
  i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 for(k=low;k<=high;k++) a[k]=b[k];
}
public MergeSort()
{
 int num,i;
 System.out.println("             MERGE SORT          ");
 System.out.println();System.out.println();System.out.println("Nhập số các số cần sắp xếp");
 num=new Scanner(System.in).nextInt();
 System.out.println();
 System.out.println("Nhập giá trị ");
 for(i=1;i<=num;i++)
 {
  a[i]=new Scanner(System.in).nextInt() ;
 }
 merge_sort(1,num);
 System.out.println();
 System.out.println("So, the sorted list (using MERGE SORT) will be :");
 System.out.println();
 System.out.println();

 for(i=1;i<=num;i++)
     System.out.print(a[i]+"    ");


}
public static void main(String[] args) {
    new MergeSort();
}