我必须用 Python 编写一个 shell 排序程序，但除此之外，我还必须有一个程序，可以使用一些特殊的间隙序列创建文本文件，这就是我的 shell 排序获得其间隙编号的地方。
在维基百科 (http://en.wikipedia.org/wiki/Shellsort) 普拉特序列的方程是这样的：“连续的数字形式为 2^p*3^q”，它产生 1,2， 3,4,6,8,9,12,...
我不明白的是如何实现这个，基本上P和Q是什么？
最坏情况时间复杂度为 O(Nlog^2N)
我当前的序列生成器文件代码：
def Hibbard(big):
H = open("Hibbard.txt","w")
i = 1
math = (2**i)-1
while math <= big:
H.write(str(math))
H.write("\n")
i+=1
math = (2**i)-1
def Pratt(big):
pass
def SedA(big):
SA = open("SedgewickA.txt","w")
SA.write("1\n")
i = 1
math = (4**i)+3*2**(i-1)+1
while math <= big:
SA.write(str(math))
SA.write("\n")
i+=1
math = (4**i)+3*2**(i-1)+1
def SedB(big):
pass
def main():
big = int(input("Enter the largest gap: "))
Hibbard(big)
# Pratt(big)
SedA(big)
# SedB(big)
main()
在普拉特序列的定义中，p和q分别是2和3的指数。您需要找到 2 和 3 的幂的所有乘积，且不大于您排序的最大间隙大小。为此，请制作一个表格，顶部为 2 的幂，侧面为 3 的幂，并用它们的乘积填充每个单元格，直到它们超过最大间隙大小。例如，最大间隙大小为 500，表格将如下所示：
1 2 4 8 16 32 64 128 256
3 6 12 24 48 96 192 384
9 18 36 72 144 288
27 54 108 216 432
81 162 324
243 486
现在用Python模拟这个表的生成。
def generate_pratt(max_size):
"""Generate a sorted list of products of powers of 2 and 3 below max_size"""
# for https://stackoverflow.com/q/25964453/2738262
products = []
pow3 = 1 # start with q = 0
while pow3 <= max_size:
# At this point, pow3 = 3**q, so set p = 0
pow2 = pow3
while pow2 <= max_size:
# At this point, pow2 = 2**p * 3**q
products.append(pow2)
pow2 = pow2 * 2 # this is like adding 1 to p
# now that p overflowed the maximum size, add 1 to q and start over
pow3 = pow3 * 3
# the Pratt sequence is the result of this process up to the given size
return sorted(products)
print(generate_pratt(12))
罗伯特·威尔逊的观察可用于筛选数字
但它会太慢 O(n^2)
Mathematica 代码看起来不错并生成
在小于 O(n) 的时间内排序的 Pratt 序列
unit queue;
interface
type pfifo_node = ^fifo_node;
fifo_node = record
data:longint;
next:pfifo_node;
end;
fifo_pointers = record
head,tail:pfifo_node;
end;
procedure queue_init(var fifo:fifo_pointers);
function queue_isEmpty(fifo:fifo_pointers):boolean;
procedure enqueue(var fifo:fifo_pointers;d:longint);
procedure dequeue(var fifo:fifo_pointers);
procedure print_queue(fifo:fifo_pointers);
implementation
procedure queue_init(var fifo:fifo_pointers);
begin
fifo.head := NIL;
fifo.tail := NIL;
end;
function queue_isEmpty(fifo:fifo_pointers):boolean;
begin
queue_isEmpty := ((fifo.head = NIL) and (fifo.tail = NIL));
end;
procedure enqueue(var fifo:fifo_pointers;d:longint);
var new_node:pfifo_node;
begin
new(new_node);
new_node^.data := d;
new_node^.next := NIL;
if(fifo.head = NIL) then
begin
fifo.head := new_node;
fifo.tail := new_node;
end
else
begin
fifo.tail^.next := new_node;
fifo.tail := new_node;
end;
end;
procedure dequeue(var fifo:fifo_pointers);
var tmp:pfifo_node;
begin
if(fifo.head <> NIL)then
begin
tmp := fifo.head^.next;
dispose(fifo.head);
fifo.head := tmp;
if(tmp = NIL)then
fifo.tail := NIL;
end;
end;
procedure print_queue(fifo:fifo_pointers);
var tmp:pfifo_node;
f:text;
begin
assign(f,'');
rewrite(f);
tmp := fifo.head;
while(tmp <> NIL) do
begin
write(f,tmp^.data,' ');
tmp := tmp^.next;
end;
writeln(f);
close(f);
end;
begin
end.
program PrattGenerator;
uses crt,queue;
var fifo:fifo_pointers;
n,pow3:longint;
err:integer;
aux:pfifo_node;
begin
val(ParamStr(1),n,err);
queue_init(fifo);
enqueue(fifo,1);
pow3 := 3;
aux := fifo.head;
while(fifo.tail^.data <= n) do
begin
if(2*aux^.data < pow3) then
begin
enqueue(fifo,2*aux^.data);
aux := aux^.next;
end
else
begin
enqueue(fifo,pow3);
pow3 := pow3 * 3;
end;
end;
print_queue(fifo);
while not queue_isEmpty(fifo) do
dequeue(fifo);
end.
为了进行比较，我将介绍达米安的解决方案
unit list;
interface
type PNode = ^TNode;
TNode = record
key:longint;
next:PNode;
end;
procedure ListInit(var L:PNode);
function ListIsEmpty(L:PNode):boolean;
procedure ListPrint(L:PNode);
function ListSearch(L:PNode;k:longint):PNode;
procedure ListInsert(var L:PNode;k:longint);
procedure ListDelete(var L:PNode;k:longint);
implementation
procedure ListInit(var L:PNode);
begin
L := NIL;
end;
function ListIsEmpty(L:PNode):boolean;
begin
ListIsEmpty := (L = NIL);
end;
procedure ListPrint(L:PNode);
var x:PNode;
f:text;
begin
assign(f,'');
rewrite(f);
x := L;
while(x <> NIL)do
begin
write(f,x^.key,' ');
x := x^.next;
end;
writeln(f);
close(f);
end;
function ListSearch(L:PNode;k:longint):PNode;
var x:PNode;
begin
x := L;
while((x <> NIL) and (x^.key <> k)) do
x := x^.next;
ListSearch := x;
end;
procedure ListInsert(var L:PNode;k:longint);
var x,y,z:PNode;
begin
new(x);
x^.key := k;
if(L = NIL)then
begin
L := x;
x^.next := NIL;
end
else
begin
y := L;
z := NIL;
while((y <> NIL) and (x^.key > y^.key)) do
begin
z := y;
y := y^.next;
end;
x^.next := y;
if z <> NIL then
z^.next := x
else
L := x;
end;
end;
procedure ListDelete(var L:PNode;k:longint);
var x,y:PNode;
begin
x := ListSearch(L,k);
if ((L <> NIL) and (x <> NIL)) then
if (L = x) then
begin
L := x^.next;
dispose(x);
end
else
begin
y := L;
while (y^.next <> x) do
y := y^.next;
y^.next := x^.next;
dispose(x);
end;
end;
begin
end.
program Prattgenerator;
uses list;
var L:PNode;
pow2,pow3,max_size:longint;
err:integer;
begin
val(ParamStr(1),max_size,err);
ListInit(L);
pow3 := 1;
while (pow3 <= max_size) do
begin
pow2 := pow3;
while (pow2 <= max_size) do
begin
ListInsert(L,pow2);
pow2 := pow2 * 2;
end;
pow3 := pow3 *3;
end;
ListPrint(L);
while not ListIsEmpty(L) do
ListDelete(L,L^.key);
end.
我们可以使用堆栈来反转元素的顺序
不需要为堆栈创建新节点
我们可以尝试从现有的队列节点构建堆栈