Кодування Windows-1251 (синоним cp1251)

.0

.1

.2

.3

.4

.5

.6

.7

.8

.9

.A

.B

.C

.D

.E

.F

8.

Ђ 402

Ѓ 403

‚ 201A

ѓ 453

„ 201E

… 2026

† 2020

‡ 2021

€ 20AC

‰ 2030

Љ 409

‹ 2039

Њ 40A

Ќ 40C

Ћ 40B

Џ 40F

9.

ђ 452

‘ 2018

’ 2019

“ 201C

” 201D

• 2022

– 2013

— 2014

™ 2122

љ 459

› 203A

њ 45A

ќ 45C

ћ 45B

џ 45F

A.

A0

Ў 40E

ў 45E

Ј 408

¤ A4

Ґ 490

¦ A6

§ A7

Ё 401

© A9

Є 404

« AB

¬ AC

­ AD

® AE

Ї 407

B.

° B0

± B1

І 406

і 456

ґ 491

µ B5

¶ B6

· B7

ё 451

№ 2116

є 454

» BB

ј 458

Ѕ 405

ѕ 455

ї 457

C.

А 410

Б 411

В 412

Г 413

Д 414

Е 415

Ж 416

З 417

И 418

Й 419

К 41A

Л 41B

М 41C

Н 41D

О 41E

П 41F

D.

Р 420

С 421

Т 422

У 423

Ф 424

Х 425

Ц 426

Ч 427

Ш 428

Щ 429

Ъ 42A

Ы 42B

Ь 42C

Э 42D

Ю 42E

Я 42F

E.

а 430

б 431

в 432

г 433

д 434

е 435

ж 436

з 437

и 438

й 439

к 43A

л 43B

м 43C

н 43D

о 43E

п 43F

F.

р 440

с 441

т 442

у 443

ф 444

х 445

ц 446

ч 447

ш 448

щ 449

ъ 44A

ы 44B

ь 44C

э 44D

ю 44E

я 44F

Двобайтне кодування стандарту unicode – utf-8,utf-16

Для кодування складних алфавітів с числом символів більше 256, наприклад, китайських ієрогліфів, довелося перейти до двобайтного кодування стандарту UTF-8, UNF-16.

В UTF-16 (сучасна модифікація стандарту UTF-8) символи кодуються двобайтними словами з використанням всіх можливих діапазонів значень (від 0 до FFFF16). При цьому можна кодувати символи Unіcode у діапазонах 000016..D7FF16 і E00016..10FFFF16.

Виключений звідси діапазон D80016..DFFF16 використається саме для кодування так званих сурогатних пар - символів, які кодуються двома 16-бітними словами (наприклад, китайські ієрогліфи).

Символи Unіcode до FFFF16 включно (крім діапазону для сурогатів) записуються як є 16-бітним словом. Символи ж у діапазоні 1000016..10FFFF16 (більше 16 біт) уже кодуються парою 16-бітних слів. Для цього їхній код арифметично зрушується до нуля (з нього віднімається мінімальне число 1000016). У результаті вийде значення від нуля до FFFFF16, що займає до 20 біт. Старші 10 біт цього значення йдуть у лідируюче (перше) слово, а молодші 10 біт - у наступне (друге). При цьому в обох словах з 6 біт використаються для позначення сурогату. Біти з 11 по 15 зі значення 110112, а 10-ий біт містить 0 у лідируючого слові й 1 - у наступному. У зв'язку із цим можна легко визначити до чого ставиться кожне слово.

Алгоритм сортування Шелла:

Метод ‘бульбашки’ з послідовністю інтервалів d₁>d₂>…>d_m=1.

Швидкодія – O(N²)->O(N^3/2)->O(Nlog²N)

program ShellSrt;

{$APPTYPE CONSOLE}

uses SysUtils;

type massive=array[1..100] of integer;

var A:massive; n:integer;

procedure RndArrInput(var a1:massive; n1:integer);

var i1:integer;

begin

randomize;

for i1:=1 to n1 do

a1[i1]:=10-random(20);

end;

procedure Arroutput(a2:massive; n2:integer);

var i2:integer;

begin

for i2:=1 to n2 do

write(a2[i2],' ');

end;

Procedure change (var k,l:integer);

var tmp:integer;

begin

tmp:=k; k:=l; l:=tmp;

end;

procedure ShellSort(var A:massive; n:integer);

