Сортировка слиянием (рекурсивная и нерекурсивная версии)

java
  1. private static int[] sortMerge(int[] arr) {
  2.     int len = arr.length;
  3.     if (len < 2)
  4.         return arr;
  5.     int middle = len / 2;
  6.     return merge(sortMerge(Arrays.copyOfRange(arr, 0, middle)),
  7.             sortMerge(Arrays.copyOfRange(arr, middle, len)));
  8. }
  9.  
  10. private static void sortMergeNoRecursive(int[] arr) {
  11.     int len = arr.length;
  12.     int n = 1; // кратность сравнений (сравнивать по 1-му елем., двум
  13.     int shift; // сдвиг в перебираемом массиве
  14.     int two_size;// количество елементов для 2-го массива
  15.     int[] arr2;
  16.     while (n < len) {
  17.         shift = 0;
  18.         while (shift < len) {
  19.             if (shift + n >= len)
  20.                 break;
  21.             two_size = (shift + n * 2 > len) ? (len - (shift + n)) : n;
  22.             arr2 = merge(
  23.                     Arrays.copyOfRange(arr, shift, shift + n),
  24.                     Arrays.copyOfRange(arr, shift + n, shift + n + size));
  25.             for (int i = 0; i < n + two_size; ++i)
  26.                 arr[shift + i] = arr2[i]; // замена на отсортрованное
  27.             shift += n * 2;
  28.         }
  29.         n *= 2;
  30.     }
  31. }
  32.  
  33. private static int[] merge(int[] arr_1, int[] arr_2) {
  34.     int len_1 = arr_1.length, len_2 = arr_2.length;
  35.     int a = 0, b = 0, len = len_1 + len_2; // a, b - счетчики в массивах
  36.     int[] result = new int[len];
  37.     for (int i = 0; i < len; i++) {
  38.         if (b < len_2 && a < len_1) {
  39.             if (arr_1[a] > arr_2[b])
  40.                 result[i] = arr_2[b++];
  41.             else
  42.                 result[i] = arr_1[a++];
  43.         } else if (b < len_2) {
  44.             result[i] = arr_2[b++];
  45.         } else {
  46.             result[i] = arr_1[a++];
  47.         }
  48.     }
  49.     return result;
  50. }
По скорости примерно одинаковые. Рекурсивная версия немного быстрее (по крайней мере на массивах длинной менее 100 000)
Назад

Реклама

Мы в соцсетях

tw tg yt gt