Фильтрация и проверка данных PHP. Частые ошибки

Материал предназначен в основном для начинающих веб-программистов.

Введение.
Часто ко мне обращаются клиенты, у которых установлены самописные CMS или модули, написанные начинающими веб-программистами, которые не понимают, что нужно для защиты данных и зачастую копируют функции фильтрации, не задумываясь о том как они работают и что именно нужно с ними делать.

Здесь я постараюсь описать как можно подробнее частые ошибки при фильтрации данных в PHP скрипте и дать простые советы как правильно выполнить фильтрацию данных.

В сети много статей по поводу фильтрации данных, но они как правильно не полные и без подробные примеров.

Разбор полетов.

Фильтрация. Ошибка №1

Для числовых переменных используется такая проверка:

$number = $_GET['input_number'];
if (intval($number))
{
... выполняем SQL запрос ...
}


Почему она приведет к SQL инъекции? Дело в том, что пользователь может указать в переменной input_number значение:
1'+UNION+SELECT


В таком случаи проверка будет успешно пройдена, т.к. функция intval получает целочисленное значение переменной, т.е. 1, но в самой переменной $number ничего не изменилось, поэтому весь вредоносный код будет передан в SQL запрос.
Правильная фильтрация:
$number = intval($_GET['input_number']);
if ($number)
{
... выполняем SQL запрос ...
}


Конечно, условие может меняться, например если вам нужно получить только определенный диапазон:
if ($number >= 32 AND $number <= 65)



Если вы используете чекбоксы или мультиселекты с числовыми значениями, выполните такую проверку:
$checkbox_arr = array_map('intval', $_POST['checkbox']);


array_map
Так же встречаю фильтрацию в виде:
$number = htmlspecialchars(intval($_GET['input_number']));

htmlspecialchars
Или:
$number = mysql_escape_string(intval($_GET['input_number']));


mysql_escape_string

Ничего кроме улыбки это не может вызвать :)

Фильтрация. Ошибка №2.

Для стринг-переменных используется такая фильтрация:
$input_text = addslashes($_GET['input_text']);


Функция addslashes экранирует спец. символы, но она не учитывает кодировку БД и возможен обход фильтрации. Не стану копировать текст автора, который описал данную уязвимость и дам просто ссылку Chris Shiflett (перевод можно поискать в рунете).

Используйте функцию mysql_escape_string или mysql_real_escape_string, пример:
$input_text = mysql_escape_string($_GET['input_text']);


Если вы не предполагаете вхождение html тегов, то лучше всего сделать такую фильтрацию:
$input_text = strip_tags($_GET['input_text']);
$input_text = htmlspecialchars($input_text);
$input_text = mysql_escape_string($input_text);

strip_tags — убирает html теги.
htmlspecialchars — преобразует спец. символы в html сущности.
Так вы защитите себя от XSS атаки, помимо SQL инъекции.
Если же вам нужны html теги, но только как для вывода исходного кода, то достаточно использовать:
$input_text = htmlspecialchars($_GET['input_text']);
$input_text = mysql_escape_string($input_text);



Если вам важно, чтобы значение переменной не было пустой, то используйте функцию trim, пример:
$input_text = trim($_GET['input_text']);
$input_text = htmlspecialchars($input_text);
$input_text = mysql_escape_string($input_text);



Фильтрация. Ошибка №3.

Она касается поиска в БД.
Для поиска по числам используйте фильтрацию, описанную в первой ошибке.
Для поиска по тексту используйте фильтрацию, описанную во второй ошибке, но с оговорками.
Для того, чтобы пользователь не смог выполнить логическую ошибку, нужно удалять или экранировать спец. символы SQL.
Пример без доп. обработки строки:
$input_text = htmlspecialchars($_GET['input_text']); // Поиск: "%"
$input_text = mysql_escape_string($input_text);


На выходе у нас получится запрос вида:
... WHERE text_row LIKE '%".$input_text."%' ... // WHERE text_row LIKE '%%%'


Это значительно увеличит нагрузку на базу.
В своём скрипте я использую функцию, которая удаляет нежелательные мне символы из поиска:
function strip_data($text)
{
    $quotes = array ("\x27", "\x22", "\x60", "\t", "\n", "\r", "*", "%", "<", ">", "?", "!" );
    $goodquotes = array ("-", "+", "#" );
    $repquotes = array ("\-", "\+", "\#" );
    $text = trim( strip_tags( $text ) );
    $text = str_replace( $quotes, '', $text );
    $text = str_replace( $goodquotes, $repquotes, $text );
    $text = ereg_replace(" +", " ", $text);
            
    return $text;
}


Конечно, не все из выше перечисленных символов представляют опасность, но в моём случаи они не нужны, поэтому выполняю поиск и замену.
Пример использования фильтрации:
$input_text = strip_data($_GET['input_text']);
$input_text = htmlspecialchars($input_text);
$input_text = mysql_escape_string($input_text);


Также советую сделать ограничение по количеству символов в поиске, хотя бы не меньше 3-х, т.к. если у вас будет большое количество записей в базе, то поиск по 1-2 символам будет значительно увеличивать нагрузку на БД.

Фильтрация. Ошибка №4.

Не фильтруются значения в переменной $_COOKIE. Некоторые думаю, что раз эту переменную нельзя передать через форму, то это гарантия безопасности.
Данную переменную очень легко подделать любым браузером, отредактировав куки сайта.
Например, в одной известной CMS была проверка, используемого шаблона сайта:
if (@is_dir ( MAIN_DIR . '/template/' . $_COOKIE['skin'] )){
	$config['skin'] = $_COOKIE['skin'];
}
$tpl->dir = MAIN_DIR . '/template/' . $config['skin'];


В данном случаи можно подменить значение переменной $_COOKIE['skin'] и вызвать ошибку, в результате которой вы увидите абсолютный путь до папки сайта.
Если вы используете значение куков для сохранения в базу, то используйте одну из выше описанных фильтраций, тоже касается и переменной $_SERVER.

Фильтрация. Ошибка №5.

Включена директива register_globals. Обязательно выключите её, если она включена.
В некоторых ситуациях можно передать значение переменной, которая не должна была передаваться, например, если на сайте есть группы, то группе 2 переменная $group должна быть пустой или равняться 0, но достаточно подделать форму, добавив код:
<input type="text" name="group" value="5" />


В PHP скрипте переменная $group будет равна 5, если в скрипте она не была объявлена со значением по умолчанию.

Фильтрация. Ошибка №6.

Проверяйте загружаемые файлы.
Выполняйте проверку по следующим пунктам:
1. Расширение файла. Желательно запретить загрузку файлов с расширениями: php, php3, php4, php5 и т.п.
2. Загружен ли файл на сервер move_uploaded_file
3. Размер файла

Проверка. Ошибка №1.

Сталкивался со случаями, когда для AJAX запроса (например: повышение репутации) передавалось имя пользователя или его ID (кому повышается репутация), но в самом PHP не было проверки на существование такого пользователя.
Например:
$user_id = intval($_REQUEST['user_id']);
... INSERT INTO REPLOG SET uid = '{$user_id}', plus = '1' ...
... UPDATE Users SET reputation = reputation+1 WHERE user_id = '{$user_id}' ...


Получается мы создаем запись в базе, которая совершенно бесполезна нам.

Проверка. Ошибка №2.

При выполнении различного рода действий (добавление, редактирование, удаление) с данными не забывайте проверять права пользователя на доступ к данной функции и дополнительные возможности (использование html тегов или возможность опубликовать материал без проверки).

Давно исправлял в одном модуле форума подобную ошибку, когда любой пользователь мог отредактировать сообщение администрации.

Проверка. Ошибка №3.

При использовании нескольких php файлов сделайте простую проверку.
В файле index.php (или в любом другом главном файле) напишите такую строчку перед подключением других php файлов:
define ( 'READFILE', true );


В начале других php файлов напишите:
if (! defined ( 'READFILE' ))
{
	exit ( "Error, wrong way to file.<br><a href=\"/\">Go to main</a>." );
}


Так вы ограничите доступ к файлам.

Проверка. Ошибка №4.

Используйте хеши для пользователей. Это поможет предотвратить вызов той или иной функции путём XSS.
Пример составления хеша для пользователей:
$secret_key = md5( strtolower( "http://site.ru/" . $member['name'] . sha1($password) . date( "Ymd" ) ) ); // $secret_key - это наш хеш


Далее во все важные формы подставляйте инпут со значением текущего хеша пользователя:
<input type="hidden" name="secret_key" value="$secret_key" />


Во время выполнения скрипта осуществляйте проверку:
if ($_POST['secret_key'] !== $secret_key)
{
exit ('Error: secret_key!');
}



Проверка. Ошибка №5.

При выводе SQL ошибок сделайте простое ограничение к доступу информации. Например задайте пароль для GET переменной:
if ($_GET['passsql'] == "password")
{
... вывод SQL ошибки ...
}
else
{
... Просто информация об ошибке, без подробностей ...
}


Это позволит скрыть от хакера информацию, которая может ему помочь во взломе сайта.

Проверка. Ошибка №5.
Старайтесь не подключать файлы, получая имена файлов извне.
Например:
if (isset($_GET['file_name']))
{
include $_GET['file_name'] .'.php';
}


Используйте переключатель switch:
switch($_GET['file_name'])
{         
         case 'file_1':
         include 'file_1.php';    
         break;     
         
         default:
         include 'file_0.php';    
         break;
}


В таком случаи вы предотвратите подключение файлов, которые не были вами предусмотрены.

Совет.

Для большей надежности используйте один из готовых и популярных классов для фильтрации данных, дабы самому не пропустить какие-то вредоносные символы/данные. Также в этих классах часто имеется возможность выбора фильтра данных.

UPD: Поправил пост. Перенес все советы по поводу функций и переменных, которые были в комментариях.

Добавлено: 19 Ноября 2021 07:27:05 Добавил: Андрей Ковальчук

Как в mysql лучше всего хранить ip адрес?

Наиболее удобно ip-адрес в MySQL хранить в типе INT. Причём обязательно UNSIGNED (беззнаковый), чтобы адреса выше 127. вполне вмещались в эти 4 байта.

`ip` int(10) unsigned NOT NULL

Тип INT более удобен для хранения ip-адресов по сравнению с CHAR(15) по двум причинам:

Требует меньше памяти (4 байта INT против 15 байт CHAR). Как результат, таблица занимает меньше места на диске, а скорость выполнения запросов возрастает, т.к. индекс меньшего размера.
Удобно производить выборки по диапазонам адресов и маскам, а также делать сортировку (получается обычная сортировка по числам).
Имеется недостаток по сравнению с хранением ip как plaintxt (char или varchar) в mysql:

Необходимость дополнительного преобразования ip-строки в число и наоборот для удобства восприятия. Для чего используются функции INET_ATON и INET_NTOA (см. дальше). Но это ведь не проблема.
Как видно, достоинства хранения ip в UNSIGNED INT сильно превосходят единственный недостаток.

Функции преобразования ip-адреса в mysql:

INET_ATON() — для преобразования IP адреса в число,
INET_NTOA() — для обратного преобразования числа в IP адрес.

Для простоты запоминания нужно знать расшифровку аббревиатуры:

ATON — Address TO Number (адрес в число),
NTOA — Number TO Address (число в адрес).

Примеры преобразования IP в mysql:
SELECT INET_NTOA(ip) FROM tablename LIMIT 10;  # выведет ip в обычном строковом формате
 
SELECT INET_ATON('127.0.0.1');    #2130706433
SELECT INET_ATON('93.125.99.10');  #1568498442
 
SELECT INET_NTOA(2130706433);   #127.0.0.1
SELECT INET_NTOA(1568498442);   #93.125.99.10

Аналогичные функции преобразования ip-адреса в PHP:

ip2long() — для преобразования IP адреса в число;
long2ip() — для обратного преобразования числа в IP адрес.
ip2long('127.0.0');     //false
ip2long('93.125.99.10'); //1568498442
ip2long('127.0.0.1');    //2130706433
ip2long('192.168.0.1'); //3232235521

long2ip('1568498442'); //93.125.99.10
long2ip('2130706433'); //127.0.0.1
long2ip('3232235521'); //192.168.0.1

Задача. Нам нужно получить все записи, которые находятся в диапазоне адресов 148.100.0.0 — 158.255.255.255. Если хранить IP в виде строк, то пришлось бы производить поиск с помощью регулярных выражений, а запрос выполнялся бы очень долго.

В случае хранения IP-адреса в типе INT sql-запрос будет таким:
SELECT .... WHERE ip BETWEEN INET_ATON('148.100.0.0') AND INET_ATON('158.255.255.255')

Добавлено: 14 Ноября 2021 07:17:57 Добавил: Андрей Ковальчук

MySQL функция CURDATE


В этом учебном пособии вы узнаете, как использовать MySQL функцию CURDATE с синтаксисом и примерами.

Описание
MySQL функция CURDATE возвращает текущую дату.

Синтаксис
Синтаксис MySQL функции CURDATE:

CURDATE( )

Параметры или аргументы
Для функции CURDATE нет параметров или аргументов.

Примечание
1. Функция CURDATE возвращает текущую дату в формате ‘YYYY-MM-DD’, если используется в контексте строки.
2. Функция CURDATE возвращает текущую дату в формате YYYYMMDD, если используется в числовом контексте.
3. Функция CURDATE является синонимом функции CURRENT_DATE.
Применение
Функция CURDATE может использоваться в следующих версиях MySQL:

MySQL 5.7, MySQL 5.6, MySQL 5.5, MySQL 5.1, MySQL 5.0, MySQL 4.1, MySQL 4.0, MySQL 3.23
Пример
Рассмотрим примеры MySQL функции CURDATE, чтобы понять, как использовать функцию CURDATE в MySQL.
Например:
mysql> SELECT CURDATE();

#Результат:   2017-05-11 

mysql> SELECT CURDATE()  0;

#Результат:   20170511 

mysql> SELECT CURDATE()  1;

#Результат:   20170512

Добавлено: 19 Мая 2021 06:44:36 Добавил: Андрей Ковальчук

Как вывести все записи и разбить их по рубриками WordPress

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

Чтобы сделать подобное, мы будем использовать функцию WordPress - get_categories(). Можете найти о ней информацию, чтобы дополнительно настроить параметры вывода будущего списка. Я же покажу как вывести абсолютно все статьи всех рубрик.

Для начала как раз и настроим параметры get_categories. Создадим переменную $arg_cat и присвоим ей массив с параметрами.

