Алгоритм сортировки слиянием

Question

Какой может быть лучший алгоритм «сортировки слиянием» в C ++, где память должна использоваться «наиболее эффективно»?Я просто знаю стандартный способ сделать это, но это не самый эффективный способ использования памяти.Это единственный известный мне вариант:

#include <iostream>
using namespace std;
int main() {
int arr1[20]= {0,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int arr2[14]= {0,23,25,27,29,31,33,35,37,39,40,41,42,43};
int arr3[34];
int indexA=0, indexB=0, indexC=0;

while((indexA<20) && (indexB<14)) {
    if(arr1[indexA] < arr2[indexB]) {
        arr3[indexC] = arr1[indexA];
        indexA++;
    }
    else {
        arr3[indexC] = arr2[indexB];
        indexB++;
    }
    indexC++;
}

while(indexA<20) {
    arr3[indexC] = arr1[indexA];
    indexA++;
    indexC++;
}

while(indexB<14) {
    arr3[indexC] = arr2[indexB];
    indexB++;
    indexC++;
}

for (int i=0; i<34; i++)
    cout << arr3[i] << " ";
return 0;
}

Может кто-нибудь посоветовать мне лучший алгоритм для "сортировки слиянием", который использует память "более эффективным" способом?Это также не может быть с массивами.

Большое спасибо!

Answer 1

Обычная проблема с сортировкой слиянием состоит в том, что для каждой рекурсии вы используете целую новую часть памяти. Это оказывается нужным O (N * log (n)) памяти. Оказывается, если вы немного умнее, вы можете сделать это с помощью линейной памяти O (N). Просто не создавайте новые массивы и меняйте их местами по мере необходимости внутри исходного.

Answer 2

вместо использования слияния и сортировки в основном вы могли бы использовать рекурсию, которая уменьшала бы вашу нагрузку при вычислении вручную и делении массива на две части enter code here mid = beg + end / 2; a [beg, .. ..., конец] // так a1 [прошу, ... середина] // и a2 [] середина + 1, .... конец] then call the recursion functions check the base case carefully если (большой

Answer 3

По природе алгоритма - сортировка слиянием требует дополнительного пространства того же размера массива, который вы пытаетесь отсортировать.

Своеобразный ответ на ваш вопрос.В книге «Структуры данных и алгоритмы в Java - второе издание Роберта Лафора» приведен пример, в котором вместо создания нескольких подмассивов использовался только дублированный массив одинакового размера.Вы можете найти программу @

http://homepage.cs.uiowa.edu/~sriram/21/fall07/code/mergeSort.java

Следующий пример просто объясняет сортировку слиянием простым способом.

import java.util.Arrays;
import java.util.Random;

public class SimpleMergeSort {

void mergeSort(int [] arr)
{
    if( arr.length <= 1)
        return;

    int mid = arr.length / 2;
    int [] left = Arrays.copyOfRange(arr, 0, mid);
    int [] right = Arrays.copyOfRange(arr, mid, arr.length);
    mergeSort(left);
    mergeSort(right);
    merge(left,right,arr);
}

void merge(int [] left, int [] right, int[] arr)
{
    int arrIndex = 0;
    int leftIndex = 0;
    int rightIndex = 0;

    //both left and right are not empty
    while( leftIndex < left.length && rightIndex < right.length)
    {
        if( left[leftIndex] < right[rightIndex])
        {
            arr[arrIndex++] = left[leftIndex++];
        }
        else
        {
            arr[arrIndex++] = right[rightIndex++];
        }
    }

    //if left still has some content
    while(leftIndex < left.length)
    {
        arr[arrIndex++] = left[leftIndex++];
    }

    //if right still has some content
    while(rightIndex < right.length)
    {
        arr[arrIndex++] = right[rightIndex++];
    }
}


public static void main(String[] args) {

    int [] array = new int[10];

    Random random = new Random();
    for(int i=0; i<array.length; i++)
    {
        array[i] = random.nextInt(1000);
    }
    System.out.println(Arrays.toString(array));
    SimpleMergeSort sort = new SimpleMergeSort();
    sort.mergeSort(array);
    System.out.println(Arrays.toString(array));

}

}