Var i,j,h:integer;

Begin

h:=N div 2;

While h>0 do

Begin

For i:=1 to N-h do

Begin

j:=i;

While (j>=1)and(A[j]>A[j+h]) do

Begin

change(a[j],a[j+h]);

dec(j);

End;

End;

h:=h div 2;

end;

end;

begin

writeln('enter data:');

readln(n);

RndArrInput(a,n);

ArrOutPut(a,n); readln;

ShellSort(a,n);

ArrOutPut(a,n);

readln;

end.

Швидке сортування (гнома): O(N²) <->O(NlogN). Переставляє тільки першу зустрічну «неправильну» пару і починає аналіз спочатку.

program Quick_Sort;

var A:array[1..100] of integer;

N,i : integer;

{У процедуру передаються ліва та права границі фрагменту, що сортується}

procedure QSort(L,R:integer);

var X,y,i,j:integer;

begin

X:=A[(L+R) div 2];

i:=L; j:=R;

while i<=j do

begin

while A[i]<X do i:=i+1;

while A[j]>X do j:=j-1;

if i<=j then

begin

y:=A[i]; A[i]:=A[j]; A[j]:=y;

i:=i+1; j:=j-1;

end;

end;

if L<j then QSort(L,j);

if i<R then QSort(i,R);

end;

begin

write('Кількість елементів масиву ');

read(N);

for i:=1 to n do read(A[i]);

QSort(1,n); {Впорядкувати елементи з першого по n-ий}

for i:=1 to n do write(A[i],' '); {Упорядкований масив}

end.

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

Пример:

56	19	3	95	23	17	38	44	84	73	64
19 56		3 95		17 23		38 44		73 84		64
3 19 56 95				17 23 38 44				73 64 84
3 17 19 23 38 44 56 95								64 73 84
3	17	19	23	38	44	56	64	73	84	95
O(NlogN)

procedure MergeSort( var ar1, ar2: array of Integer; min, max: Integer);

var

middle, int1, int2, int3: Integer;

begin

if min<max then begin //інакше массив складається

//з одного елемента і є впорядкованим.

middle:=min div 2+max div 2;

// рекурсивно сортуєму підсписки

MergeSort(ar1, ar2, min, middle);

MergeSort(ar1, ar2, middle+1, max);

int1:=min; //вказівник на 1-й массив

int2:=middle+1; //вказівник на 2-й массив

int3:=min; //вказівник на обєднаний масив

//обєднання сортованих масивів

while (int1<=middle) and (int2<=max) do begin

if ar1[int1] then begin

ar2[int3]:=ar1[int1];

int1:=int1+1;

end

else begin

ar2[int3]:=ar1[int2];

int2:=int2+1;

end;

inc(int3);

end;

// очистка не пустого списка

while (int1<=middle) do begin

ar2[int3]:=ar1[int1];

int1:=int1+1;

int3:=int3+1;

end;

while (int2<=middle) do begin

ar2[int3]:=ar1[int2];

int2:=int2+1;

int3:=int3+1;

end;

end;

//прирівнювання входящих массивів

for int1:=min to max do

ar1[int1]:=ar2[int1];

end;

Ще один приклад:

uses SysUtils;

const n=10;

type mas=array[1..n] of integer;

var x1,x2:mas;

i:integer;

procedure mrg(var y,x:mas; m,s,r:integer);

var mr,k,i,j:integer;

begin

mr:=m+s;

i:=m;

j:=mr;

for k:=m to m+s+r-1 do

if i>m+s-1 then

begin

x[k]:=y[j];

j:=j+1;

end

else

if j>mr+r-1 then

begin

x[k]:=y[i];

i:=i+1;

end

else if y[i]<y[j] then

begin

x[k]:=y[i];

i:=i+1;

end

else

begin

x[k]:=y[j];

j:=j+1;

end;end;

procedure Mrg_rec(var a,b:mas; l,r:integer);

var m,k:integer;

begin

if l>=r then exit;

m:=(l+r)div 2;

Mrg_rec(a,b,l,m);

Mrg_rec(a,b,m+1,r);

mrg(a,b,l,m-l+1,r-m);

for k:=1 to r do

a[k]:=b[k];

end;

begin

randomize;

for i:=1 to n do

x1[i]:=random(10)-5;

for i:=1 to n do

writeln(x1[i]);

mrg_rec(X1,X2,1,n);

writeln;

