Можете ли вы предоставить альтернативные алгоритмы для сортировки массивов?

Question

Я написал следующий метод, который сортирует массив, копируя самые большие значения в другой массив.Я хотел бы увидеть альтернативы этому подходу.например, подход, который меняет значения в самом первичном массиве, тем самым устраняя необходимость во вторичном массиве для копирования значений.

Я не хочу использовать предварительно написанные методы библиотеки .net, такие как Array.sort или т. Д., Поскольку моя главная цель - только попрактиковаться в написании алгоритмов.Слабые стороны приведенного ниже кода и его недостатки и то, как его можно улучшить, будут высоко оценены.

спасибо

private static void sortArray(int[] array)
{
    int[] sorted = new int[array.Length];
    int curMax = 0;      
    int bigIndex = 0;  

    for (int i = 0; i < array.Length; i++)
    {
        for (int j = 0; j < array.Length; j++)
        {
            if (array[j] > curMax)
            {
                bigIndex = j;
                curMax = array[j];
            }
        }

        sorted[i] = array[bigIndex];
        array[bigIndex] = 0;
        curMax = 0;
    }
}

пример пузырьковой сортировки:

 private static void sortArray(int[] array)
        {

            bool lastExchange;
            do
            {

                lastExchange = false;

                for (int i = 1; i < array.Length; i++)
                {

                    if (array[i - 1] > array[i])
                    {
                        lastExchange = true;
                        int temp = array[i - 1];
                        array[i - 1] = array[i];
                        array[i] = temp;
                    }
                }
            } while (lastExchange);

        }

Answer 1

Ваш алгоритм (извините, что сказал это) довольно неэффективен, как может быть алгоритм сортировки. Например, вы можете сделать его более эффективным, просто поменяв местами элементы в массиве, вместо того, чтобы оставлять неиспользуемые значения в массиве. Сделав это, вы уменьшите количество элементов, которые вы должны просматривать для каждой итерации:

private static void sortArray(int[] array) {
  for (int i = 0; i < array.Length; i++) {
    int largest = array[i];
    int largeIndex = i;
    for (int j = i + 1; j < array.Length; j++) {
      if (array[j] > largest) {
        largeIndex = j;
        largest = array[j];
      }
    }
    array[largeIndex] = array[i];
    array[i] = largest;
  }
}

(Еще одна проблема вашего алгоритма заключается в том, что он не работает с отрицательными или нулевыми значениями.)

Один из самых простых алгоритмов сортировки - пузырьковая сортировка :

private static void sortArray(int[] array) {
  bool cont = true;
  while (cont) {
    cont = false;
    for (int i = 1; i < array.Length; i++) {
      if (array[i - 1] > array[i]) {
        cont = true;
        int temp = array[i - 1];
        array[i - 1] = array[i];
        array[i] = temp;
      }
    }
  }
}

Answer 2

Посмотрите на http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms примеры алгоритмов сортировки.Вы можете перейти к любому, который захотите, и попытаться реализовать их самостоятельно, основываясь на их описании.

В настоящий момент у вас есть сортировка выбора, которую довольно легко реализовать, но она не так хороша, какнасколько алгоритмы сортировки идут.Хороший алгоритм сортировки будет иметь n (log n) сложность (обычно это log n search * n items).

Answer 3

Мне нравится Сортировка ведер и она расширена Сортировка по радикалам Лучше всего! две причины:

1. не могу пропустить O (n) над O (nLog (n))
2. Я люблю хеш-таблицы, и это своего рода концепция

Также взгляните на Сортировка кучи , что является хорошим алгоритмом.

Answer 4

Вы уже думали о реализации следующих алгоритмов сортировки:

Bubble Sort Быстрая сортировка

Привет,

Обновление 1:
Очень хорошая страница об алгоритмах сортировки (визуализированная): http://www.sorting -algorithms.com /