php 归并排序的C#,java,js,python,ruby实现

C 实现 Merge sort

// Mix two sorted tables in one and split the result into these two tables.
int *Mix(int *tab1,int *tab2,int count1,int count2)
{
  int i,i1,i2;
  i = i1 = i2 = 0;
  int * temp = (int *)malloc(sizeof(int)*(count1+count2));

  while((i1<count1) && (i2<count2))
  {
    while((i1<count1) && (*(tab1+i1)<=*(tab2+i2)))
    {
      *(temp+i++) = *(tab1+i1);
      i1++;
    }
    if (i1<count1)
    {
      while((i2<count2) && (*(tab2+i2)<=*(tab1+i1)))
      {
        *(temp+i++) = *(tab2+i2);
        i2++;
      }
    }
  }

  memcpy(temp+i,tab1+i1,(count1-i1)*sizeof(int));
  memcpy(tab1,temp,count1*sizeof(int));

  memcpy(temp+i,tab2+i2,(count2-i2)*sizeof(int));
  memcpy(tab2,temp+count1,count2*sizeof(int));
  // These two lines can be:
  // memcpy(tab2,temp+count1,i2*sizeof(int));
  free(temp);
}

// MergeSort a table of integer of size count.
// Never tested.
void MergeSort(int *tab,int count)
{
  if (count==1) return;

  MergeSort(tab,count/2);
  MergeSort(tab+count/2,(count+1)/2);
  Mix(tab,tab+count/2,count/2,(count+1)/2);
}

C++

//! \brief Performs a recursive merge sort on the given vector
//! \param vec The vector to be sorted using the merge sort
//! \return The sorted resultant vector after merge sort is
//! complete.
vector<int> merge_sort(vector<int>& vec)
{
    // Termination condition: List is completely sorted if it
    // only contains a single element.
    if(vec.size() == 1)
    {
        return vec;
    }

    // Determine the location of the middle element in the vector
    std::vector<int>::iterator middle = vec.begin() + (vec.size() / 2);

    vector<int> left(vec.begin(), middle);
    vector<int> right(middle, vec.end());

    // Perform a merge sort on the two smaller vectors
    left = merge_sort(left);
    right = merge_sort(right);

    return merge(left, right);
}

下面是使用vector的归并排序的实现：

//! \brief Merges two sorted vectors into one sorted vector
//! \param left A sorted vector of integers
//! \param right A sorted vector of integers
//! \return A sorted vector that is the result of merging two sorted
//! vectors.
vector<int> merge(const vector<int>& left, const vector<int>& right)
{
    // Fill the resultant vector with sorted results from both vectors
    vector<int> result;
    unsigned left_it = 0, right_it = 0;

    while(left_it < left.size() && right_it < right.size())
    {
        // If the left value is smaller than the right it goes next
        // into the resultant vector
        if(left[left_it] < right[right_it])
        {
            result.push_back(left[left_it]);
            left_it++;
        }
        else
        {
            result.push_back(right[right_it]);
            right_it++;
        }
    }

    // Push the remaining data from both vectors onto the resultant
    while(left_it < left.size())
    {
        result.push_back(left[left_it]);
        left_it++;
    }

    while(right_it < right.size())
    {
        result.push_back(right[right_it]);
        right_it++;
    }

    return result;
}

下面是使用变长数组和递归的实现算法：

#include <iostream>
using namespace std;

void merge(int a[], const int low, const int mid, const int high)
{
    // Variables declaration. 
    int * b = new int[high+1-low];
    int h,i,j,k;
    h=low;
    i=0;
    j=mid+1;
    // Merges the two array's into b[] until the first one is finish
    while((h<=mid)&&(j<=high))
    {
        if(a[h]<=a[j])
        {
            b[i]=a[h];
            h++;
        }
        else
        {
            b[i]=a[j];
            j++;
        }
        i++;
    }
    // Completes the array filling in it the missing values
    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++;
        }
    }
    // Prints into the original array
    for(k=0;k<=high-low;k++) 
    {
        a[k+low]=b[k];
    }
    delete[] b;
}

