Идеята на метода е разделен на групи сравнение на елементи последователност, които са отделно от определено разстояние. Първоначално разстояние D е равно или N / 2, където N - общ брой на елементите. В първия етап, като всяка група включва два елемента, разположени една от друга на разстояние N / 2; те се сравняват един с друг, и ако е необходимо, променете места. В последващи етапи се срещат като инспекция и обмен, но разстояние D се редуцира до г / 2, и броя на групите намалява съответно. Постепенно намалява разстоянието между елементите, и г = 1 чрез подаване на масива се случва в последно време.
След пример последователност от числа, илюстрира процеса на сортиране масив от Shell. За удобство и яснота, елементите на една група са разпределени в същия цвят.
Първата стойност, съответстваща на разстояние D е равно на 10/2 = 5. На всяка стъпка, тя се намалява наполовина. Елементи, които принадлежат към една и съща група се сравняват и ако стойността на всеки елемент, който стои от лявата страна на който той се съпоставя, е по-дълго (подредени във възходящ ред), докато те са разменени. По този начин, чрез интра-пермутация елементи постепенно се превърна в техните позиции, и последната стъпка на (г = 1) се редуцира до сортиране преминаването на една и съща група, включително всички елементи N масив. В този случай, необходимия брой обмен е много нисък.
програмен код за C ++:
програмен код на Паскал:
програма ShellSorting;
използва CRT;
тип Massiv = масив # 91; 1. 100 # 93; на цяло число;
Var аз. к. п. г. брои. цяло число;
А. Massiv;
процедура Shell # 40; А. Massiv; п. цяло число # 41; ;
започвам
г: = N;
г: = г DIV 2;
докато # 40; г> 0 # 41; правя
започвам
за I: = 1 до п - Д направи
започвам
J: = I;
докато # 40; # 40; J> 0 # 41; и # 40; А # 91; к # 93;> A # 91; J + г # 93; # 41; # 41; правя
започвам
брои: = A # 91; к # 93; ;
А # 91; к # 93; : А = # 91; J + г # 93; ;
А # 91; J + г # 93; : = Граф;
J: = J - 1;
приключи;
приключи;
г: = г DIV 2;
приключи;
writeln;
защото: = 1 до п пиша # 40; ''. А # 91; аз # 93; # 41; ;
приключи;
започвам
пиша # 40; "Размерът на масива> ' # 41; ; чета # 40; п # 41; ;
за I: = 1 до п направи
започнете запис # 40; аз. "Елемент> ' # 41; ; readln # 40; А # 91; аз # 93; # 41; ; приключи;
пиша # 40; 'Полученият масива " # 41; ;
черупка # 40; А. п # 41; ;
край.
Shell нещо толкова ефективна, колкото бързо сортиране, но победи в сортиране вложки. Сравнете скоростта на тези три алгоритми е възможно с помощта на следната таблица.
Свързани статии