<?php 
$arg_cat = array(
    'orderby'      => 'name',
    'order'        => 'ASC',
    'hide_empty'   => 1,
    'exclude'      => '',
    'include'      => '',
);

В данном масcиве базовые настройки для get_categories. Обратите внимание, что в первой строке у нас тег РНР. Он нужен если вы помещаете код в среду HTML. Если у вас уже среда РНР то этот тег не нужен. Это элементарно, но многие в пешке не замечают, а потом оставляют гневные комментарии о неработоспособности кода. Вы же не один из таких плохих вебмастеров?

orderby - сортируем категории по имени.
order - направление сортировки, указанной в параметре orderby. То бишь от А до Я или от Я до А.
hide_empty - скрывать ли пустые категории. 0 - нет. 1 - да. Рекомендую скрывать, чтобы не выводить просто названия, под которыми не будет списка.
exclude - список ID тех категорий которые нужно исключить из списка. В данном примере - таковых нет.
include - список ID тех категорий из которых только и выводить записи. В данном примере - таковых нет. Можно вывести только с пары рубрик, или с одной, например если в ней много подрубрик.
Теперь присваиваем параметры для get_categories и помещаем ее в переменную - $categories

$categories = get_categories( $arg_cat );

Далее мы проверим не пуста ли переменная $categories, то бишь, если get_categories, согласно заданным в начале параметрам нашла подходящие категории, то мы продолжаем работу. После чего, с помощью foreach, перебираем массив наших категорий что получила get_categories.

Можете прочитать по какому принципу работает foreach, подробно останавливаться на этом не буду. Эта статья материал не для новичков, поэтому если вы не знакомы з foreach. рекомендую ознакомится. Код перебора массива з рубриками, что мы получим, выглядит будет так:

if( $categories ){
    foreach( $categories as $cat ){
     
// ТУТ БУДЕТ БУДУЩИЙ КОД ЦИКЛА ДЛЯ ВЫВОДА СПИСКА
 
}   
} 
?>

Обратите внимание, что в последней строке закрывающий тег РНР. Если вы не в среде HTML, то он не нужен. Выше в статье я писал об этом.

Перебор массива пошел, теперь нужно выводить данные наших рубрик. То бишь - название рубрики и все записи, что в нее входят. В этом нам поможет - WP_Query.

С помощью WP_Query мы выведем цикл. Весь код что мы получим нужно будет поместить внутрь foreach. Для WP_Query можно и нужно задать параметры. С помощью них можно настроить какие записи вы хотите получить, их количество, сортировка и тд. Ознакомьтесь с WP_Query и узнайте все.

В нашем случаи мы будем использовать лишь 2 параметра. один из которых обязателен. Массив с параметрами поместим в переменную - $arg_posts.

$arg_posts =  array(
    'cat' => $cat->cat_ID,
    'posts_per_page' => -1,
);

cat - тот самый обязательный параметр. В нем мы указываем что нужно выводить записи только той категории, которую выбрал перебор foreach из массива категорий. $cat->cat_ID - параметр, который менять нельзя.
posts_per_page - указав значение -1, мы разрешили выводить все записи рубрики. Если хотите выводить только последние 5, то укажите число 5.
Теперь присваиваем параметры для WP_Query и помещаем ее в переменную - $query.

$query = new WP_Query($arg_posts);

Далее уже строим цикл где и выведем все нужные данные.

if ($query->have_posts() ) : ?>
<a href="<?php echo get_category_link( $cat->term_id ); ?>"><h2><?php echo $cat->name; ?></h2></a>
 
<ul>
    <?php while ( $query->have_posts() ) : $query->the_post();  ?>
    <li>
        <a href="<?php the_permalink(); ?>" title="<?php the_title(); ?>"><h3><?php the_title(); ?></h3></a>
    </li>
<?php endwhile; wp_reset_postdata(); ?>
</ul>         
<?php endif; 

Разбирать подробно код не имеет смысла, это обычный цикл. Сначала проверяем есть ли посты соответствующие нашим параметрам WP_Query. Далее выводим ссылку с названием категории, список записей из которой будет выведен ниже. Вы заметили что мы обернули цикл в теги UL, для того чтобы вывести записи в виде списка, если хотите иначе - учтите. Внутри самого цикла у нас просто ссылка на запись с ее названием. Можете поместить что угодно как и в обычном цикле - миниатюру, отрывок текста, произвольные поля и тд. Все как и в обычном цикле на главной, в категориях, архивах и тд.

Теперь соберем все в кучу, чтобы получить готовый результат.

<?php 
//НАЧАЛО СПИСКА
 
$arg_cat = array(
    'orderby'      => 'name',
    'order'        => 'ASC',
    'hide_empty'   => 1,
    'exclude'      => '',
    'include'      => '',
);
$categories = get_categories( $arg_cat );
 
if( $categories ){
    foreach( $categories as $cat ){
        $arg_posts =  array(
                'posts_per_page' => -1,
                'cat' => $cat->cat_ID,
            );
    $query = new WP_Query($arg_posts);
 
if ($query->have_posts() ) : ?>
<a href="<?php echo get_category_link( $cat->term_id ); ?>"><h2><?php echo $cat->name; ?></h2></a>
 
<ul>
    <?php while ( $query->have_posts() ) : $query->the_post();  ?>
    <li>
        <a href="<?php the_permalink(); ?>" title="<?php the_title(); ?>"><h3><?php the_title(); ?></h3></a>
    </li>
<?php endwhile; wp_reset_postdata(); ?>
</ul>         
<?php endif; 
 }  } 
 
// КОНЕЦ 
?>

Данный код можно поместить в любое место темы, где хотите вывести данный список. Учтите только среда РНР или HTML.

Так же, могу предложить вам для того, чтобы посмотреть на результат, добавить страницу на сайте на которой будет пример. Для этого скачайте файл ниже, это шаблон страницы с встроенным списком. Поместите его в папку с темой. Шаблон называется - Страница со всеми записями. Далее создайте новую страницу в консоли вашего сайта WordPress. После чего в параметрах страницы укажите шаблон - Страница со всеми записями.

Сохраните настройки и смотрите страницу. Функция выведет все рубрики и записи к ним что есть на сайте.

Добавлено: 18 Мая 2021 06:35:31 Добавил: Андрей Ковальчук

Как создать бота в Телеграм для получения оповещений с форм сайта

В принципе, данная инструкция может быть актуальной и для других форм и плагинов, для которых нужен бот в Телеграм. Суть у всех одна, боты создаются одинаково. Главное что нужно после создания это Токен вашего бота и ID чата куда он добавлен или чата самого бота.

Если подключить к форме отправку на Телеграм или вы используете один из моих плагинов, то вы будете получать оповещения прям в мессенджер.

Как создать бота
1. Первым делом, у вас должен быть установлен мессенджер Telegram. На телефоне или ПК, а желательно и там и там. Я буду показывать на примере ПК, но на телефоне все то же самое.

2. Далее нужно найти через поиск в мессенджере главного бота, что создает других. Это BotFather - единственный бот, который управляет ими всеми. Используйте его для создания новых учетных записей ботов и управления существующими ботами. Найдите и нажмите на него, чтобы открылся его чат.

3. Теперь нужно запустить BotFather. Для этого нужно нажать кнопку ЗАПУСТИТЬ внизу чата или написать в чат /start, если вместо кнопки у вас поле для ввода.

4. После запуска появится список команд, переместитесь в начало сообщения и нажмите на команду /newbot или просто пропишите эту команду через поле сообщения.

5. Теперь BotFather предложит вам назвать своего бота. Это название вы будете видеть в списке контактов. В примере бот назван как testmailbot. Можете называть как угодно, например: Бот для формы контактов, Бот какого-то плагина, Мой бот с сайта и тд. Без разницы, лишь бы вы понимали что это за бот и если у вас их будет много, вы их не путали.

6. Далее BotFather предложит вам указать имя бота. Вот тут нужно быть внимательным. Имя бота вводится только латиницей и в конце должно заканчиваться на bot. В примере это testmailbot_bot. Задавайте что хотите, если имя будет существовать, BotFather вас предупредит. Так что придумайте что-то уникальное.

7. Если вы задали правильное имя, то BotFather напишет вам, что все готово и вашему боту присвоен Токен, который понадобится для доступа через HTTP API. Этот токен нам и нужен для того, чтобы формы отправляли свои данные в Телеграм.

8. Теперь найдем и запустим нашего бота. Для этого в поиске контактов в Telegram найдите бота и нажмите на него.

9. Так же нужно запустить бота. Внизу есть кнопка ЗАПУСТИТЬ или напишите в чат /start, если вместо кнопки у вас поле для ввода.

Это еще не конец. Если вы не хотите создавать групповой чат для многих ботов, если у вас одна форма или один плагин или вы хотите чтобы данные со всех форм приходили только к одному боту, что вполне нормально, то можно пропустить следующие 4 шага и перейти к пункту - 12.

8. Чтобы добавить бота в групповой чат, если вы захотите иметь несколько ботов для нескольких форм, то вам нужно перейти в настройки Telegram и выбрать пункт - Создать группу.

9. Далее нужно ввести название для группы. Вводите какое вам нравится.

10. Теперь нужно добавить участников в группу, то бишь нашего бота. Есть 2 способа. Можно просто на странице самого бота нажать на его настройки и там выбрать пункт Добавить в группу. После чего вам предложит ваши собственные группы. Выберите ту что создали только что для ботов и все. Второй вариант - нажмите на настройки группы и выберите пункт - Добавить участников.

11. Перед вами появится окно поиска, введите в поле имя своего бота, то что вводили в пункте 6. Возможно, найдется несколько ботов, но только у одного будет точное название, в нашем примере это @testmailbot_bot. Когда найдете своего бота, выделите и нажмите кнопку - Добавить.

12. Последнее что нужно сделать чтобы передавать данные с форм которые поддерживают передачу на Телеграм, это получить ID чата. Тут два варианта. Если вы используете только чат бота, то ID один, если чат группы с ботами, то ID другой. Чтобы узнать нужный ID, нужно в адресной строке браузера перейти по ссылке, которую нужно сформировать.

https://api.telegram.org/botХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХ/getUpdates

Вместо ХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХ нужно вставить тот токен, который вам дал BotFather в пункте 7, этой инструкции.

Если вы используете мой плагин с возможностью отправки оповещений на телеграмм, то можете прям в настройках плагина перейти по готовой ссылке, главное сначала добавьте в нужное поле токен и сохраните, после ссылка станет рабочей.


12. Последнее что нужно сделать чтобы передавать данные с форм которые поддерживают передачу на Телеграм, это получить ID чата. Тут два варианта. Если вы используете только чат бота, то ID один, если чат группы с ботами, то ID другой. Чтобы узнать нужный ID, нужно в адресной строке браузера перейти по ссылке, которую нужно сформировать.

https://api.telegram.org/botХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХ/getUpdates

Вместо ХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХХ нужно вставить тот токен, который вам дал BotFather в пункте 7, этой инструкции.

Если вы используете мой плагин с возможностью отправки оповещений на телеграмм, то можете прям в настройках плагина перейти по готовой ссылке, главное сначала добавьте в нужное поле токен и сохраните, после ссылка станет рабочей.

Рекомендую открывать ссылку в браузере Mozilla Firefox. В нем данные отображаются сгруппировано и очень легко понять где нужный ID. Где чат бота, где чат группы, если вы в нее добавили бота.


Как видите, по изображению видно что вначале показывает ID чата бота с моим именем, у вас будет с вашим, после того как вы напишите что-нибудь боту. Ну а далее ID группы, в которую мы добавили нашего бота в пункте 9/10.

Много непонятного, но среди этого кода нужно всего одно значение. Какое, зависит от того используете ли вы лишь бота или чат. Если только бота то ищите, ID такого типа - "id":380199086,"first_name". И з этого вам нужно только номер 380199086. Если у вас группа с ботами, то такого "id":-1011500162037. У ID груп стоит черточка в начале. Вам, опять же, нужен номер только с черточкой -1011500162037. Если, вдруг, вы добавили токен и ID в форму, а сообщения не приходят, то попробуйте другой. Сложностей не должно возникнуть.

После успешного добавления испытайте плагин или форму. Вы должны получить оповещение на Telegram, в моем примере, это выглядело так:

Теперь у вас есть и токен и нужный ID. Они вам потребуются чтобы их добавить в настройках моих плагинов, других разработчиков, в свои собственные формы, если вы такие создаете.

Добавлено: 15 Мая 2021 07:58:40 Добавил: Андрей Ковальчук

Идентификационный код, дата рождения,юзабилити

Читатели блога, проживающие в Украине, конечно, знают, что всем жителям Украины присваивается, так называемый, идентификационный код (ИК). Есть он и у меня. Но совсем недавно я узнал, что это не просто набор из 10 цифр.

Первые пять цифр – это номер дня рождения, начиная с 1 января 1900 года. Т.е. человек, родившийся 1.01.1900 получит код, начинающийся с 00001, 2.01.1900 – 00002, …, 1.01.1901 – 00366 и т.д.

Следующие четыре знака – порядковый номер человека (среди тех, кто родился в один день). Он присваивается по мере поступления информации о людях в центральную базу данных. В этих же четырех знаках заложена информация о поле человека. Она обозначается девятым символом: четное число – женский, нечетное – мужской.

Последний символ – контрольное число. Оно определяется по алгоритму, который не разглашается, дабы усложнить подделку номера.

Таким образом, не составляет труда по ИК определить дату рождения и, наоборот. Вот здесь мы подходим к вопросу о юзабилити. При оформлении кредитов, депозитов и т.д. и т.п. требуется указать и день рождения и ИК. Естественно, эти данные поступают в компьютер. Хорошая программа после ввода ИК автоматически заполнит поле с датой рождения, при вводе даты рождения подставит первые 5 цифр в поле ИК, если оно пустое, или сообщит об ошибке, если код и дата не соответствуют друг другу.

И еще одна история о юзабилити, рассказанная мне несколько лет назад коллегой. Он работал в некоторой фирме, среди сотрудников которой (в основном программистов) была женщина, плохо владеющая компьютером и занимающаяся только вводом в компьютер бумажного словаря. Изо дня в день, слово за словом, она вносила содержимое словаря в, написанную одним из программистов фирмы, для этих целей программу. Однажды программа вывела сообщение, в котором сообщала, что введенное слово неверно. Действительно, оно содержало ошибку, но как простая программа, не имеющая своего словаря догадалась об этом? Оказывается, разработчик программы, зная, что слова будут вноситься последовательно из словаря, сделал проверку на то, чтобы слова шли в алфавитном порядке. Конечно, все ошибки ввода таким образом отсечь невозможно, но, согласитесь, что реализовать такую проверку очень просто, а юзабилити продукта улучшается.

