Сортировка слиянием
Сортировка слиянием (англ. merge sort)
— алгоритм сортировки, который упорядочивает списки (или другие
структуры данных, доступ к элементам которых можно получать только
последовательно, например — потоки) в определённом порядке. Эта
сортировка — хороший пример использования принципа «разделяй и властвуй».
Алгоритм был изобретён Джоном фон Нейманом в 1945 году. Реализация на JAVA
public class MergeSort {
public static void mergesort (int[] a) {
mergesort(a, 0, a.length-1);
}
private static void mergesort (int[] a, int l, int r) {
//base case: a[l..r] is empty or has only one element
if ( l>=r ) return;
//recursion step: a[l..r] is not empty
//divide into sublists and merge
int m = (l+r)/2;
mergesort (a, l, m);
mergesort (a, m+1, r);
merge (a, l, m, r);
}
//merges to sublists
private static void merge (int[] a, int l, int m, int r) {
//base case: second sublist is empty
if (m+1>r) return;
int[] b = new int[a.length];
//create temporary array
//copy a[l..m] to b[l..m]
for (int i=l; i!=m+1; i++) {
b[i] = a[i];
}
//copy a[m+1..r] to b[m+1..r] in reverse order
for (int i=m+1; i!=r+1; i++) {
b[i] = a[r+m+1-i];
}
//merge b[l..m] with b[m+1..r] to a[l..r]
int k=l; int j=r; //pointer wandering from outside inward
for (int i=l; i!=r+1; i++) {
if (b[k] <= b[j]) a[i] = b[k++];
else a[i] = b[j--];
}
}
} | Реализация на C
/* Merge sort
// The merge sort divides the array into two sub-arrays, sorts them and then
// calls merge to merge the two arrays back together.
*/
void Merge( int a[], int b[], int c[], int m, int n )
{
int i = 0, j = 0, k = 0;
while (i < m && j < n)
{
if( a[i] < b[j] )
{
c[k++] = a[i++];
}
else
{
c[k++] = b[j++];
}
}
while ( i < m )
{
c[k++] = a[i++];
}
while ( j < n )
{
c[k++] = b[j++];
}
}
void merge_sort( int key[], int n )
{
int j, k, m, *w;
for( m = 1; m < n; m *= 2 );
if (m != n)
{
printf ("ERROR: Size of the array is not power of 2.");
}
else
{
w = calloc( n, sizeof(int) );
for( k = 1; k < n; k *= 2 )
{
for( j = 0; j < (n - k); j += 2 * k )
{
Merge(key + j, key + j + k, w + j, k, k);
for ( j = 0; j < n; j++) key[j] = w[j];
}
}
free(w);
}
} |
Реализация на C++
/* Sorts first n elements of array a[] in non-decreasing order. */
template<typename T> void merge_sort(T a[], int n)
{
int i, j, k;
T tmp;
/* For small arrays, insertion sort is much faster */
if (n < 64) {
for (i = 1; i < n; i++) {
tmp = a[i];
for (j = i-1; j >= 0 && tmp < a[j]; j--) a[j+1] = a[j];
a[j+1] = tmp;
}
return;
}
int f = n / 2; /* f = number of elements in first half */
/* Recursively sort both halves */
merge_sort(a, f);
merge_sort(a+f, n-f);
/* Merge */
T *s = new T[n]; /* temporary array to keep the sorted sequence */
for (i = 0, j = f, k = 0; i < f && j < n;)
s[k++] = (a[i] < a[j]) ? a[i++] : a[j++];
while (i < f) s[k++] = a[i++];
while (j < n) s[k++] = a[j++];
for (i = 0; i < n; i++) a[i] = s[i];
delete[] s;
}
/* Example of usage: */
#include <cstdio>
#include <cstdlib>
int main()
{
int n=100, *a=new int[n];
for (int i = 0; i < n; i++) a[i] = rand();
merge_sort(a, n);
for (int i = 0; i < n; i++) printf("%d\n", a[i]);
} |
Литература
|
