Быстрая сортировка (Quick Sort) (Реализация на C#)

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

В данной статье представлена реализация алгоритма быстрой сортировки (QSort / Quick Sort). Значения l и r передаваемые в функцию quickSort определяют диапазон в массиве, где будет произведена сортировка, поэтому для полной сортировки необходимо передать l = 0 и r = n — 1, где n — размерность массива. Если необходимо сортировать массивы других типов данных отличных от int, то стоит только заменить тип параметра в функции и передать соответствующий массив для сортировки.
Реализация данного алгоритма на C#:

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

namespace Sort
{
class Program
{
static void quickSort(int[] a, int l, int r)
{
int temp;
int x = a[l + (r - l) / 2];
//запись эквивалентна (l+r)/2,
//но не вызввает переполнения на больших данных
int i = l;
int j = r;
//код в while обычно выносят в процедуру particle
while (i <= j) { while (a[i] < x) i++; while (a[j] > x) j--;
if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } if (i < r) quickSort(a, i, r); if (l < j) quickSort(a, l, j); } static void Main() { // Считываем размер массива, // который необходимо отсортировать int size; size = Convert.ToInt32(Console.ReadLine()); // Динамически выделяем память под // хранение массива размера size //считываем строку string str = Console.ReadLine(); //разбиваем по пробелам string[] mas = str.Split(' '); int[] a = new int [size]; for (int i = 0; i < size; i++) { a[i] = int.Parse(mas[i]); } quickSort(a, 0, size - 1); // Выводим отсортированный массив for (int i = 0; i < size; i++) { Console.Write(a[i]); Console.Write(' '); } } } }

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

  • на Delphi

  • на Java

  • на C++