Эти два примера показывают, как небольшой ценой можно увеличить удобство пользования программой и произвести хорошее впечатление на пользователей. Думаю, что вы можете что-то улучшить в ваших программах. Попробуйте.

Добавлено: 25 Марта 2021 08:35:43 Добавил: Андрей Ковальчук

Простые методы для повышения уровня безопасности

Одним из критических пунктов практики разработки PHP приложений является постоянное удерживание в памяти важности вопросов безопасности, что совсем не так просто. Чтобы убедиться в том, что безопасность вашим вэб приложений включена в рабочий процесс, ее нужно постоянно оценивать, отслеживать и усилять.

Введение
До тех пор, пока использование фильтров и проверок данных является частью процессов безопасности, вэб разработчику нужно помнить о том, что криптография, случайные числа и запутывание кода могут существенно изменить уровень безопасности вэб приложения. Данная статья описывает несколько простых методов создания и использования случайных или уникальных значений в ваших вэб приложениях, проводит обзор использования некоторых техник запутывания кода, а также более глубоко описывает науку криптографии и ее использование в PHP.

Что Вы узнаете в данной статье
Как генерировать случайные числа в PHP
Генерация случайных паролей
Хранение паролей и аутентификация пользователей
Обзор запутывания кода в PHP
Криптография в PHP и ее применение
Генерирование случайных чисел
Генерация случайных чисел определяется несколькими способами, однако вычислительные генераторы не достигают настоящей случайности, такой как белый шум (хороший пример белого шума - отсутствие настройки в чернобелом телевизоре, который в такие моменты показывает шипящий и мерцающий экран). Вычисленные числа называются псевдо-случайными.

В PHP существует два различных метода для получения случайного значения. Рассмотрим несколько наиболее популярных функций.

<?php
rand(int $min, int $max);
mt_rand(int $min, int $max);
str_shuffle($str);
uniqid($prefix, more_entropy=);
?>

Две функции rand() и mt_rand() наиболее часто используемые функции для генерации случайных чисел в PHP. Функция rand(), более старая версия генератора, вытесняется mt_rand(), которая быстрее, более надежная и может работать с максимально большим значением типа integer на большинстве платформ. Функция str_shuffle() не совсем точно отражает сущность генератора случайных чисел. Она смешивает строку, которую получает в качестве аргумента.

<?php
//Пример использования mt_rand()
print mt_rand();//По умолчанию
echo "<br />";
print mt_rand(0, 20);//Выводит случайное целое между 0 и 20
echo "<br />";
//Примеры использования rand()
print rand();//По умолчанию
echo "<br />";
print rand(0, 25);//Выводит случайное целое между 0 и 25
echo "<br />";
//Пример использования str_shuffle()
$string = 'abcefghijklmnopqrstuvwxyz';
print str_shuffle($string);//Смешение строки $string
?>

Функции rand() и mt_rand() принимают два параметра, где $min является наименьшим целым, с котрого начинается диапазон случайных чисел, а $max представляет максимальное число, которое ограничивает диапазон случайных чисел сверху. Функция str_shuffle получает один параметр строку и выводит ее смешанный вариант. Функция str_shuffle выполняет действия, похожие на перемешивание колоды карт.

Также для генерирования случайных уникальных значений широко используется функция uniqid(). Функция uniqid() генерирует уникальный идентификатор на основе текущего времени, выраженного в микросекундах (с помощью php.net). Использование данной функции очень удобно при создании идентификаторов сессий и ключей форм.

<?php
//Пример использования uniqid()
print uniqid();//По умолчанию
echo "<br />";
print uniqid("NETTUTS", TRUE);//Добавлен дополнительный префикс и установлено значение TRUE для more_entropy 
?>

Функция uniqid() принимает два параметра. Первый добавляет префикс к результату, а второй, при значении TRUE указывает на то, что нужно сделать конец значения более неопределенным.

Генерирование случайного пароля
Существует огромное количество примеров в интернете, которые демонстрируют генерацию случайных паролей и все отлично работают. Для чего нужно генерировать случайный пароль? Ответ очень прост. Нельзя полагаться на пользователя, что он придумает достаточно надежный пароль. Генерирование случайного пароля также необходимо при регистрации пользователя или в случаях, когда пользователь теряет свой пароль. Такая практика обеспечивает получение надежного пароля сразу с самого знакомства пользователя с вашим сайтом, а также сокращает некоторое количество строк кода, когда пользователю нужно снова получить доступ.

Несколько примеров.

Пример 1

<?php
//Простая функция, которая генерирует случайный пароль
function randompassword($count){
$pass = str_shuffle('abcefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890@#%$*');
return substr($pass,3,$count);//Возвращаем пароль
}
?>

В данном примере строка смешивается с помощью str_shuffle, а затем формируется строка пароля заданной длины. Таким образом, если Вы хотите сгенерировать пароль длиной 8 символов, то нужно передать функции randompassword () значение 8.

Пример 2

<?php
//Другой пример создания случайного пароля
function anorandpass($count) {
$m_rand = mt_rand(); //генерируем случайное целое
$u_id = uniqid("MNO!@#$%^&*=+XYZ", TRUE);//создаем уникальный идентификатор с префиксом, постфиксом и повышенной энтропией
$combine = $m_rand . $u_id;// Комбинируем переменные для формирования строки
$new = str_shuffle($combine);//смешиваем строку
return substr($new, 2, $count);//возвращаем пароль
}
print anorandpass(8);
?>

Если сравнивать два примера, то первый получает статичную строку, перемешивает ее и затем возвращает, а во втором процесс имеет более динамичный характер. В примере два смешиваемая строка не является статичной, каждая ее часть генерируется случайно. В то время, как использование примера 1 будет достаточным в большинстве случаев для генерации надежного пароля, пример 2 позволяет нам быть уверенным, что длина строки и набор символов будут изменяться при использовании, что существенно снижает шансы получить копию пароля..

Давление на пользователя использовать сложный пароль для доступа к ресурсам сайта может отпугнуть посетителей или привести к отказу от регистрации. Зачастую нужно находить компромисс между желаемым трафиком и уверенностью в безопасности программного комплекса. Хорошей практикой является обеспечение возможности для ваших пользователей выбрать между созданием своего собственного пароля или генерацией случайной строки в системе.

Добавление шума к паролю для улучшения безопасности.
Добавление шума к паролю является эффективным способом для увеличения безопасности учетных записей ваших пользователей даже в случае если злодей получил доступ к вашей базе данных. Если все сделано правильно. Если злодей может получить доступ к методу добавления шума, то он может получить расширенные полномочия для управления системой. Поэтому использование техники случайных чисел при хранении пароля делают процесс захвата очень сложным, особенно в условиях, когда информация пользователей и контент хранится в разных базах данных.

Почему и как?
Наблюдения показывают, что конечный пользователь старается обеспечить себе как можно более простой способ обеспечения безопасности Обычно используются пароли, которые легко запомнить, и даже используется один пароль для доступа к нескольким сайтам. Легко запоминающиеся пароли обычно представляют собой общеупотребительные слова или некоторые виды значений (например 12345, QWERTY). Разработчики часто смеются над такой практикой, существенно изменить положение в данной ситуации нет возможности.

Для того, чтобы вэб приложение использовало добавление шума в пароль, нужно где-то хранить процедуру. Не рекомендуется использовать одинаковый шум для всех паролей базы данных, нужно генерировать для каждого пароля индивидуальный шум. Создание полноценной системы регистрации пользователей со всеми колокольчиками и свистками выходит за рамки данного урока, однако мы сделаем простую систему, которая позволит продемонстрировать генерацию шума и использование методов случайных чисел.:

1. Соединение с базой
Здесь описана структура таблицы SQL, которую мы будем использовать.