for i:=1 to n do

writeln(x1[i]);

readln; writeln('that''s all'); readln;

end.

А це - складний приклад реалізації сортування масивів:

program SortArrays;

{$APPTYPE CONSOLE}

uses SysUtils;

type Massive=array[1..25] of integer;

var A:massive; n:integer;

procedure RndArrInput (var a1:massive; n1:integer);

var i1:integer;

begin

Randomize;

for i1:=1 to n1 do

a1[i1]:=20-random(20);

end;

procedure ArrOutPut(a2:massive; n2:integer);

var i2:integer;

begin

for i2:=1 to n2 do

write(a2[i2],' ');

end;

procedure Annihilate(var an:massive; nn:integer);

var i_:integer;

begin

for i_:=1 to nn do

an[i_]:=0;

end;

procedure MergeUnion(const a:massive; N_a:integer;

const b:massive; N_b:integer; var c:massive; {var N_c:integer}start:integer);

var i_a,i_b,i_c:integer;

Begin

i_a:=1; i_b:=1; i_c:={1;}start;

while (i_a<=N_a)and(i_b<=N_b) do begin

if a[i_a]<b[i_b] then begin

c[i_c]:=a[i_a];

inc(i_a);

inc(i_c);

end else

if a[i_a]>b[i_b] then begin

c[i_c]:=b[i_b];

inc(i_b);

inc(i_c);

end else begin (* a[i_a]=b[i_b] *)

c[i_c]:=a[i_a];

inc(i_a);

{inc(i_b);} //we shouldn't write the equal value only once

inc(i_c); c[i_c]:=b[i_b]; inc(i_b); inc(i_c);

end

end;

while (i_a<=N_a) do begin

c[i_c]:=a[i_a];

inc(i_a);

inc(i_c);

end;

while (i_b<=N_b) do begin

c[i_c]:=b[i_b];

inc(i_b);

inc(i_c);

end;

End;

procedure MergeSort(var a3:massive; n3:Integer);

var hlp1,hlp2,hlp3:massive; cnt:integer; LineChanged:Boolean;

cur_1, cur_2:integer; i:integer;

cur:Integer; pnt:integer; hlp_cur:integer; WtoHlp1,WtoHlp2:Boolean;

begin

Annihilate(hlp1,n3);

Annihilate(hlp2,n3);

Annihilate(hlp3,n3);

cnt:=1; LineChanged:=true;

while LineChanged do

begin

pnt:=1; lineChanged:=false;

while pnt<=n3 do

begin

cur:=1; WtoHlp1:=false; Wtohlp2:=false; cur_1:=0; cur_2:=0;

while (cur<=cnt)and(pnt<=n3) do

begin

hlp1[cur]:=a3[pnt];

inc(pnt);

inc(cur); inc(cur_1);

WtoHlp1:=true;

end;

cur:=1;

while (cur<=cnt)and(pnt<=n3) do

begin

hlp2[cur]:=a3[pnt];

inc(pnt);

inc(cur); inc(cur_2);

WtoHlp2:=true; lineChanged:=true;

end;

if WToHlp1 and WToHlp2 then

MergeUnion(hlp1,cur_1,hlp2,cur_2,hlp3,pnt-{2*cnt}(cur_1+cur_2));

if WToHlp1 and not(WtoHlp2) then

for i:=1 to cur_1 do

begin

hlp3[pnt-(cur_1+cur_2)]:=hlp1[i];

inc(pnt);

end;

//tail-writting. cur_1 is the point, how many elements have we in hlp1.

end;

cnt:=cnt*2;

a3:=hlp3;

end;{of while LineChanged}

end;{of procedure}

begin

writeln('enter data:');

readln(n);

RndArrInput(a,n);

ArrOutput(a,n);

readln;

MergeSort(a,n);

readln;

ArrOutput(a,n);

readln;

end.

Сортування перерахунком.

K-діапазон ключів. Наприклад, байтів ключ має К=256. Масив A, що сортується, має N членів. Масив лічильників ключів С має К комірок. B-робочий масив з довжиною А.

У прикладі, що наведений нижче, K=10, N=11

A=

1

9

3

9

1

5

3

4

5

2

0

Ключі	0	1	2	3	4	5	6	7	8	9
С=	1	2	1	2	1	2	0	0	0	2

B=

0

1

1

2

3

3

4

5

5

9

9

Далі В переписується в А.

42