void merge_sort(int a[], const int low, const int high)     // Recursive sort ...
{
    int mid;
    if(low<high)
    {
        mid=(low+high)/2;
        merge_sort(a, low,mid);
        merge_sort(a, mid+1,high);
        merge(a, low,mid,high);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int arraySize;
    // a[] is the array to be sorted. ArraySize is the size of a[] ...
    merge_sort(a, 0, (arraySize-1) );        // would be more natural to use merge_sort(a, 0, arraySize ), so please try ;-)

    // some work 
    return 0;
}

C#实现归并排序

public IList MergeSort(IList list)
        {
            if (list.Count <= 1)
                return list;

            int mid = list.Count / 2;

            IList left = new ArrayList();
            IList right = new ArrayList();

            for (int i = 0; i < mid; i++)
                left.Add(list[i]);

            for (int i = mid; i < list.Count; i++)
                right.Add(list[i]);

            return Merge(MergeSort(left), MergeSort(right));
        }

        public IList Merge(IList left, IList right) 
        {
            IList rv = new ArrayList();

            while (left.Count > 0 && right.Count > 0)
                if (((IComparable)left[0]).CompareTo(right[0]) > 0)
                {
                    rv.Add(right[0]);
                    right.RemoveAt(0);
                }
                else
                {
                    rv.Add(left[0]);
                    left.RemoveAt(0);
                }

            for (int i = 0; i < left.Count; i++)
                rv.Add(left[i]);

            for (int i = 0; i < right.Count; i++)
                rv.Add(right[i]);

            return rv;
        }

Erlang

merge_sort(List) when length(List) =< 1 -> List;
merge_sort(List) ->
    {Left, Right} = lists:split(length(List) div 2, List),
    lists:merge(merge_sort(Left), merge_sort(Right)).

Java 归并排序

java">public int[] mergeSort(int array[])  {
    if(array.length > 1)    {
        int elementsInA1 = array.length/2;
        int elementsInA2 = array.length - elementsInA1;
        int arr1[] = new int[elementsInA1];
        int arr2[] = new int[elementsInA2];

        for(int i = 0; i < elementsInA1; i++)
            arr1[i] = array[i];

        for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
            arr2[i - elementsInA1] = array[i];

        arr1 = mergeSort(arr1);
        arr2 = mergeSort(arr2);

        int i = 0, j = 0, k = 0;

        while(arr1.length != j && arr2.length != k) {
            if(arr1[j] <= arr2[k]) {
                array[i] = arr1[j];
                i++;
                j++;
            } else {
                array[i] = arr2[k];
                i++;
                k++;
            }
        }

        while(arr1.length != j) {
            array[i] = arr1[j];
            i++;
            j++;
        }
        while(arr2.length != k) {
            array[i] = arr2[k];
            i++;
            k++;
        }
    }
    return array;
 }

归并排序的JavaScript实现

javascript">function merge_sort(arr) {
    var l = arr.length, m = Math.floor(l/2);
    if (l <= 1) return arr;
    return merge(merge_sort(arr.slice(0, m)), merge_sort(arr.slice(m)));
}

function merge(left,right) {
    var result = [];
    var ll = left.length, rl = right.length;
    while (ll > 0 && rl > 0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
            ll--;
        } else {
            result.push(right.shift());
            rl--;
        }
    }
    if (ll > 0) {
        result.push.apply(result, left);
    } else if (rl > 0) {
        result.push.apply(result, right);
    }
    return result;
}

PHP实现归并排序

function merge_sort(&$arrayToSort)
{
    if (sizeof($arrayToSort) <= 1)
        return $arrayToSort;

    // split our input array into two halves
    // left...
    $leftFrag = array_slice($arrayToSort, 0, (int)(count($arrayToSort)/2));
    // right...
    $rightFrag = array_slice($arrayToSort, (int)(count($arrayToSort)/2));

    // RECURSION
    // split the two halves into their respective halves...
    $leftFrag = merge_sort($leftFrag);
    $rightFrag = merge_sort($rightFrag);

    $returnArray = merge($leftFrag, $rightFrag);

    return $returnArray;
}

