Инверсия массива



бет2/2
Дата19.03.2022
өлшемі1,39 Mb.
#136132
1   2
Байланысты:
Сортировка массивов









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

Массив:

35

12

28

47

20

31

1-итерация

12

35

28

47

20

31

2-итерация

12

28

35

47

20

31

3-итерация

12

28

35

47

20

31

4-итерация

12

20

28

35

47

31

5-итерация

12

20

28

31

35

47



using System;


class Program


{
//метод обмена элементов
static void Swap(ref int e1, ref int e2)
{
var temp = e1;
e1 = e2;
e2 = temp;
}

//сортировка вставками


static int[] InsertionSort(int[] array)
{
for (var i = 1; i < array.Length; i++)
{
var key = array[i];
var j = i;
while ((j > 1) && (array[j - 1] > key))
{
Swap(ref array[j - 1], ref array[j]);
j--;
}

array[j] = key;


}

return array;


}

static void Main(string[] args)


{
Console.WriteLine("Сортировка вставками");
Console.Write("Введите элементы массива: ");
var parts = Console.ReadLine().Split(new[] { " ", ",", ";" }, StringSplitOptions.RemoveEmptyEntries);
var array = new int[parts.Length];
for (int i = 0; i < parts.Length; i++)
{
array[i] = Convert.ToInt32(parts[i]);
}

Console.WriteLine("Упорядоченный массив: {0}", string.Join(", ", InsertionSort(array)));


Console.ReadLine();


}
}

Без swap
static int[] InsertionSort(int[] array)


{

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


{
var key = array[i];
var j = i;
while ((j > 1) && (array[j - 1] > key))
{
array[j] = array[j - 1];
j--;
}

array[j] = key;


}

return array;


}





3. Сортировка слиянием (merge sort)





using System;


class Program


{
//метод для слияния массивов
static void Merge(int[] array, int lowIndex, int middleIndex, int highIndex)
{
var left = lowIndex;
var right = middleIndex + 1;
var tempArray = new int[highIndex - lowIndex + 1];
var index = 0;

while ((left <= middleIndex) && (right <= highIndex))


{
if (array[left] < array[right])
{
tempArray[index] = array[left];
left++;
}
else
{
tempArray[index] = array[right];
right++;
}

index++;
}


for (var i = left; i <= middleIndex; i++)


{
tempArray[index] = array[i];
index++;
}

for (var i = right; i <= highIndex; i++)


{
tempArray[index] = array[i];
index++;
}

for (var i = 0; i < tempArray.Length; i++)


{
array[lowIndex + i] = tempArray[i];
}
}

//сортировка слиянием


static int[] MergeSort(int[] array, int lowIndex, int highIndex)
{
if (lowIndex < highIndex)
{
var middleIndex = (lowIndex + highIndex) / 2;
MergeSort(array, lowIndex, middleIndex);
MergeSort(array, middleIndex + 1, highIndex);
Merge(array, lowIndex, middleIndex, highIndex);
}

return array;


}

static int[] MergeSort(int[] array)


{
return MergeSort(array, 0, array.Length - 1);
}
static void Main(string[] args)
{
Console.WriteLine("Сортировка слиянием");
Console.Write("Введите элементы массива: ");
var s = Console.ReadLine().Split(new[] { " ", ",", ";" }, StringSplitOptions.RemoveEmptyEntries);
var array = new int[s.Length];
for (int i = 0; i < s.Length; i++)
{
array[i] = Convert.ToInt32(s[i]);
}

Console.WriteLine("Упорядоченный массив: {0}", string.Join(", ", MergeSort(array)));


Console.ReadLine();


}
}






4. Быстрая сортировка (quick sort)







using System;

class Program


{
//метод для обмена элементов массива
static void Swap(ref int x, ref int y)
{
var t = x;
x = y;
y = t;
}

//метод возвращающий индекс опорного элемента


static int Partition(int[] array, int minIndex, int maxIndex)
{
var pivot = minIndex - 1;
for (var i = minIndex; i < maxIndex; i++)
{
if (array[i] < array[maxIndex])
{
pivot++;
Swap(ref array[pivot], ref array[i]);
}
}

pivot++;
Swap(ref array[pivot], ref array[maxIndex]);


return pivot;
}

//быстрая сортировка


static int[] QuickSort(int[] array, int minIndex, int maxIndex)
{
if (minIndex >= maxIndex)
{
return array;
}

var pivotIndex = Partition(array, minIndex, maxIndex);


QuickSort(array, minIndex, pivotIndex - 1);
QuickSort(array, pivotIndex + 1, maxIndex);

return array;


}

static int[] QuickSort(int[] array)


{
return QuickSort(array, 0, array.Length - 1);
}

static void Main(string[] args)


{
Console.Write("N = ");
var len = Convert.ToInt32(Console.ReadLine());
var a = new int[len];
for (var i = 0; i < a.Length; ++i)
{
Console.Write("a[{0}] = ", i);
a[i] = Convert.ToInt32(Console.ReadLine());
}

Console.WriteLine("Упорядоченный массив: {0}", string.Join(", ", QuickSort(a)));


Console.ReadLine();


}
}


Достарыңызбен бөлісу:
1   2




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет