Skip to content

27.11.2011

Сортировка выбором, вставками, слиянием и другие

Начнем с сортировки выбором:

Алгоритм

  1. выбрать наименьшее число;
  2. поменять его местами с первым числом массива;
  3. повторить 1) и 2) для еще не упорядоченной  части массива.

Первые два пункта придется повторить n – 1 раз, где n – число элементов в массиве.

static void SortChoice(int[] x)
        {
            for (int i = 0; i < x.Length - 1; i++)
            {
                int min = x[i];
                int index = i;
                for (int j = i+1; j < x.Length; j++)
                {
                    if (x[j] < min) { min = x[j]; index = j; }
                }
                int temp = x[i];
                x[i] = min;
                x[index] = temp;
            }
        }
        static void Main(string[] args)
        {
            int[] x = { 10, 5, 6,5, 4, 2};
            SortChoice(x);
        }

Сложность O(n^2).

Сортировка вставками:

Алгоритм

В массиве имеются две области: слева  уже отсортированная, справа –  еще не отсортированная. Вначале левая область состоит из одного элемента, а правая занимает весь остальной массив.

В процессе сортировки берем первое число из не отсортированной области и вставляем его в отсортированную так, чтобы порядок в ней не нарушился. Повторяем это  n – 1 раз.

На каждом шаге алгоритма неупорядоченная область сокращается, а упорядоченная растет ровно на один элемент.

        static void PrintArray(int[] x)
        {
            for (int i = 0; i < x.Length; ++i)
            {
                Console.WriteLine(x[i]);
            }
        }
        static void Main()
        {
            int[] array = { 5, 3, 4, 99, 8, 4, 5, 2, 0, -3, 10 };
            for (int j = 1; j < array.Length; ++j){
                for (int i = j - 1; i >= 0; i--)
                {
                    if (array[i+1] >= array[i]) break;
                    int temp = array[i+1];
                    array[i + 1] = array[i];
                    array[i] = temp;
                }
            }
            PrintArray(array);
        }

Лучше все таки сначала найти позицию элемента, а потом сдвинуть массив, но мне лень переписывать код.Сложность O(n^2). «погода, наверное, такая , что все алгоритмы квадратные» =)

Будет дополнятся по мере ухода моей лени, а также желания скопипастить код с http://algolist.manual.ru/sort/merge_sort.php.

 

 

Share your thoughts, post a comment.

(required)
(required)

Note: HTML is allowed. Your email address will never be published.

Subscribe to comments