Инверсия массива
жүктеу/скачать 1,39 Mb.
|
Сортировка массивов
лекция тезистері
- Бұл бет үшін навигация:
- Массив: 35
- 3. Сортировка слиянием (merge sort)
- 4. Быстрая сортировка (quick sort)
2. Сортировка вставками (insertion sort)
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
{ 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++;
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,39 Mb. Достарыңызбен бөлісу:
|