Сортировка графическим выбором и сортировка вставками

алгоритм

В прошлой статье была подробно описана пузырьковая сортировка и ее оптимизация, если интересно, можете посмотреть:

Как оптимизировать пузырьковую сортировку?

1. Сортировка выбором (SelectionSort)

  • Алгоритмическое мышление: Сначала найдите наименьший (самый большой) элемент в несортированной последовательности, сохраните его в начале отсортированной последовательности, затем продолжите поиск наименьшего (наибольшего) элемента из оставшихся несортированных элементов и поместите его в конец отсортированной последовательности. . И так до тех пор, пока все элементы не будут отсортированы.
  • Процесс сортировки: (в порядке возрастания по умолчанию)
  1. Найдите минимальное значение из исходной последовательности и замените его на первый элемент массива;
  2. Найдите наименьшее значение из оставшейся несортированной последовательности, кроме первого элемента, поменяйте местами второй элемент массива;
  3. Всего проходов N-1, каждый проход находит несортированное минимальное значение и помещает его после отсортированной последовательности.

Как показано на рисунке, каждый проход находит неотсортированное минимальное значение и помещает его в конец упорядоченной последовательности (т. е. текущий проход соответствует количеству элементов в массиве).

  • Java реализует сортировку выбором:
 private static <T extends Comparable<? super T>> void selectionSort(T[] nums) {
        if (null == nums || nums.length == 0) {
            throw new RuntimeException("数组为null或长度为0");
        }
        int length = nums.length;
        int minValueIndex = 0;
        T temp = null;
        for (int i = 0; i < length - 1; i++) {
            minValueIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (nums[j].compareTo(nums[minValueIndex]) < 0) {
                    minValueIndex = j;
                }
            }
            if (minValueIndex != i) {
                temp = nums[i];
                nums[i] = nums[minValueIndex];
                nums[minValueIndex] = temp;
            }
        }
    }
  • Анализ временной, пространственной сложности и стабильности:
  1. Лучшая временная сложность: в лучшем случае входная последовательность уже находится в порядке возрастания, и ей нужно сравнить n*(n-1)/2 раза, но не нужно обменивать элементы, то есть количество обменов равно : 0; таклучшая временная сложностьзаO(n^2).
  2. Наихудшая временная сложность: в худшем случае входная последовательность обратная, и каждый проход необходимо менять местами. То есть нужно сравнить n*(n-1)/2 раза, а количество обменов элементами равно: n-1 раз. такнаихудшая временная сложностьвсе ещеO(n^2).
  3. Средняя временная сложность: O(n^2).
  4. Пространственная сложность: используется только одна временная переменная, поэтомукосмическая сложностьзаO(1);
  5. стабильность:нестабильныйСортировать. Например, последовательность 3, 5, 3, 1. Результатами первого обмена являются 1, 5, 3, 3, и мы обнаруживаем, что первые 3 в исходной последовательности отстают от вторых 3.

2. Сортировка вставками (InsertSort)

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

  • Процесс сортировки:(по умолчанию в порядке возрастания)

    InsertionSort — это тот же процесс, что и при игре в покер, когда вы берете по одной покерные карты со стола и сортируете их в руке.

    Пример:

    Ввод: {4, 3, 8, 5, 2, 6, 1, 7}.

  1. Сначала возьмите первую карту с {4} в руке.

  2. Возьмите вторую карту 3, вставьте 3 в карту руки {4}, получите {3, 4}.

  3. Возьмите третью карту 8, вставьте 8 в карту {3, 4} в руке и получите {3, 4, 8}.

  4. И так далее.

    Сортировка вставками состоит из N-1 сортировок. После сортировки от p=1 до N-1 раз сортировка вставками гарантирует, что элементы от позиции 0 до позиции p будут отсортированы. которыйСортировка вставками использует уже упорядоченную позицию от позиции 0 до позиции p-1.условия,Вставляет элемент в позицию p, просматривая соответствующую позицию вперед.

    Как показано: на проходе p мы перемещаем элемент в позиции p влево, пока он не будет найден в правильной позиции среди первых элементов p+1 (включая элемент в текущей позиции).

  • Java реализует сортировку вставками

    private static <T extends Comparable<? super T>> void insertSort(T[] nums) {
          if (null == nums || nums.length == 0) {
              throw new RuntimeException("数组为null或长度为0");
          }
          int length = nums.length;
          T temp = null;
          int i = 0;
          for (int p = 1; p < length; p++) {
              temp = nums[p];
              for (i = p; i > 0 && (temp.compareTo(nums[i - 1]) < 0); i--) {
                  nums[i] = nums[i - 1];
              }
              nums[i] = temp;
          }
      }

  • Анализ временной, пространственной сложности и стабильности:

  1. Лучшая временная сложность: в лучшем случае последовательность уже в порядке возрастания, в этом случае операцию сравнения нужно выполнить n-1 раз. которыйлучшая временная сложностьзаO(n).
  2. Наихудшая временная сложность: в худшем случае последовательность находится в порядке убывания, тогда всего требуется n(n-1)/2 сравнений; количество ходов (операций присваивания) равно количеству сравнений минус n-1 раз (потому что каждый цикл сравнения на единицу больше, чем присваивание, всего n-1 циклов), то есть n(n-1)/2 - (n-1); поэтомунаихудшая временная сложностьзаO(n^2).
  3. Средняя временная сложность: O(n^2).
  4. Пространственная сложность: используется только одна временная переменная, поэтомукосмическая сложностьзаO(1);
  5. стабильность:стабильность.

3. Резюме

​сортировка выборомОсновное преимущество связано с перемещением данных. Если элемент находится в правильном конечном положении, он не будет перемещен.Сортировка выбором меняет местами пару элементов за раз, по крайней мере один из них будет перемещен в свою конечную позицию, поэтому сортировка таблицы из n элементов дает в общей сложности n-1 перестановок.Из всех методов сортировки, которые полностью полагаются на обмен для перемещения элементов, сортировка выбором является очень хорошей. Лучшая и наихудшая временная сложность сортировки выбором равна O(n^2), а пространственная сложность — O(1), что относится к нестабильной сортировке.

​Сортировка вставкамиНе подходит для сортировки приложений с большими объемами данных. Однако, если объем данных, подлежащих сортировке, невелик, например порядка менее тысячи, или если известно, что входные элементы расположены примерно по порядку, то сортировка вставками по-прежнему является хорошим выбором.Лучшая временная сложность сортировки вставками — O(n), наихудшая временная сложность — O(n^2), а пространственная сложность — O(1), что относится к стабильной сортировке.

Категории