Сортировка слиянием (Merge Sort) (Реализация на C#)

C#   9 июля 2012  Автор статьи:  

Сортировка слиянием (Merge Sort) — основана на принципе слияния двух упорядоченных массивов. Недостатком её считается выделение дополнительной памяти в размере О(n) для хранение векторов. В данном примере формируется вектор из 10 случайных элементов. Далее происходит сортировка элементов вектора. По этапное выполнение которой можно проследить убрав комментарии в функции merge_sort.
Реализация данного алгоритма на C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sort
{
class Program
{
public static List merge(List a, List b)
//функция сливает два вектора
{
List c = new List();
//количество использованных вершин
int kol1 = 0;//в векторе а
int kol2 = 0;//в векторе b
//заполним массив c
for (int i = 0; i < a.Count + b.Count; i++) { //если мы уже полностью использовали вектора а, //то нам осталось дописать элементы вектора b if (kol1 == a.Count) { c.Add(b[kol2]); kol2++; continue; } //наоборот if(kol2 == b.Count) { c.Add(a[kol1]); kol1++; continue; } //так как наши вектора еще не полностью //использованы, то нужно сравнить какое //значение ставить на следующее место if (a[kol1] <=b [kol2]) { c.Add(a[kol1]); kol1++; } else { c.Add(b[kol2]); kol2++; } } return c; } //функция сортирует вектор public static List merge_sort(List a)
{
//если размер вектора меньше 1,
//то он отсортирован
if (a.Count <= 1) return a; List b = new List();
List c = new List();
b = a.GetRange(0, a.Count / 2);
//Console.WriteLine("vector b: ");
//foreach (var pr in b)
//{
// Console.Write(pr);
// Console.Write(' ');
//}
//Console.WriteLine("\nvector c: ");
c = a.GetRange(a.Count / 2, a.Count - (a.Count / 2));
//foreach (var pr in c)
//{
// Console.Write(pr);
// Console.Write(' ');
//}
//Console.WriteLine();
return merge(merge_sort(b), merge_sort(c));
}
static void Main()
{
List a = new List();
Random gen = new Random();
for (int i = 0; i < 10; i++) { a.Add(gen.Next(0,100)); Console.Write(a[i]); Console.Write(' '); } Console.WriteLine(); a = merge_sort(a); for (int i = 0; i < a.Count; i++) { Console.Write(a[i]); Console.Write(' '); } } } }

  • Симонеко

    ЧТО ЭТО
    Всмысле она же не сливает массив

    • В каком смысле не сливает? Функция merge принимает на вход два отсортированных массива, а на выход возвращает массив,
      который как раз и является слиянием.

Научиться программировать

  • на Delphi

  • на Java

  • на C++