CREATE TABLE IF NOT EXISTS `users` (
`usr_id` int(11) NOT NULL AUTO_INCREMENT,
`usr_name` varchar(24) NOT NULL,
`usr_pass` varchar(32) NOT NULL,
`usr_email` varchar(255) NOT NULL,
`usr_salt` varchar(255) NOT NULL,
PRIMARY KEY (`usr_id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 ;

<?php
/*db_config.php*/
//Конфигурация базы данных
$db_host ="localhost" ; //располагается на том же сервере, что и сайт
$db_name = "thedbname"; //имя таблицы базы данных
$db_usr = "username"; //имя пользователя базы данных
$db_pass = "password";//пароль пользователя
//Устанавливаем соединение с MySQL и выбираем базу данных для использования
mysql_connect($db_host, $db_usr, $db_pass) or die("MySQL Error: " . mysql_error());
mysql_select_db($db_name) or die("MySQL Error: " . mysql_error());
?>

2. Файл регистрации
<?php
/*registration.php*/
//требуется db_config.php
require ('db_config.php');
//Проверяем, готовность данных в отправленной форме
if(!empty($_POST['username']) && !empty($_POST['email']) && !empty($_POST['password'])) {
//Готовим данные
$username = mysql_real_escape_string($_POST['username']);
$email = mysql_real_escape_string($_POST['email']);
$password = mysql_real_escape_string($_POST['password']);
//Генерируем надежный уникальный шум
$salt_gen = uniqid(mt_rand());
//Комбинируем email, пароль и шум вместе
$combine = $email . $password . $salt_gen;
//md5 вычисляет хэш комбинированного пароля * Примечание: md5 используется как пример
$newpassword = md5($combine);
//Вставляем значения в базу данных
$registerquery = mysql_query("INSERT INTO users (usr_name, usr_pass, usr_email, usr_salt) VALUES ('".$username."', '".$newpassword."', '".$email."', '".$salt_gen."')") or die("MySQL Error: ".mysql_error());
//Обратная связь с пользователем о результате операции
if ($registerquery) {
echo '<h1>Успешно</h1>';
} else {
echo '<h1>Ошибка</h1>';
}
}
?>

Рассмотрим код PHP. Для упрощения мы включили конфигурационный файл нашей базы данных. PHP проверяет готовность данных в отправленной форме по значению переменных $_POST. Если они не пустые, то скрипт подготавливает данные для вставки их в базу. Затем генерируется шум с использованием uniqid() и mt_rand() и сохраняется в переменной $salt_gen. Далее комбинируется $password и шум. А затем вычисляется хэш для скомбинированного значения с помощью md5.

Также в комбинацию пароля и шума добавляется email пользователя. Если злодей получит доступ к базе данных и сумеет прочитать значение шума, то использование email в комбинации является дополнительным препятствием на его пути, потому что нужно дополнительно исследовать код программы. А насколько случаен и уникален email?

В оставшемся коде PHP происходит добавление данных в базу и вывод информационного сообщения для пользователя. Осталось только написать HTML файл для завершения системы.

<!DOCTYPE html>
<html>
<head>
</head>
<body>
<form action="" method="post">
<label for="username">Введите имя пользователя</label>
<input type="text" name="username" /><br />
<label for="email">Email:</label>
<input type="text" name="email" /><br />
<label for="password">Пароль:</label>
<input type="password" name="password" /><br />
<input type="submit" name="submit" value="Отправить" />
</form>
</body>
</html>

Это простая HTML форма, которая предназначена для ввода имени пользователя, email, и пароля. Ничего необычного.

3. Аутентификация пользователя
Итак, у нас есть форма регистрации пользователя, которая сохраняет данные в базе. Нужно создать страницу входа на сервер, которая будет получать данные из базы и проводить аутентификацию пользователя. PHP код:

<?php
/*login.php*/
// требуется db_config.php
require ('db_config.php');
//Проверяется, заполнены ли поля формы
if(!empty($_POST['username']) && !empty($_POST['password'])) {
//Готовятся данные
$username = mysql_real_escape_string($_POST['username']);
$password = mysql_real_escape_string($_POST['password']);
//Получаем строку, которая соответствует имени пользователя в форме
$grab_row = mysql_query("SELECT * FROM users WHERE usr_name = '".$username."'") or die ("MySQL Error: ".mysql_error());
//Если получена только одна строка
if (mysql_num_rows($grab_row) == 1) {
//Создаем массив из полей
$row = mysql_fetch_array($grab_row);
//Сохраняем шум пользователя
$salt = $row['usr_salt'];
//Сохраняем email
$email = $row['usr_email'];
//Комбинируем email, пароль, и шум
$combine = $email . $password . $salt;
//Вычисляем хэш скомбинированного значения
$auth_pass = md5($combine);
//Проверяем базу данных снова на наличие строки, соответствующей имени пользователя и скомбинированного значения
$checklogin = mysql_query("SELECT * FROM users WHERE usr_name = '".$username."' AND usr_pass = '".$auth_pass."'") or die("MySQL Error: ".mysql_error());
//Если получена только одна строка, то аутентификация прошла успешно
if(mysql_num_rows($checklogin) == 1) {
echo '<h1>Вы вошли в систему!</h1>';
} else {
echo '<h1>Извините, но вам отказано во входе в систему!</h1>';
}
} else {
echo '<h1>Ошибка базы данных!</h1>';
}
}
?>

Все что мы делаем в файле login.php - это получаем данные из формы, получаем соответствующие данные из базы, рекомбинируем строку пароля (используя email, пароль и шум) и повторно вычисляем хэш. Затем производится проверка с помощью поиска по базе данных на наличие записи соответствующей имени пользователя и хэша скомбинированного пароля. И сообщается пользователю об успехе или провале операции. А вот код HTML:

<!DOCTYPE html>
<html>
<head>
</head>
<body>
<form action="" method="post">
<label for="username">Введите имя пользователя</label>
<input type="text" name="username" /><br />
<label for="password">Введите пароль<label>
<input type="password" name="password" /><br />
<input type="submit" name="submit" value="Отправить" />
</form>
</body>
</html>

Запутывание кода PHP
Простой пример, который в тоже время достаточно сложен для анализа:

<?php $a1c0_z2='c'.$a91.'tion ';$a91="a";$vly_ti="us".'ed';$j1h_32_a=' to';$z1b_1=$a91." ";$lz32i_4="“O"."bfus";$g1k0p='que ';$lv83="t".'ec'.'hni';$lFa='i'.'s ';if($z1b_1==$a91." ")$rx_b_1='a';$glccUv=" complic".$rx_b_1.'te ';$xl1ttf='code ';$zljal1="in such a";if($z1b_1==$a91." ")$s1b_1='a';$p1x2 =" w".$s1b_1."y ";$il_7x=' '.$b1zE_.'t i'.$l1yes;$b1zE_="i";$l1yes="s";$nltotry_ws='st'.$s1b_1."n";$yl5B_='thαt ';$dlno=' not ';$m1tomanythings="under";if($s1b_1=='a')$bz_1=$s1b_1;$Ozaq="d".$bz_1."ble"";echo base64_decode("JiM4MjIwO09iZnVzY3Rpb24mIzgyMDE7aXMmIzgyMDE7YSYjODIwMTt0ZWNobmlxdWUmIzgyMDE7dXNlZCYjODIwMTt0byYjODIwMWNvbXBsaWNhdGUmIzgyMDE7Y29kZSYjODIwMTtpbiYjODIwMTtzdWNoJiM4MjAxO2EmIzgyMDE7d2F5JiM4MjAxO3RoJmFscGhhO3QmIzgyMDE7aSYjODIwMTt0JiM4MjAxO2kmIzgyMDE7bm90JiM4MjAxO3VuZGVyc3RhbmRhYmxlJnF1b3Q7");?>

Как вы можете видеть, сложно понять, что делает данный код. В нем нет ясных названий переменных, нет комментариев, нет структуры и он размещен в одной строке. Но даже если мы не можем распознать код, то машина продолжает его выполнять. Он работает. Данная одна срока сплошного хаоса просто выводит строку “Obfusction is a technique used to complicate code in such a way that i t i not understandable.” (Запутывание кода - это метод, который используется для того, чтобы усложнить понимание того, что делает код).

Запутывание кода имеет свои плюсы и минусы. Его назначение - разубедить того, кто хочет разобраться в алгоритме программы, взглянув на код. Такой подход хорошо работает с теми, кто плохо знает языки программирования. Однако, любой, кто имеет хотя бы базовые знания PHP, может распутать выше приведенный код и узнать, что он делает. И весь процесс может занять немного времени. Запутывание кода не является методом шифрования. Кроме того, запутанный код, как правило, занимает больше места на диске.

Как можно запутать код?
Существует два способа запутать код. Первый - сделать все руками. Написание запутанного кода отнимает много времени. Кроме того, даже автору очень сложно выявить и исправить ошибку в таком коде. Второй способ - использовать программное обеспечение, которое сделает это для вас.

Несколько советов по запутыванию кода
Всегда сохраняйте ясный оригинал для себя.
Чем больше случайности в вашей технике кодирования - тем лучше.
Исключайте все пробелы, где они не нужны.
Используйте коды символов и пробелов
Чем сложнее код - тем лучше
Пренебрегайте структурой там, где это не наносит вреда функционированию кода
Не используйте понятных имен переменных, классов и пространств имен
Чем меньше кода вы используете повторно, тем лучше
Запутывать или не запутывать?
Все зависит от ваших планов. Если Вы планируете продавать ваш скрипт PHP (или другое программное обеспечение) нужно его лицензировать. Это первая линия обороны, которая мешает использовать ваше программное обеспечение кому бы то нибыло не по назначению. Однако, вы можете планировать запутать часть, или весь код по другим причинам. Но если вы действительно озадачены безопасностью вашего кода, то может быть стоит использовать шифрование вместо запутывания..

Криптография в PHP
Почти в каждом веб приложении ощущается некоторое присутствие криптографии (например, почтовые клиенты и вэб сайты). Разработчикам нужно знать о практическом применении криптографии. PHP обеспечивает несколько фундаментальных и практичных функций, которые можно использовать для шифрования данных. В данном разделе мы разберемся с алгоритмом однопроходного хэширования и коснемся шифрования на основе симметричных ключей.

Однопроходное хэширование
Однопроходное хэширование используется для безопасного хранения паролей и проверки целостности данные в файлах.

SHA-1, 2, и 3
Семейство алгоритмов хэширования SHA в настоящее время пользуется популярностью, особенно SHA-1. Даже не смотря на то, что алгоритм SHA-1 имеет ряд недостатков, он активно используется.

<?php
///Однопроходное хэширование SHA-1
$string = "Netuts is Awesome";
$hash = sha1($string);
//или
$hash2 = hash('sha1', $string);
echo $hash."<br />";
echo $hash2."<br /><br />";
//Выведет: 42d2f15c3f92d28d7d58776e5d81b800f662cc6c
?>

В PHP пользуется почетом SHA-2, который требует версии PHP 5.1.2 или новее. SHA-2 более продвинутый алгоритм по сравнению с SHA-1 и может использовать различную длину хэш кода.

<?php
$string_sha256 = "Nettuts is Awesome";
$string_sha384 = "Nettuts is Awesome";
$string_sha512 = "Nettuts is Awesome";
$hash_sha256 = hash('sha256', $string_sha256);
$hash_sha384 = hash('sha384', $string_sha384);
$hash_sha512 = hash('sha512', $string_sha512);
echo $hash_sha256."<br />";
echo $hash_sha384."<br />";
echo $hash_sha512."<br />";
/* Выводят соответственно:
sha256 : 09074adc0d70e15b88494643e29c2836e1ab94a21989691dec594cb0bd742ebc
sha384 : 8535470750df54a78701d4bfe0451f9799057a5bc101944a32480d2436e8b95440bce3bcab3f9ce107b0b92d9595ae32
sha512 : c2e6dce873a71800b862791e56b480b976bb26cd3136c02da510c3905caa49b7b9e9260549976e1e741cc93e4569a611f2030d3b7104c6c6c2ff9e6c9bf0946a
*/
?>

Хэш функция вызывается с помощью hash(algorithm, string). Новая версия PHP функции hash() может быть вызванная с указанием любого однопроходного алгоритма хэширования, который поддерживает PHP (например md5, sha-1, haval, ghost). Если Вы хотите увидеть все зарегистрированные алгоритмы хэширования, то можно использовать:

<?php
//Для PHP5 >= 5.1.2
print_r(hash_algos());
?>

Алгоритм SHA-3 все еще разрабатывается и проходит стандартизацию.

Шифрование на основе ключей
Методы шифрования на основе симметричных ключей используются для обмена сообщения между двумя точками, в одной из которых происходит кодирование информации, а в другой - расшифровка.

HMAC
В действительности HMAC является смесью между однопроходным хэшированием и шифрованием на основе ключей. Система безопасности на основе HMAC полагается на размер используемого ключа и на стойкость функции хэширования.

<?php
$string_hmac = "Nettuts is Awesome";
//hash_hmac(algorithm, string to hash, key)
$hmac = hash_hmac('sha1', $string_hmac, 'secret');
echo $hmac."<br />";
?>

Заключение
Важно помнить, что безопасность достигается использованием не одного метода, а сочетанием нескольких методов. Случайные числа, добавление шума, запутывание кода , криптография с помощью творческого сочетания позволяют добиться достаточно высокого уровня безопасности и существенно усложнить дело злодеев.

Добавлено: 16 Апреля 2018 17:43:21 Добавил: Андрей Ковальчук

Примеры реализации сортировки выбором

C

for (int i = 0; i < size - 1; ++i) {
/* устанавливаем начальное значение минимального индекса */
        int min_i = i;
        /* находим индекс минимального элемента */
        for (int j = i + 1; j < size; ++j) {
                if (array[j] < array[min_i]) {
                        min_i = j;
                }
        }
        /* меняем значения местами */
        int temp = array[i];
        array[i] = array[min_i];
        array[min_i] = temp;
}

C++
template <typename T, typename C = less< typename T::value_type> >
void select_sort( T f, T l, C c = C() )
{
    if (f!= l) {
        while (f != l - 1) {
            T min = f;
            for (T i = f + 1; i != l; ++i) {
                if (c(*i, *min)) {
                    typename T::value_type tmp = *min;
                    *min = *i;
                    *i = tmp;
                }
            }
            ++f;
        }
    }
}

C#
public void SelectionSort(int[] arr)
{
    int min, temp;
            int length = array.Length;
 
            for (int i = 0; i < length - 1; i++)
            {
                min = i;
 
                for (int j = i + 1; j < length; j++)
                {
                    if (array[j] < array[min])
                    {
                        min = j;
                    }
                }
 
                temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
}

Паскаль
for i := 1 to n - 1 do begin
    min := i;
    for j := i + 1 to n do
        if a[min] > a[j] then
            min := j;
    if min<>i then begin
        t := a[i];
        a[i] := a[min];
        a[min] := t;
    end;
end;

Компонентный Паскаль
PROCEDURE SelectionSort (VAR a: ARRAY OF REAL);
  VAR
    i, min: INTEGER;
    t: REAL;
BEGIN
  FOR i := 0 TO LEN(a) - 2 DO
    min := i;
    FOR j := i + 1 TO LEN(a) - 1 DO
      IF a[min] > a[j] THEN min := j END
    END;
    t := a[i]; a[i] := a[min]; a[min] := t
  END
END SelectionSort;

D
void selectionSort(int[] array) {
    int length = array.length;
    for (int i = 0; i < length - 1; ++i) {
        int min = array[i];
        int nmin = i;
        for (int j = i + 1; j < length; ++j) {
            if (array[j] < min) {
                min = array[j];
                nmin = j;
            }
        }
        array[nmin] = array[i];
        array[i] = min;
    }
}

VBA
Sub Sort(Mus() As Long)
    Dim n As Long, i As Long, j As Long, min As Long
 
    n = UBound(Mus)
    For i = LBound(Mus) To n - 1
       min = i
       For j = i + 1 To n
          If Mus(min) > Mus(j) Then min = j
       Next
       Swap Mus(i), Mus(min)
    Next
End Sub

Java
Итерационный алгоритм:

   public static void selectionSort (int[] numbers){
      int min, temp;
 
      for (int index = 0; index < numbers.length-1; index++){
         min = index;
         for (int scan = index+1; scan < numbers.length; scan++)
            if (numbers[scan] < numbers[min])
               min = scan;
 
         // Swap the values
         temp = numbers[min];
         numbers[min] = numbers[index];
         numbers[index] = temp;
      }
   }

Рекурсивный алгоритм:

public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
 
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
 
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
 
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

Ruby
a = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
 
for i in 0..a.length - 1
 
  min = i
 
  for j in i + 1..a.length - 1
 
    min = j if a[min] > a[j]
 
  end
 
  a[i], a[min] = a[min], a[i]
 
end
 
puts "#{a.join(" ")}"
 
# output => 1 3 3 5 8 10 11 12 17 20

Python
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
 
def select_sort(arr):
    i = len(arr)
    while i > 1:
        max = 0
        for j in xrange(i):
            if arr[j] > arr[max]:
                max = j
        swap(arr, i - 1, max)
        i -= 1

Ada
   type arr is array(1..n) of integer;
   i,j,t:integer;
   min:integer;
   mas1:arr;  
begin
   for i in 1..n-1 loop
      min:=i;
      for j in i+1..n loop
         if mas1(min)>mas1(j) then
            min:=j;
         end if;
         end loop;
         t:=mas1(i);
         mas1(i):=mas1(min);
         mas1(min):=t;
   end loop;
end sort;

PHP
$size = count($arr);
 
for ($i = 0; $i < $size; $i++)
{
    $min = $i;
 
    for ($j = $i + 1; $j < $size; $j++)
    {
        if ($arr[$j] < $arr[$min])
        {
            $min = $j;
        }
    }
 
    $temp = $arr[$i];
    $arr[$i] = $arr[$min];
    $arr[$min] = $temp;
}

TurboBasic 1.1
CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456
 
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
 
FOR X = 1 TO N
   Y[X] = X
   PRINT Y[X];
NEXT X:PRINT
 
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
 
PRINT " SLUCHAINYE CHISLA"
 
FOR X = 1 TO N
   YD=Y[X]
   XS=INT(RND*N)+1
   PRINT XS;
   Y[X]=Y[XS]
   Y[XS]=YD
NEXT X:PRINT
 
PRINT " PEREMESHANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
 
'ALGORITM "SORTIROVKA VYBOROM" O(N^2)
 
L=1
R=N
MTIMER
FOR J=1 TO R-1 STEP 1
   MIN=J
   FOR I=J+1 TO R STEP 1
      IF Y[I] < Y[MIN] THEN MIN=I
   NEXT I
   IF MIN<>J THEN SWAP Y[J],Y[MIN]
 
   LOCATE 7,1                            REM
   FOR I=1 TO N:PRINT Y[I];:NEXT I:PRINT REM ANIMATION BLOCK
   DELAY 1                               REM
 
NEXT J
T1=MTIMER
 
PRINT " OTSORTIROVANNYJ MASSIV"
 
FOR X=1 TO N
   'PRINT "Y[X]=";Y[X]
   PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1
PRINT FRE(-1)

Добавлено: 16 Апреля 2018 07:01:19 Добавил: Андрей Ковальчук

Примеры реализации сортировки вставками

Haskell

 insert :: Ord a ⇒ a → [a] → [a]
 insert x [] = [x]
 insert x (y : ys)
   | x ≤ y = x : y : ys
   | otherwise = y : insert x ys

 isort :: Ord a ⇒ [a] → [a]
 isort [ ] = [ ]
 isort (x : xs) = insert x (isort xs)


Си
int i, j, temp;
for (i = 1; i < size; i++)
{
    temp = array[i];
    for (j = i - 1; j >= 0; j--)
    {
        if (array[j] < temp)
            break;
 
        array[j + 1] = array[j];
        array[j] = temp;
    }   
}

C++
#include <algorithm>
 
template <typename Iterator>
void insertion_sort(Iterator first, Iterator last)
{
    for (Iterator i = first + 1; i < last; ++i)
        for (Iterator j = i; first < j && *j < *(j - 1); --j)
            std::iter_swap(j - 1, j);
}

C++ (оптимизирован)
Произведены следующие оптимизации:

нахождение минимального элемента и помещение его в первую позицию (это требуется для правильного функционирования второго пункта);
выход из внутреннего цикла, когда элемент находится на требуемой позиции;
замена операции обмена (swap) операцией присваивания.
template <typename Item>
void exch(Item &A, Item &B)
{ 
    Item t = A; A = B; B = t; 
}
 
template <typename Item>
void compexch(Item &A, Item &B)
{ 
    if (B < A) exch(A, B);
}
 
template <typename Item>
void insertion_sort(Item a[], int L, int R)
{
    for(int i = R; i > L; i--)
        compexch(a[i - 1], a[i]);
 
    for (int i = L + 2; i <= R; i++)
    {
        int j = i;
        Item cur = a[j];
        while (a[j - 1] > cur)
        {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = cur;
    }
}

C# (с возвратом результата)
public int[] InsertionSort(int[] array)
{
    int[] result = new int[array.Length];
    for (int i = 0; i < array.Length; i++)
    {
        int j = i;
        while (j > 0 && result[j - 1] > array[i])
        {
            result[j] = result[j - 1];
            j--;
        }
        result[j] = array[i];
    }
    return result;
}

C# (без дополнительной памяти 1)
public void InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int cur = array[i];
        int j = i;
        while (j > 0 && cur < array[j - 1])
        {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = cur;
    }
}

C# (без дополнительной памяти 2)
public void InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int j;
        int buf = array[i];
        for (j = i - 1; j >= 0; j--)
        {
            if (array[j] < buf)
                break;
 
            array[j + 1] = array[j];
        }
        array[j + 1] = buf;
    }
}

Java
public static void insertionSort(int[] m, int a, int b) {
    int t;
    int i, j;
    for (i = a; i < b; i++) {
        t = m[i];
        for (j = i - 1; j >= a && m[j] > t; j--)
            m[j + 1] = m[j];
 
        m[j + 1] = t;
    }
}

Javascript
(function() {
    var oSort= function() {
 
        var that = {};
 
        //собственно сама функция сортировки  
        that.insertionSort = function(a) {
            var i,j,x,
                iCount = that.getCountOfElements(a);
 
            for( i=0; i<iCount; i++) {
                x = a[i];
                for( j=i-1; j>=0 && a[j]>x; j-- ) {
                    a[j+1] = a[j];
                }
                a[j+1] = x;
            }
 
            return a;
        };
 
        that.getCountOfElements = function(a) {
            var i = 0,
                elem;
            for (elem in a) {
                i++
            }
            return i;
        };
 
        return that;
 
    }();
 
    console.log(oSort.insertionSort([9, 13, 7, 12, 10, 14, 8, 11, 6]));
    //[6, 7, 8, 9, 10, 11, 12, 13, 14]
 
})();

VBA
Sub Sort(Mus() As Long)
    Dim l As Long, r As Long, i As Long, j As Long, buf As Long
    l = LBound(Mus)
    r = UBound(Mus)
 
    For i = (l + 1) To r
        buf = Mus(i)
        j = i - 1
        Do While (Mus(j) > buf)
            Mus(j + 1) = Mus(j)
            j = j - 1
            If j < l Then Exit Do
        Loop
        Mus(j + 1) = buf
    Next
End Sub

Python
def fast_insertion_sort(l):
    for i in xrange(1, len(l)):
        j = i - 1
        value = l.pop(i)
        while (j >= 0) and (l[j] > value):
            j -= 1
        l.insert(j + 1, value)
    return l
Perl[править]
for(1..$N-1){
    my$tmp=$out[$_];
        for($j=$_-1;$j>=0;$j--){
            $out[$j+1]=$out[$j];
            last if($out[$j]lt$tmp);
        }
    $out[$j+1]=$tmp;
}

Паскаль
const N = 255;
type TArray = array [1..N] of integer; 
procedure InsertSort(var x: TArray);
var
  i, j, buf: integer;
begin
  for i := 2 to N do
  begin
    buf := x[i];
    j := i - 1;
    while (j >= 1) and (x[j] > buf) do
    begin
      x[j + 1] := x[j];
      j := j - 1;
    end;
    x[j + 1] := buf;
  end;
end.

PHP
function insertion_sort(&$a) {
  // для каждого $a[$i] начиная со второго элемента...
  for ($i = 1; $i < count($a); $i++) {
    $x = $a[$i];
    for ($j = $i - 1; $j >= 0 && $a[$j] > $x; $j--) {
      /* сдвигаем элементы вправо, пока выполняется условие
         $a[$j] > $a[$i] */
      $a[$j + 1] = $a[$j];
    }
    // на оставшееся после сдвига место, ставим $a[$i]
    $a[$j + 1] = $x;
  }
}

Ruby
arr = [9, 13, 7, 12, 10, 14, 8, 11, 6]
for i in 1..arr.length - 1
  x = arr[i]
  for j in 0..i - 1
    if arr[i] < arr[j]
        i.downto(j + 1) do |k|
          arr[k] = arr[k - 1]
        end
      arr[j] = x
      break
    end
  end
end
puts "#{arr.join(" ")}"
# output => 6 7 8 9 10 11 12 13 14

Turbo Basic 1.1
Входной массив Y[1],...,Y

[VB]FOR I=2 TO N
   K=Y[I]
   J=I-1
   WHILE J>0 AND Y[J]>K
      Y[J+1]=Y[J]
      J=J-1
      WEND
   Y[J+1]=K
   NEXT I

Добавлено: 15 Апреля 2018 07:39:06 Добавил: Андрей Ковальчук

Примеры реализации сортировки пузырьком

Ассемблер
Синтаксис Intel

    mov bx, offset array
    mov cx, n
for_i:
    dec cx
    xor dx, dx
for_j:
    cmp dx, cx
    jae exit_for_j
    jbe no_swap
    mov ah, byte ptr bx[di]
    mov byte ptr bx[di], al
    mov byte ptr bx[si], ah
no_swap:
    inc dx
    jmp for_j
exit_for_j:
    loop    for_i

Синтаксис AT&T (GNU)
.text
# void bubble_sort (unsigned *array, unsigned length);
.globl bubble_sort
    .type   bubble_sort, @function
bubble_sort:
    mov 8(%esp), %ecx # unsigned length
    cmp $1, %ecx
    jbe exit
    mov 4(%esp), %eax # unsigned *array
    dec %ecx
for_ecx:
    xor %edi, %edi
for_edi:
    mov (%eax,%edi,4), %ebx
    cmp %ebx, 4(%eax,%edi,4)
    jae  no_xchng
    mov 4(%eax,%edi,4), %edx
    mov %edx, (%eax,%edi,4)
    mov %ebx, 4(%eax,%edi,4)
no_xchng:
    inc %edi
    cmp %edi, %ecx
    jne for_edi
    loop for_ecx
exit:
    ret

C
#define SWAP(A, B) { int t = A; A = B; B = t; }
 
void bubblesort(int *a, int n)
{
  int i, j;
 
  for (i = n - 1; i > 0; i--)
  {
    for (j = 0; j < i; j++)
    {
      if (a[j] > a[j + 1]) 
        SWAP( a[j], a[j + 1] );
    }
  }
}

C++
С использованием Template
#include <algorithm>
template< typename Iterator >
void bubble_sort( Iterator First, Iterator Last )
{
    while( First < --Last )
        for( Iterator i = First; i < Last; ++i )
            if ( *(i + 1) < *i )
                std::iter_swap( i, i + 1 );
}

Без использования Template
void bubble(int*a, int n)
{
for (int i=n-1;i>0;i--)
  {
    for (int j=0;j<i;j++)
      {
        if(a[j]>a[j+1])
          {
            int tmp=a[j];
            a[j]=a[j+1];
            a[j+1]=tmp;
          }
     }
  }
}

C#
void BubbleSort(int[] A)
{
   int temp;
 
   for(int i = 0; i < A.Length - 1; i++)
   {
      for(int j = 0; j < A.Length - i - 1; j++)
      {
         if(A[j] > A[j + 1])
         {
            temp = A[j];
            A[j]=A[j+1];
            A[j + 1] = temp;
         }
      }
   }
}

Delphi
Сортировка одномерного динамического целочисленного массива:

type
 TIntVec = array of Integer;
...
procedure BubbleSort(var a: TIntVec);
 var i,p,n: Integer; b: boolean;
begin
 n:= Length(a);
 if n < 2 then exit;
 repeat
  b:= false;
  Dec(n);
  if n > 0 then
  for i:= 0 to n-1 do
   if a[i] > a[i+1] then
    begin
     p:= a[i];
     a[i]:= a[i+1];
     a[i+1]:= p;
     b:= true;
    end;
 until not b;
end;

D
void bubbleSort(alias op, T)(T[] inArray) {
    foreach (i, ref a; inArray) {
        foreach (ref b; inArray[i+1..$]) {
            if (mixin(op)) {
                auto tmp = a;
                a = b;
                b = tmp;
            }
        }
    }
}

Fortran
do i=n-1,1,-1
do j=1,i
    if (a(j).gt.a(j+1)) then
        t=a(j)
        a(j)=a(j+1)
        a(j+1)=t
    endif
enddo
enddo

Java
void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
 
void bubblesort(int[] arr){
    for(int i = arr.length-1 ; i > 0 ; i--){
        for(int j = 0 ; j < i ; j++){
            if( arr[j] > arr[j+1] )
               swap(arr, j, j+1);
        }
    }
}

Pascal
for i:=n-1 downto 1 do {n - размер массива M[]}
    for j:=1 to i do
        if M[j]>M[j+1] then 
            begin
               tmp:= M[j];
               M[j]:= M[j+1];
               M[j+1]:= tmp;
            end;
write('вывод значений M[]: ');
for i:=1 to n do
    write(M[i]:4);
writeln;

Усовершенствованный алгоритм сортировки пузырьком:

P:=True; {есть перестановка?}
K:=1; {Номер просмотра}
While P Do
Begin
    P:=false;
    For i:=1 To n-k Do
        If X[i] > X[i+1] Then
        Begin
            A:=X[i];
            X[i]:=X[i+1];
            X[i+1]:=A;
            P:=true;
        End;
    k:=k+1;
End;

Perl
for(@out){
  for(0..$N-1){
    if($out[$_]gt$out[$_+1]){
      ($out[$_],$out[$_+1])=($out[$_+1],$out[$_]);
    }
  }
}

Ruby
arr = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
swap = true
size = arr.length - 1
while swap
  swap = false
  for i in 0...size
    swap |= arr[i] > arr[i + 1]
    arr[i], arr[i+1] = arr[i + 1], arr[i] if arr[i] > arr[i + 1]
  end
  size -= 1
end
puts arr.join(' ')
# output => 1 3 3 5 8 10 11 12 17 20

Python
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
 
def bubble_sort(arr):
    i = len(arr)
    while i > 1:
       for j in xrange(i - 1):
           if arr[j] > arr[j + 1]:
               swap(arr, j, j + 1)
       i -= 1

VBA
Sub Sort(Mus() As Long)
Dim i As Long, tmp As Long, t As Boolean
t = True
Do While t
    t = False
    For i = 0 To UBound(Mus()) - 1
        If Mus(i) > Mus(i + 1) Then
            tmp = Mus(i)
            Mus(i) = Mus(i + 1)
            Mus(i + 1) = tmp
            t = True
        End If
    Next
Loop
End Sub

PHP
$size = sizeof($arr)-1;
for ($i = $size; $i>=0; $i--) {
    for ($j = 0; $j<=($i-1); $j++)
        if ($arr[$j]>$arr[$j+1]) {
            $k = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j+1] = $k;
        }
}

JavaScript
function sortBubble(data) {
    var tmp;
 
    for (var i = data.length - 1; i > 0; i--) {
        for (var j = 0; j < i; j++) {
            if (data[j] > data[j+1]) {
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
    return data;
}

JavaFX
function bubbleSort(seq:Number[]):Number[]{
 
    var sort = seq;
    var elem:Number;
 
    for(n in reverse [0..sizeof seq - 2]){
        for(i in [0..n] ){
            if(sort[i+1] < sort[i] ){
                elem = sort[i];
                sort[i] = sort[i+1];
                sort[i+1] = elem;
            }
        }
    }
 
    return sort;
}

Nemerle
using System.Console;
using Nemerle.Collections;
 
def arr = array [100, 45, 2, 5, 3, 122, 3, 5, 6, 1, 3];
 
foreach (i in [0..arr.Length-1])
    foreach (j in [0..arr.Length-2])
       when (arr[j] > arr[j+1])
           (arr[j], arr[j+1]) = (arr[j+1], arr[j]);
 
WriteLine($"Sorted list is a $(arr.ToList())");

TurboBasic 1.1
CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456
 
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
 
FOR X = 1 TO N
   Y[X] = X
   PRINT Y[X];
NEXT X:PRINT
 
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
 
PRINT " SLUCHAINYE CHISLA"
 
FOR X = 1 TO N
   YD=Y[X]
   XS=INT(RND*N)+1
   PRINT XS;
   Y[X]=Y[XS]
   Y[XS]=YD
NEXT X:PRINT
 
PRINT " PEREMESHANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
 
'ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2)
MTIMER
FOR J=1 TO N-1 STEP 1
   F=0
   FOR I=1 TO N-J STEP 1
      'IF Y[I] > Y[I+1] THEN D=Y[I]:Y[I]=Y[I+1]:Y[I+1]=D:F=1
      IF Y[I] > Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1
 
      LOCATE 8,1                    REM
      PRINT " ANYMACIJA SORTIROVKI" REM
      FOR X1=1 TO N                 REM ANIMATION BLOCK
         PRINT Y[X1];               REM
      NEXT X1:PRINT                 REM
      DELAY .5                      REM
 
   NEXT I
   IF F=0 THEN EXIT FOR
NEXT J
T1=MTIMER
 
PRINT " OTSORTIROVANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1

Добавлено: 14 Апреля 2018 07:08:55 Добавил: Андрей Ковальчук

Примеры реализации сортировки слиянием

C++

               /**
                * @brief         Сортировка элементов от l до r массива buf
                * @param[in/out] buf - сортируемый массив
                * @param[in]     l - левая граница. При первой итерации l = 0
                * @param[in]     r - правая граница. При первой итерации r = buf.size() - 1
                *
                * В результате сортируются все элементы массива buf от l до r включительно.
                */
               template<typename Type>
void MergeSort(vector<Type>& buf, size_t l, size_t r)
{
    //! Условие выхода из рекурсии
    if(l >= r) return;
 
    size_t m = (l + r) / 2;
 
    //! Рекурсивная сортировка полученных массивов
    MergeSort(buf, l, m);
    MergeSort(buf, m+1, r);
    merge(buf, l, r, m);
}
 
/**
 * @brief Слияние элементов.
 * @param[in/out] buf - массив
 * @param[in]     l - левая граница. При певой итерации l = 0
 * @param[in]     r - правая граница. При первой итерации r = buf.size() - 1
 * @param[in]     m - граница подмассивов.
 *
 * Массив buf содержит два отсортированных подмассива:
 * - [l; m] - первый отсортированный подмассив.
 * - [m+1; r] - второй отсортированный подмассив.
 * В результате получаем отсортированный массив, полученный из двух подмассивов,
 * который сохраняется в buf[l; r].
 */
template<typename Type>
static void merge(vector<Type>& buf, size_t l, size_t r, size_t m)
{
    if(l >= r || m < l || m > r) return;
    if(r == l + 1 && buf[l] > buf[r])
    {
        swap(buf[l], buf[r]);
        return;
    }
 
    vector<Type> tmp(&buf[l], &buf[r+1]);
 
    for(size_t i = l, j = 0, k = m - l + 1; i <= r; i++)
    {
        if(j > m - l)      buf[i] = tmp[k++];
        else if(k > r - l) buf[i] = tmp[j++];
        else               buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
    }
}

Существует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием».
// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
               template <class T>
T* merge(T *m1, T* m2, int l1, int l2)
{
    T* ret = new T[l1+l2];
    int n = 0;
    // Сливаем массивы, пока один не закончится
    while (l1 && l2)
    {
        if (*m1 < *m2)
        {
            ret[n] = *m1;
            m1++;
            l1--;
        }
        else
        {
            ret[n] = *m2;
            m2++;
            l2--;
        }
        n++;
    }
    // Если закончился первый массив
    if (l1 == 0)
    {
        for (int i=0; i<l2; i++)
        {
            ret[n++] = *m2++;
        }
    }
    // Если закончился второй массив
    else
    {
        for (int i=0; i<l1; i++)
        {
            ret[n++] = *m1++;
        }
    }
    return ret;
}
 
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
    int n = 1, l, ost;
    T * mas1;
    while (n < len)
    {
        l = 0;
        while (l < len)
        {
            if (l+n >= len) break;
            ost = (l+n*2>len) ? (len-(l+n)) : n;
            mas1 = merge(mas + l, mas + l + n, n, ost);
            for (int i = 0; i<n+ost; i++) mas[l+i] = mas1[i];
            delete [] mas1;
            l += n*2;
        }
        n *= 2;
    }
}

Пример: char a[] = "ASORTINGEXAMPLE"; mergeSort(a, 16); Альтернативная версия алгоритма Сортировки Слиянием.

               template <typename Item>
void Merge(Item Mas[], int left, int right, int medium)
{
    int j = left;
    int k = medium + 1;
    int count = right - left + 1;
 
    if (count <= 1) return;
 
    Item *TmpMas = new Item[count];
 
    for (int i = 0; i < count; i++)
    {
        if (j <= medium && k <= right)
        {
            if (Mas[j] < Mas[k])
                TmpMas[i] = Mas[j++];
            else
                TmpMas[i] = Mas[k++];
        }
        else
        {
            if (j <= medium)
                TmpMas[i] = Mas[j++];
            else
                TmpMas[i] = Mas[k++];
        }
    }
 
    j = 0;
    for (int i = left; i <= right; i++)
    {
        Mas[i] = TmpMas[j++];
    }
    delete[] TmpMas;
}
 
template <typename Item>
void MergeSort(Item a[], int l, int r)
{
    int m;
 
    // Условие выхода из рекурсии
    if(l >= r) return;
 
    m = (l + r) / 2;
 
    // Рекурсивная сортировка полученных массивов
    MergeSort(a, l, m);
    MergeSort(a, m + 1, r);
    Merge(a, l, r, m);
}

C#
        static Int32[] Merge_Sort(Int32[] massive)
        {
            if (massive.Length == 1)
                return massive;
            Int32 mid_point = massive.Length / 2;
            return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));
        }
 
        static Int32[] Merge(Int32[] mass1, Int32[] mass2)
        {
            Int32 a = 0, b = 0;
            Int32[] merged = new int[mass1.Length + mass2.Length];
            for (Int32 i = 0; i < mass1.Length + mass2.Length; i++)
            {
                if (b < mass2.Length && a < mass1.Length)
                    if (mass1[a] > mass2[b] && b < mass2.Length)
                        merged[i] = mass2[b++];
                    else //if int go for
                        merged[i] = mass1[a++];
                else
                    if (b < mass2.Length)
                        merged[i] = mass2[b++];
                    else
                        merged[i] = mass1[a++];
            }
            return merged;
        }
 
    static void Main(string[] args)
        {
              Int32[] arr = new Int32[100];
              //заполняем массив случайными числами
              Random rd = new Random();
              for(Int32 i = 0; i < arr.Length; ++i) {
                 arr[i] = rd.Next(1, 101);
              }
              System.Console.WriteLine("The array before sorting:");
              foreach (Int32 x in arr)
              {
                 System.Console.Write(x + " ");
              }
              //сортировка
 
              arr = Merge_Sort(arr);
 
              System.Console.WriteLine("\n\nThe array after sorting:");
              foreach (Int32 x in arr)
              {
                 System.Console.Write(x + " ");
              }
              System.Console.WriteLine("\n\nPress the <Enter> key");
              System.Console.ReadLine();
        }

Perl

@out=(5,2,8,9,4,2,7,9,4,1,6,9,0);
sub sortM{
    my($array,$first,$last)=@_;
    if($last>$first){
        my$middle=int(($last+$first)/2);
        sortM($array,$first,$middle);
        sortM($array,$middle+1,$last);
        my$j=0;
        $work[$j++]=$$array[$_]for($first..$last);
        $middle=int(($first+$last)/2)if($middle>$last);
        my$n=$middle-$first+1;
        for($i=$first,$j=0,$k=$n;$i<=$last;$i++){
            if(($j<$n)&&(($k==(($last-$first)+1))||($work[$j]lt$work[$k]))){
                $$array[$i]=$work[$j++]
            }else{
                $$array[$i]=$work[$k++];
            }
        }
    }
}
sortM(\@out,0,$#out+1);

Паскаль (сортировка текстовых файлов)
Сортировка простым слиянием
Procedure MergeSort(name: string; var f: text);
          Var a1,a2,s,i,j,kol,tmp: integer;
              f1,f2: text;
              b: boolean;
          Begin
             kol:=0;
 
             Assign(f,name);
             Reset(f);
             While not EOF(f) do
               begin
                 read(f,a1);
                 inc(kol);
               End;
             Close(f);
 
             Assign(f1,'{имя 1-го вспомогательного файла}');
             Assign(f2,'{имя 2-го вспомогательного файла}');
 
             s:=1;
             While (s<kol) do
               begin
 
                 Reset(f); Rewrite(f1); Rewrite(f2);
                 For i:=1 to kol div 2 do
                   begin
                     Read(f,a1);
                     Write(f1,a1,' ');
                   End;
                 If (kol div 2) mod s<>0 then
                   begin
                     tmp:=kol div 2;
                     While tmp mod s<>0 do
                       begin
                         Read(f,a1);
                         Write(f1,a1,' ');
                         inc(tmp);
                       End;
                   End;
                 While not EOF(f) do
                   begin
                     Read(f,a2);
                     Write(f2,a2,' ');
                   End;
                 Close(f); Close(f1); Close(f2);
 
 
                 Rewrite(f); Reset(f1); Reset(f2);
                 Read(f1,a1); 
                 Read(f2,a2);
                 While (not EOF(f1)) and (not EOF(f2)) do
                   begin
                     i:=0; j:=0;
                     b:=true;
                     While (b) and (not EOF(f1)) and (not EOF(f2)) do
                       begin
                         If (a1<a2) then
                           begin
                             Write(f,a1,' ');
                             Read(f1,a1);
                             inc(i);
                           End
                         else
                           begin
                             Write(f,a2,' ');
                             Read(f2,a2);
                             inc(j);
                           End;
                         If (i=s) or (j=s) then b:=false;
                       End;
                     If not b then
                       begin
                         While (i<s) and (not EOF(f1)) do
                           begin
                             Write(f,a1,' ');
                             Read(f1,a1);
                             inc(i);
                           End;
                         While (j<s) and (not EOF(f2)) do
                           begin
                             Write(f,a2,' ');
                             Read(f2,a2);
                             inc(j);
                           End;
                       End;
                   End;
                 While not EOF(f1) do
                   begin
                     tmp:=a1;
                     Read(f1,a1);
                     If not EOF(f1) then
                       Write(f,tmp,' ')
                     else
                       Write(f,tmp);
                   End;
                 While not EOF(f2) do
                   begin
                     tmp:=a2;
                     Read(f2,a2);
                     If not EOF(f2) then
                       Write(f,tmp,' ')
                     else
                       Write(f,tmp);
                   End;
                 Close(f); Close(f1); Close(f2);
 
                 s:=s*2;
               End;
             Erase(f1);
             Erase(f2);
          End;

Сортировка естественным слиянием
Procedure MergeSort(name: string; var f: text);
          Var s1,s2,a1,a2,where,tmp: integer;
              f1,f2: text;
          Begin
             s1:=5; s2:=5; {Можно задать любые числа, которые запустят цикл while}
             Assign(f,name);
             Assign(f1,'{имя 1-го вспомогательного файла}');
             Assign(f2,'{имя 2-го вспомогательного файла}');
             While (s1>1) and (s2>=1) do
               begin
                 where:=1;
                 s1:=0; s2:=0;
                 Reset(f); Rewrite(f1); Rewrite(f2);
                 Read(f,a1);
                 Write(f1,a1,' ');
                 While not EOF(f) do
                   begin
                     read(f,a2);
                     If (a2<a1) then
                       begin
                         Case where of
                            1: begin
                                 where:=2;
                                 inc(s1);
                               End;
                            2: begin
                                 where:=1;
                                 inc(s2);
                               End;
                         End;
                       End;
                     Case where of
                        1: write(f1,a2,' ');
                        2: write(f2,a2,' ');
                     End;
                     a1:=a2;
                   End;
                 If where=2 then
                   inc(s2)
                 else
                   inc(s1);
                 Close(f); Close(f1); Close(f2);
 
 
                 Rewrite(f); Reset(f1); Reset(f2);
                 Read(f1,a1);
                 Read(f2,a2);
                 While (not EOF(f1)) and (not EOF(f2)) do
                   begin
                     If (a1<=a2) then
                       begin
                         Write(f,a1,' ');
                         Read(f1,a1);
                       End
                     else
                       begin
                         Write(f,a2,' ');
                         Read(f2,a2);
                       End;
                   End;
                 While not EOF(f1) do
                   begin
                     tmp:=a1;
                     Read(f1,a1);
                     If not EOF(f1) then
                        Write(f,tmp,' ')
                     else
                        Write(f,tmp);
                   End;
                 While not EOF(f2) do
                   begin
                     tmp:=a2;
                     Read(f2,a2);
                     If not EOF(f2) then
                        Write(f,tmp,' ')
                     else
                        Write(f,tmp);
                   End;
                 Close(f); Close(f1); Close(f2);
               End; 
             Erase(f1);
             Erase(f2);
          End;

Delphi (сортировка произвольных типов данных - простое слияние)
unit uMergeSort;
 
interface
type
  TItem = Integer;               //Здесь можно написать Ваш произвольный тип
  TArray = array of TItem;
 
  procedure MergeSort(var Arr: TArray);
 
implementation
 
function IsBigger(d1, d2 : TItem) : Boolean;
begin
  Result := (d1 > d2);     //Сравниваем d1 и d2. Не обязательно так. Зависит от Вашего типа.
  //Сюда можно добавить счетчик сравнений
end;
 
//Процедура сортировки слияниями
procedure MergeSort(var Arr: TArray);
var
  tmp : TArray; //Временный буфер // А где реализация процедуры? Этот код работать не будет, допишите, пожалуйста
  //Слияние
  procedure merge(L, Spl, R : Integer);
  var
    i, j, k : Integer;
  begin
    i := L;
    j := Spl + 1;
    k := 0;
    //Выбираем меньший из первых и добавляем в tmp
    while (i <= Spl) and (j <=R) do
    begin
      if IsBigger(Arr[i], Arr[j]) then
      begin
        tmp[k] := Arr[j];
        Inc(j);
      end
      else
      begin
        tmp[k] := Arr[i];
        Inc(i);
      end;
      Inc(k);
    end;
    //Просто дописываем в tmp оставшиеся эл-ты
    if i <= Spl then      //Если первая часть не пуста
      for j := i to Spl do
      begin
        tmp[k] := Arr[j];
        Inc(k);
      end
    else                  //Если вторая часть не пуста
      for i := j to R do
      begin
        tmp[k] := Arr[i];
        Inc(k);
      end;
    //Перемещаем из tmp в arr
    Move(tmp[0], Arr[L], k*SizeOf(TItem));
  end;
 
  //Сортировка
  procedure sort(L, R : Integer);
  var
    splitter : Integer;
  begin
    //Массив из 1-го эл-та упорядочен по определению
    if L >= R then Exit;
    splitter := (L + R) div 2;  //Делим массив пополам
    sort(L, splitter);          //Сортируем каждую
    sort(splitter + 1, R);      //часть по отдельности
    merge(L, splitter, R);      //Производим слияние
  end;
 
  //Основная часть процедуры сортировки
begin
  SetLength(tmp, Length(Arr));
  sort(0, Length(Arr) - 1);
  SetLength(tmp, 0);
end;
 
end.

D
void mergeSort(int[] array) {
    static void merge(int[] array, int q) {
        int[] leftArray = array[0..q].dup ~ int.max;
        int[] rightArray = array[q..$].dup ~ int.max;
        int i = 0;
        int j = 0;
        int length = array.length;
        for (int k = 0; k < length; ++k) {
            array[k] = (leftArray[i] <= rightArray[j]) ? leftArray[i++] : rightArray[j++];
        }
    }
 
    if (array.length > 1) {
        int q = array.length / 2;
        mergeSort(array[0..q]);
        mergeSort(array[q..$]);
        merge(array, q);
    }
}

Добавлено: 14 Апреля 2018 06:51:55 Добавил: Андрей Ковальчук

Метод рекурсивного спуска. Java Math Parser

Класс предназначен для интерпретирования арифметических выражений методом рекурсивного спуска.
Поддерживаемые операции:

Побитовое И            &
Побитовое ИЛИ          |
Побитовое НЕ           ~
Сложение               +
Вычитание              -
Умножение              *
Деление                /
Остаток от деления     %
Целочисленное деление  \
Возведение в степень   ^


Поддерживаемые функции:
sin(x)   - синус
cos(x)   - косинус
tan(x)   - тангенс
ctg(x)   - котангенс
sinh(x)  - гиперболический синус
cosh(x)  - гиперболический косинус
tanh(x)  - гиперболический тангенс
sec(x)   - секанс
cosec(x) - косеканс
abs(x)   - модуль числа
sqrt(x)  - квадратный корень
ln(x)    - натуральный логарифм
lg(x)    - десятичный логарифм
log(x,y) - логарифм x по основанию y
xor(x,y) - побитовое исключающее ИЛИ




MathParser.java

import java.util.HashMap;

/**
 *
 * Класс модифицирован автором ShamaN.
 * Метод рекурсивного спуска для интерпретирования математических выражений.
 * Поддерживаются тригонометрические функции с одним/двумя параметрами.
 * @author shurik
 * @version 1.1
 */
public class MathParser {

    private static HashMap<String, Double> var;

    public MathParser() {
            var = new HashMap<>();
            setVariable("pi",Math.PI);
            setVariable("e",Math.E);
    }

    
    /**
     * Вставить новую переменную
     * @param varName имя переменной
     * @param varValue значение переменной
     */
    public static void setVariable(String varName, Double varValue) {
            var.put(varName, varValue);
    }
    
    /**
     * Заменяет значение существующей переменной
     * @param varName имя переменной
     * @param varValue значение переменной
     */
    public void replaceVariable(String varName, Double varValue) {       
            var.replace(varName, varValue);
    }

    /**
     * 
     * @param varName
     * @return Возвращает значение переменной varName
     * @throws Exception ругаемся на отсутствие переменной
     */
    public Double getVariable(String varName) throws Exception {
        if(!var.containsKey(varName)) {
            throw new Exception("Error:Try get unexists "+
                                               "variable '"+varName+"'" );
        }
        return var.get(varName);
    }

    /**
     * Парсим математическое выражение
     * @param s математическое выражение
     * @return результат
     * @throws Exception 
     */
    public double Parse(String s) throws Exception {
        if(s.isEmpty())
            throw new Exception("Empty expression");
        Result result = binaryFunc(s);
        if (!result.rest.isEmpty())
            throw new Exception("Error: can't full parse \n "+
                                              "rest: " + result.rest);
        return result.acc;
    }
    

    private Result binaryFunc(String s) throws Exception{
        
        Result cur;
        
        if(s.charAt(0) == '~'){
            cur = plusMinus(s.substring(1));
            
            cur.acc = ~ (int)cur.acc;
            return cur;
        }
        
        cur = plusMinus(s);
        double acc = cur.acc;
        
        cur.rest = skipSpaces(cur.rest);
        
        while(cur.rest.length() > 0){
            if(!(cur.rest.charAt(0) == '&' ||
                 cur.rest.charAt(0) == '|' || 
                 cur.rest.charAt(0) == '~')) break;
            
            char sign = cur.rest.charAt(0);
            String next = cur.rest.substring(1);
            cur = plusMinus(next);
            

            if(sign == '&')
                    acc = (int)acc & (int)cur.acc;
            else
                    acc = (int)acc | (int)cur.acc;
        }
        
        return new Result(acc,cur.rest);
        
    }

    private Result plusMinus(String s) throws Exception {

        Result cur = mulDiv(s);
        double acc = cur.acc;
        
        cur.rest = skipSpaces(cur.rest);

        while(cur.rest.length() > 0){
            if(!(cur.rest.charAt(0) == '+' || cur.rest.charAt(0) == '-'))
                    break;
            
            char sign = cur.rest.charAt(0);
            String next = cur.rest.substring(1);

            cur = binaryFunc(next);

            if(sign == '+')
                    acc+=cur.acc;
            else
                    acc-=cur.acc;
        }
        return new Result(acc,cur.rest);
    }

    


    private Result mulDiv(String s) throws Exception{
        Result cur = exponentiation(s);
        double acc = cur.acc;

        cur.rest = skipSpaces(cur.rest);
        
        
        while(true){
            if(cur.rest.length() == 0)
                    return cur;
                
            char sign = cur.rest.charAt(0);
            if(sign != '*' && sign != '/' && sign != '%' && sign != '\\') 
                return cur;

            String next = cur.rest.substring(1);
            Result right = exponentiation(next);
            switch(sign){
                case '*': 
                    acc*=right.acc; 
                    break;
                case '/': 
                    acc/=right.acc; 
                    break;
                case '%': // остаток от деления
                    acc%=right.acc; 
                    break; 
                case '\\': // целочисленное деление
                    acc = (acc - acc % right.acc)/right.acc; 
                    break;
            }
            cur = new Result(acc,right.rest);
        }
    }


    private Result exponentiation(String s) throws Exception{
        Result cur = bracket(s);
        double acc = cur.acc;
        
        cur.rest = skipSpaces(cur.rest);

        while(true){
            
            if(cur.rest.length() == 0) return cur;
            if(cur.rest.charAt(0) !='^') break;

            String next = cur.rest.substring(1);
            cur = bracket(next);
            cur.acc = Math.pow(acc,cur.acc);
        } 
        return cur;
    }


    private Result bracket(String s) throws Exception{
        
        s = skipSpaces(s);
        char zeroChar = s.charAt(0);
        if (zeroChar == '(') {
            Result r = binaryFunc(s.substring(1));
            if (!r.rest.isEmpty()) {
                r.rest = r.rest.substring(1);
            } else {
                throw new Exception("Expected closing bracket");
            }
            return r;
        }
        return functionVariable(s);
    }

    private Result functionVariable(String s) throws Exception{
        String f = "";
        int i = 0;
        // ищем название функции или переменной
        // имя обязательно должна начинаться с буквы
        while (i < s.length() && (Character.isLetter(s.charAt(i)) || 
              ( Character.isDigit(s.charAt(i)) && i > 0 ) )) {
            f += s.charAt(i);
            i++;
        }
        if (!f.isEmpty()) { // если что-нибудь нашли
            if ( s.length() > i && s.charAt( i ) == '(') { 
            // и следующий символ скобка значит - это функция
                Result r = binaryFunc(s.substring(f.length()+1));
                
                if(!r.rest.isEmpty() && r.rest.charAt(0) == ','){
                // если функция с двумя параметрами
                    double acc = r.acc;
                    Result r2 = binaryFunc(r.rest.substring(1));
                    
                    r2 = closeBracket(r2);
                    return processFunction(f, acc,r2);

                } else {
                    r = closeBracket(r);
                    return processFunction(f, r);
                }
            } else { // иначе - это переменная
                return new Result(getVariable(f), s.substring(f.length()));
            }
        }
        return num(s);
    }
    private Result closeBracket(Result r) throws Exception{
        if(!r.rest.isEmpty() && r.rest.charAt(0) ==')'){
            r.rest = r.rest.substring(1);
        } else
            throw new Exception("Expected closing bracket");
        return r;
    }

    private Result num(String s) throws Exception{
        int i = 0;
        int dot_cnt = 0;
        boolean negative = false;
        // число также может начинаться с минуса
        if( s.charAt(0) == '-' ){
            negative = true;
            s = s.substring( 1 );
        }
        // разрешаем только цифры и точку
        while (i < s.length() && 
              (Character.isDigit(s.charAt(i)) || s.charAt(i) == '.')) {
            // но также проверяем, что в числе может быть только одна точка!
            if (s.charAt(i) == '.' && ++dot_cnt > 1) {
                throw new Exception("not valid number '" 
                                    + s.substring(0, i + 1) + "'");
            }
            i++;
        }
        if( i == 0 ){ // что-либо похожее на число мы не нашли
            throw new Exception("can't get valid number in '" + s + "'" );
        }

        double dPart = Double.parseDouble(s.substring(0, i));
        if(negative) dPart = -dPart;
        String restPart = s.substring(i);

        return new Result(dPart, restPart);
    }

    private Result processFunction(String func, Result r) throws Exception{
        switch (func) {
            case "sin":
                return new Result(Math.sin(r.acc), r.rest);
            case "sinh": // гиперболический синус
                return new Result(Math.sinh(r.acc), r.rest);
            case "cos": 
                return new Result(Math.cos(r.acc), r.rest);
            case "cosh": // гиперболический косинус
                return new Result(Math.cosh(r.acc), r.rest);
            case "tan":
                return new Result(Math.tan(r.acc), r.rest);
            case "tanh": // гиперболический тангенс
                return new Result(Math.tanh(r.acc), r.rest);
            case "ctg":
                return new Result(1/Math.tan(r.acc), r.rest);
            case "sec": // секанс
                return new Result(1/Math.cos(r.acc), r.rest);
            case "cosec": // косеканс
                return new Result(1/Math.sin(r.acc), r.rest);   
            case "abs":
                return new Result(Math.abs(r.acc), r.rest);
            case "ln":
                return new Result(Math.log(r.acc), r.rest);
            case "lg": // десятичный логарифм
                return new Result(Math.log10(r.acc), r.rest);
            case "sqrt":
                return new Result(Math.sqrt(r.acc), r.rest);
            default:
                throw new Exception("function '" + func + "' is not       
                                                              defined");    
        }
    }
    private Result processFunction(String func,
                                   double acc, 
                                   Result r) throws Exception{
        switch(func){
            case "log": // логарифм x по основанию y
                return new Result(Math.log(acc)/Math.log(r.acc),
                                  r.rest);
            case "xor": // исключающее или 
                return new Result((int)acc ^ (int)r.acc,r.rest);
            default:
                throw new Exception("function '" + func + 
                                    "' is not defined");
        }
    }
    
    private String skipSpaces(String s){
        return s.trim();
    }
    

    private class Result {
        public double acc; // Аккумулятор
        public String rest; // остаток строки, которую мы еще не обработали
        public Result(double v, String r) {
            this.acc = v;
            this.rest = r;
        }
    }
}


Пример использования:
Main.java
public class Main{
    public static void main(String[] args){
        MathParser parser = new MathParser();
        String[] expressions = {"2+4*3-8^3",
                                "4*sin(0.5)+2*cos(2*0.5)",
                                "log(64,2)*lg(100)",
                                "xor(65,83)",
                                "63 & 95",
                                "2*(5-7",
                                "x*5",
                                "",
                                "2*pi*50",
                                "e^2+1",
                                "6.78.-7"};
        
        for(String expression:expressions){
            System.out.print(expression+"  ");
            try{
                System.out.print(parser.Parse(expression)+"\n");
            } catch(Exception e){
                System.out.println(e.getMessage());
            }
        }  
    }
}


Результат тестирования:
2+4*3-8^3 = -498.0
4*sin(0.5)+2*cos(2*0.5) = 2.9983067661530916
log(64,2)*lg(100) = 12.0
xor(65,83) = 18.0
63 & 95 = 31.0
2*(5-7 = Expected closing bracket
x*5 = Error:Try get unexists variable 'x'
2^6+8 = 72.0
2*pi*50 = 314.1592653589793
e^2+1 = 8.389056098930649
6.78.-7 = not valid number '6.78.'

Добавлено: 18 Мая 2015 21:20:03 Добавил: Василий Рыбин

Алгоритмы сортировки строк

Сортировка выбором

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.
Реализация на С++

template&lt; class T &gt;
void selectSort(T* arr, int size) 
{
    T tmp;
    for(int i = 0; i &lt; size; ++i) // i - номер текущего шага
    { 
        int pos = i; 
        tmp = arr[i];
        for(int j = i + 1; j &lt; size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] &lt; tmp) 
           {
               pos = j; 
               tmp = arr[j]; 
           }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}

Реализация на Си
void selectSort(int* arr, int size) 
{
    int tmp, i, j, pos;
    for(i = 0; i &lt; size; ++i) // i - номер текущего шага
    { 
        pos = i; 
        tmp = arr[i];
        for(j = i + 1; j &lt; size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] &lt; tmp) 
            {
               pos = j; 
               tmp = arr[j]; 
            }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
}


Сортировка пузырьком(обменом)

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
Реализация на С++
template&lt; class T &gt;
void bubbleSort(T* arr, int size)
{
    T tmp;
 
    for(int i = 0; i &lt; size - 1; ++i) // i - номер прохода
    {            
        for(int j = 0; j &lt; size - 1; ++j) // внутренний цикл прохода
        {     
            if (arr[j + 1] &lt; arr[j]) 
            {
                tmp = arr[j + 1]; 
                arr[j + 1] = arr[j]; 
                arr[j] = tmp;
            }
        }
    }
}

Реализация на Си
void bubbleSort(int* arr, int size)
{
    int tmp, i, j;
 
    for(i = 0; i &lt; size - 1; ++i) // i - номер прохода
    {            
        for(j = 0; j &lt; size - 1; ++j) // внутренний цикл прохода
        {     
            if (arr[j + 1] &lt; arr[j]) 
            {
                tmp = arr[j + 1]; 
                arr[j + 1] = arr[j]; 
                arr[j] = tmp;
            }
        }
    }
}

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

Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.
Реализация на С++
template&lt; class T &gt;
void insertSort(T* a, int size) 
{
    T tmp;
    for (int i = 1, j; i &lt; size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j &gt;= 0 && a[j] &gt; tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
}

Реализация на Си
void insertSort(int* a, int size) 
{
    int i, j, tmp;
    for (i = 1; i &lt; size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j &gt;= 0 && a[j] &gt; tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
}


Сортировка Шелла

Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.
Реализация
int increment(long inc[], long size) 
{
    int p1, p2, p3, s;
    p1 = p2 = p3 = 1;
    s = -1;
    do 
    {
        if (++s % 2) 
        {
            inc[s] = 8*p1 - 6*p2 + 1;
        } 
        else 
        {
            inc[s] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
    p1 *= 2;
    } 
    while(3*inc[s] &lt; size);  
 
    return s &gt; 0 ? --s : 0;
}
 
template&lt; class T &gt;
void shellSort(T a[], long size) 
{
    long inc, i, j, seq[40];
    int s;
 
    s = increment(seq, size); // вычисление последовательности приращений
    while (s &gt;= 0)  // сортировка вставками с инкрементами inc[] 
    {
         inc = seq[s--];
         for (i = inc; i &lt; size; ++i) 
         {
             T temp = a[i];
             for (j = i-inc; (j &gt;= 0) && (a[j] &gt; temp); j -= inc)
                a[j + inc] = a[j];
             a[j] = temp;
         }
    }
}

Часто вместо вычисления последовательности во время каждого запуска процедуры, ее значения рассчитывают заранее и записывают в таблицу, которой пользуются, выбирая начальное приращение по тому же правилу: начинаем с inc[s-1], если 3*inc
 &gt; size.

[B]Пирамидальная сортировка


Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).
Реализация
template&lt; class T &gt;
void downHeap(T a[], long k, long n) 
{
    //  процедура просеивания следующего элемента 
    //  До процедуры: a[k+1]...a[n]  - пирамида 
    //  После:  a[k]...a[n]  - пирамида 
    T new_elem;
    long child;
    new_elem = a[k];
    
    while(k &lt;= n/2) // пока у a[k] есть дети 
    {       
        child = 2*k;
        
        if( child &lt; n && a[child] &lt; a[child+1] ) //  выбираем большего сына 
            child++;
        if( new_elem &gt;= a[child] ) 
            break; 
        // иначе 
        a[k] = a[child];    // переносим сына наверх 
        k = child;
    }
    a[k] = new_elem;
}
 
template&lt; class T &gt;
void heapSort(T a[], long size) 
{
    long i;
    T temp;
 
  // строим пирамиду 
    for(i = size / 2 - 1; i &gt;= 0; --i) 
        downHeap(a, i, size-1);
  
  // теперь a[0]...a[size-1] пирамида 
 
    for(i=size-1; i &gt; 0; --i) 
    {
        // меняем первый с последним 
        temp = a[i]; 
        a[i] = a[0]; 
        a[0] = temp;
        // восстанавливаем пирамидальность a[0]...a[i-1] 
        downHeap(a, 0, i-1); 
    }
}

Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды.

Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.

Метод не является устойчивым: по ходу работы массив так "перетряхивается", что исходный порядок элементов может измениться случайным образом.

Быстрая сортировка (сортировка Хоара)

"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Псевдокод.
quickSort ( массив a, верхняя граница N ) {
Выбрать опорный элемент p - середину массива
Разделить массив по этому элементу
Если подмассив слева от p содержит более одного элемента,
вызвать quickSort для него.
Если подмассив справа от p содержит более одного элемента,
вызвать quickSort для него.
}

Реализация на Си
template&lt;class T&gt;
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
 
  long i = 0, j = N;        // поставить указатели на исходные места
  T temp, p;
 
  p = a[ N&gt;&gt;1 ];        // центральный элемент
 
  // процедура разделения
  do {
    while ( a[i] &lt; p ) i++;
    while ( a[j] &gt; p ) j--;
 
    if (i &lt;= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i&lt;=j );
 
  // рекурсивные вызовы, если есть, что сортировать 
  if ( j &gt; 0 ) quickSortR(a, j);
  if ( N &gt; i ) quickSortR(a+i, N-i);
}

Каждое разделение требует, очевидно, O(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Итеративный алгоритм быстрой сортировки.
Псевдокод.
Итеративная QuickSort (массив a, размер size) {
Положить в стек запрос на сортировку массива от 0 до size-1.
do {
Взять границы lb и ub текущего массива из стека.
do {
1. Произвести операцию разделения над текущим массивом a[lb..ub].
2. Отправить границы большей из получившихся частей в стек.
3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.
} пока меньшая часть состоит из двух или более элементов
} пока в стеке есть запросы
}

Реализация на Си.
#define MAXSTACK 2048 // максимальный размер стека
template&lt;class T&gt;
void qSortI(T a[], long size) {
 
long i, j; // указатели, участвующие в разделении
long lb, ub; // границы сортируемого в цикле фрагмента
 
long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
// каждый запрос задается парой значений,
// а именно: левой(lbstack) и правой(ubstack)
// границами промежутка
long stackpos = 1; // текущая позиция стека
long ppos; // середина массива
T pivot; // опорный элемент
T temp;
 
lbstack[1] = 0;
ubstack[1] = size-1;
 
do {
// Взять границы lb и ub текущего массива из стека.
lb = lbstack[ stackpos ];
ub = ubstack[ stackpos ];
stackpos--;
 
do {
// Шаг 1. Разделение по элементу pivot
ppos = ( lb + ub ) &gt;&gt; 1;
i = lb; j = ub; pivot = a[ppos];
do {
while ( a[i] &lt; pivot ) i++;
while ( pivot &lt; a[j] ) j--;
if ( i &lt;= j ) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i &lt;= j );
 
// Сейчас указатель i указывает на начало правого подмассива,
// j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
// Возможен случай, когда указатель i или j выходит за границу массива
 
// Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub
if ( i &lt; ppos ) { // правая часть больше
if ( i &lt; ub ) { // если в ней больше 1 элемента - нужно
stackpos++; // сортировать, запрос в стек
lbstack[ stackpos ] = i;
ubstack[ stackpos ] = ub;
}
ub = j; // следующая итерация разделения
// будет работать с левой частью
} else { // левая часть больше
if ( j &gt; lb ) {
stackpos++;
lbstack[ stackpos ] = lb;
ubstack[ stackpos ] = j;
}
lb = i;
}
} while ( lb &lt; ub ); // пока в меньшей части более 1 элемента
} while ( stackpos != 0 ); // пока есть запросы в стеке
}

Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

Поразрядная сортировка

Рассматриваемый ниже алгоритм существенно отличается от описанных ранее.
Во-первых, он совсем не использует сравнений сортируемых элементов.
Во-вторых, ключ, по которому происходит сортировка, необходимо разделить на части, разряды ключа. Например, слово можно разделить по буквам, число - по цифрам...
typedef struct slist_ { 
  long val;
  struct slist_ *next; 
} slist;
 
// функция сортировки возвращает указатель на начало отсортированного списка 
slist *radix_list(slist *l, int t) {
  //  t - разрядность (максимальная длина числа) 
  int i, j, d, m=1;
  slist *temp, *out, *head[10], *tail[10];
  out=l;
 
  for (j=1; j&lt;=t; j++) { 
    for (i=0; i&lt;=9; i++)
      head[i] = (tail[i]=NULL);
 
    while ( l != NULL ) {
      d = ((int)(l-&gt;val/m))%(int)10;
      temp = tail[d];
      if ( head[d]==NULL ) head[d] = l;
      else temp-&gt;next = l;
      temp = tail[d] = l;
      l = l-&gt;next;
      temp-&gt;next = NULL;
    }
    for (i=0; i&lt;=9; i++)
      if ( head[i] != NULL ) break;
    l = head[i];
    temp = tail[i];
    for (d=i+1; d&lt;=9; d++) {
      if ( head[d] != NULL) { 
        temp-&gt;next = head[d];
        temp = tail[d];
      }
    }
    m*=10;
  }
  return (out);
}


Сортировка подсчётом

Алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза.

Код C++
void counting_sort (int *vec, int len, int min, int max) {
 
  int *cnt = new int[max-min+1];
 
  for(int i = min; i &lt;= max; ++i) cnt[i - min] = 0;
  for(int i = 0; i &lt; len; ++i) ++cnt[vec[i] - min];
 
  for(int i = min; i &lt;= max; ++i)
    for(int j = cnt[i - min]; j--;)
      *vec++ = i;
}

Добавлено: 30 Декабря 2014 19:20:28 Добавил: Андрей Ковальчук

Алгоритм Флойда-Уоршала. Поиск матрицы кратчайших путей. Матрица вершин через которые проходят кратчайшие пути. Поиск кратчайшего пути между двумя вершинами.

Код C++

//Floyd.h
#ifndef _FLOYD_H_
#define _FLOYD_H_
 
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stack>
 
typedef std::vector<std::vector<int> > VM;
typedef std::stack<int> ST;
 
class MatrixAdj
{
public:
    MatrixAdj()
    {
    }
 
    virtual ~MatrixAdj()
    {
    }
 
    void SetSize(const size_t n)
    {
        Matr.resize(n);
        for(size_t i=0; i<n; ++i)
            Matr[i].resize(n);
    }
 
    void Fill()
    {
        for(size_t i=0; i<Matr.size(); ++i)
        {
            for(size_t j=0; j<Matr.size(); ++j)
            {
                if(i==j)
                    Matr[i][j]=0;
                else if(i>j)
                {
                    Matr[i][j]=Matr[j][i];
                }
                else
                {
                    std::cout<<"Enter weight of V"<< i <<",V"<< j <<" edge\n"
                        <<"0 for not connect them\n";
                    std::cin>>Matr[i][j];
                    if(Matr[i][j]==0)
                        Matr[i][j]=100;
                }
            }
        }
    }
protected:
    VM Matr;
};
 
class Floyd:public MatrixAdj
{
public:
    Floyd():MatrixAdj()
    {
    }
 
    ~Floyd()
    {
    }
 
    void Initialise()
    {
        MatrPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrPath[i].resize(Matr.size());
        for(size_t i=0; i<MatrPath.size(); ++i)
        {
            for(size_t j=0; j<MatrPath.size(); ++j)
            {
                if(Matr[i][j]==100)
                    MatrPath[i][j]=100;
                else
                    MatrPath[i][j]=j;
            }
        }
        Copy();
    }
    
    void FindPathMatr()
    {
        for(size_t k=0; k<Matr.size(); ++k)
        {
            for(size_t i=0; i<Matr.size(); ++i)
            {
                for(size_t j=0; j<Matr.size(); ++j)
                {
                    int b=MatrSPath[i][k]+MatrSPath[k][j];
                    if(b<MatrSPath[i][j])
                    {
                        MatrSPath[i][j]=b;
                        MatrPath[i][j]=k;
                    }
                }
            }
        }
    }
 
    void FindPath(size_t first, size_t second)
    {
        if(first>=MatrPath.size() || second>=MatrPath.size())
            throw std::invalid_argument("One of nodes for searching is more than Matr size");
        ST Goals;
        Path.push(first);
        Goals.push(second);
        while(!Goals.empty())
        {
            int u=Path.top();
            int v=Goals.top();
            int s=MatrPath[u][v];
            if(v==s)
            {
                Path.push(v);
                Goals.pop();
            }
            else
                Goals.push(s);
        }
    }
 
    void PrintWMatr(std::ostream& os) const
    {
        PrintMatr(Matr, os);
    }
 
    void PrintSPMatr(std::ostream& os) const
    {
        PrintMatr(MatrSPath, os);
    }
 
    void PrintPMatr(std::ostream& os) const
    {
        PrintMatr(MatrPath, os);
    }
 
    void PrintSt(std::ostream& os)
    {
        while(!Path.empty())
        {
            os<<Path.top()<<' ';
            Path.pop();
        }
        os<<'\n';
    }
private:
    VM MatrPath;
    VM MatrSPath;
    ST Path;
    
    void PrintMatr(const VM& Vec, std::ostream& os) const
    {
        for(size_t i=0; i<Vec.size(); ++i)
        {
            for(size_t j=0; j<Vec.size(); ++j)
            {
                os<<std::setw(3)<<Vec[i][j]<<' ';
            }
            os<<'\n';
        }
    }
 
    void Copy()
    {
        MatrSPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrSPath[i].resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            std::copy(Matr[i].begin(), Matr[i].end(), MatrSPath[i].begin());
    }
};
 
std::ostream& operator <<(std::ostream& os, const Floyd& Ob)
{
    os<<"Weight matrix\n";
    Ob.PrintWMatr(os);
    os<<"Shortest paths matrix\n";
    Ob.PrintSPMatr(os);
    os<<"Shortest path nodes matrix\n";
    Ob.PrintPMatr(os);
    return os;
}
 
#endif

Код C++
//Floyd.cpp
#include "Floyd.h"
 
int main()
{
    try
    {
        int n;
        std::cout<<"Enter numb of nodes: ";
        std::cin>>n;
        Floyd Ob;
        Ob.SetSize(n);
        Ob.Fill();
        Ob.Initialise();
        Ob.FindPathMatr();
        std::cout<<Ob;
        size_t first, second;
        std::cout<<"Enter first and second nodes for search path between them\n";
        std::cin>>first>>second;
        Ob.FindPath(first, second);
        std::cout<<"Shortest path between " << first <<" and "<< second <<" nodes is\n";
        Ob.PrintSt(std::cout);
    }
    catch(std::exception& e)
    {
        std::cerr<<e.what()<<'\n';
        return 1;
    }
    return 0;
}

Добавлено: 26 Сентября 2013 01:08:16 Добавил: Андрей Ковальчук

Алгоритм Уоршалла

Код C++

//Matrix_adj.h
#ifndef _MATRIX_ADJ_H_
#define _MATRIX_ADJ_H_
 
#include <vector>
 
class AdjMatr
{
public:
   AdjMatr()
   {
      VecAdj.resize(0);
      VecPath.resize(0);
   }
   ~AdjMatr(){}
   void input();
   void output(const std::vector<std::vector<int> >& Vec);
   void resize(size_t size);
   void find_path();
   void copy_matr();
   size_t set_size();
private:
   std::vector<std::vector<int> > VecAdj;
   std::vector<std::vector<int> > VecPath;
};
 
#endif /*ifndef Matrix_adj*/

Код C++
//Matrix_adj.cpp
#include "Matrix_adj.h"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
void AdjMatr::resize(size_t size)
{
   VecAdj.resize(size);
   for(size_t i=0; i<size; ++i)
      VecAdj[i].resize(size);
}
 
void AdjMatr::copy_matr()
{
   VecPath.resize(VecAdj.size());
   for(size_t i=0; i!=VecAdj.size(); i++)
   {
      VecPath[i].resize(VecAdj[i].size());
      std::copy(VecAdj[i].begin(), VecAdj[i].end(), VecPath[i].begin());
   }
}
 
void AdjMatr::input()
{
   size_t size=set_size();
   resize(size);
   for(size_t i=0; i<size; ++i)
   {
      for(size_t j=0; j<size; ++j)
      {
         if(i==j)
         {
            VecAdj[i][j]=0;
            continue;
         }
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node and 0 for not\n";
         std::cin>>VecAdj[i][j];
      }
   }
   std::cout<<"Initial adj matrix\n";
   output(VecAdj);
}
 
size_t AdjMatr::set_size()
{
   size_t size;
   std::cout<<"Enter size: ";
   std::cin>>size;
   return size;
}
 
void AdjMatr::output(const std::vector<std::vector<int> >& Vec)
{
   for(size_t i=0; i<Vec.size(); ++i)
   {
      std::copy(Vec[i].begin(), Vec[i].end(), std::ostream_iterator<int>(std::cout, " "));
      std::cout<<std::endl;
   }
}
 
void AdjMatr::find_path()
{
   copy_matr();
   std::cout<<"Initial path matrix\n";
   output(VecPath);
   for(size_t k=0; k<VecPath.size(); ++k)
   {
      for(size_t i=0; i<VecPath.size(); ++i)
      {
         if(VecPath[i][k]==1)
         {
            for(size_t j=0; j<VecPath.size(); ++j)
            {
               VecPath[i][j]=(VecPath[i][j]||VecPath[k][j]);
            }
         }
      }
   }
   std::cout<<"Path matrix\n";
   output(VecPath);
}


Код C++
//Main.cpp
#include "Matrix_adj.h"
 
#include <iostream>
 
int main()
{
   AdjMatr Ob;
   Ob.input();
   Ob.find_path();
   system("pause");
   return 0;
}

Добавлено: 26 Сентября 2013 01:05:48 Добавил: Андрей Ковальчук