Сначала поставьте на места термины.
Обычно под VPS и представляют виртуальный хостинг (полностью выделенная виртуальная машина на общих с соседями ресурсах: kvm, openvz ...)
VDS - физический сервер, когда вам резервируют полностью компьютер (в софтверном плане почти ничем не отличается от VPS)
Shared hosting - хостинг с соседями, без полноценной виртуальной машины, с возможность использовать только тот софт, который установит хостер.
Если вы переходите на последний, то там, действительно, ни сфинкс, ни solr работать не будут.
В таком случае, нужно, действительно, искать тот поисковый движок, где в зависимостях только пхп (то есть, то, что есть на вашем шаред хостинге). И, возможно, смотреть, все ли пхп расширения доступны и у вашего хостера. Как-то так