function merge(&$lF, &$rF)
{
    $result = array();

    // while both arrays have something in them
    while (count($lF)>0 && count($rF)>0) {
        if ($lF[0] <= $rF[0]) {
            array_push($result, array_shift($lF));
        }
        else {
            array_push($result, array_shift($rF));
        }
    }

    // did not see this in the pseudo code,
    // but it became necessary as one of the arrays
    // can become empty before the other
    array_splice($result, count($result), 0, $lF);
    array_splice($result, count($result), 0, $rF);

    return $result;
}

归并排序的Python实现

def mergesort(arr):
    if len(arr) == 1:
        return arr

    m = len(arr) / 2
    l = mergesort(arr[:m])
    r = mergesort(arr[m:])

    if not len(l) or not len(r):
        return l or r

    result = []
    i = j = 0
    while (len(result) < len(r)+len(l)):        
        if l[i] < r[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(r[j])
            j += 1            
        if i == len(l) or j == len(r):            
            result.extend(l[i:] or r[j:])
            break

    return result

归并排序的Ruby实现

def mergesort(list)
  return list if list.size <= 1
  mid = list.size / 2
  left  = list[0, mid]
  right = list[mid, list.size]
  merge(mergesort(left), mergesort(right))
end

def merge(left, right)
  sorted = []
  until left.empty? or right.empty?
    if left.first <= right.first
      sorted << left.shift
    else
      sorted << right.shift
    end
  end
  sorted.concat(left).concat(right)
end

Fortran 的归并排序

subroutine Merge(A,NA,B,NB,C,NC)

   integer, intent(in) :: NA,NB,NC         ! Normal usage: NA+NB = NC
   integer, intent(in out) :: A(NA)        ! B overlays C(NA+1:NC)
   integer, intent(in)     :: B(NB)
   integer, intent(in out) :: C(NC)

   integer :: I,J,K

   I = 1; J = 1; K = 1;
   do while(I <= NA .and. J <= NB)
      if (A(I) <= B(J)) then
         C(K) = A(I)
         I = I+1
      else
         C(K) = B(J)
         J = J+1
      endif
      K = K + 1
   enddo
   do while (I <= NA)
      C(K) = A(I)
      I = I + 1
      K = K + 1
   enddo
   return

end subroutine merge

recursive subroutine MergeSort(A,N,T)

   integer, intent(in) :: N
   integer, dimension(N), intent(in out) :: A
   integer, dimension((N+1)/2), intent (out) :: T

   integer :: NA,NB,V

   if (N < 2) return
   if (N == 2) then
      if (A(1) > A(2)) then
         V = A(1)
         A(1) = A(2)
         A(2) = V
      endif
      return
   endif      
   NA=(N+1)/2
   NB=N-NA

   call MergeSort(A,NA,T)
   call MergeSort(A(NA+1),NB,T)

   if (A(NA) > A(NA+1)) then
      T(1:NA)=A(1:NA)
      call Merge(T,NA,A(NA+1),NB,A,N)
   endif
   return

end subroutine MergeSort

program TestMergeSort

   integer, parameter :: N = 8
   integer, dimension(N) :: A = (/ 1, 5, 2, 7, 3, 9, 4, 6 /)
   integer, dimension ((N+1)/2) :: T
   call MergeSort(A,N,T)
   write(*,'(A,/,10I3)')'Sorted array :',A

end program TestMergeSort

Groovy 归并排序

def mergeSort(list){
 if( list.size() <= 1) return list
  center = list.size() / 2
  left  = list[0..center]
  right = list[center..list.size()]
  merge(mergeSort(left), mergeSort(right))
}

def merge(left, right){
  sorted = []
  while(left.size() > 0 || right.size() > 0)
    if(left.get(0) <= right.get(0)){
      sorted << left
    }else{
      sorted << right
    }
  sorted = sorted + left + right
}