归并排序的C#,java,js,python,ruby实现，,C 实现 Merge s

归并排序的C#,java,js,python,ruby实现，,C 实现 Merge s

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 归并排序

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实现

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))enddef 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   returnend subroutine mergerecursive 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   returnend subroutine MergeSortprogram 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 :',Aend 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}