Following instructions will work only on Ubuntu. To install on Centos, check out the following link...

how to install vim8 with python3 support

Vim Setup

Remove previous versions of Vim

sudo apt-get remove --purge vim vim-runtime vim-gnome vim-tiny vim-gui-common
sudo rm -rf /usr/local/share/vim /usr/bin/vim

Install following packages now...

sudo apt-get install -y liblua5.1-dev luajit libluajit-5.1 python-dev ruby-dev libperl-dev libncurses5-dev libatk1.0-dev libx11-dev libxpm-dev libxt-dev

Download Vim From Git

git clone https://github.com/vim/vim ~/vimtemp
cd ~/vimtemp
git pull && git fetch

Configure Vim With Python 3 Support

Run following command in vimtemp directory...

./configure \
--enable-multibyte \
--enable-perlinterp=dynamic \
--enable-rubyinterp=dynamic \
--with-ruby-command=/usr/bin/ruby \
--enable-pythoninterp=dynamic \
--with-python-config-dir=/usr/lib/python2.7/config-x86_64-linux-gnu \
--enable-python3interp \
--with-python3-config-dir=/usr/lib/python3.6/config-3.6m-x86_64-linux-gnu \
--enable-cscope \
--enable-gui=auto \
--with-features=huge \
--with-x \
--enable-fontset \
--enable-largefile \
--disable-netbeans \
--with-compiledby="yourname" \
--enable-fail-if-missing

make && sudo make install

Common Errors While Installing Vim

configure: error: could not configure perl

configure: error: could not configure X

For all the above errors, make sure you didn't skip or miss "Vim Setup" in the beginning.

Install Vim

Run following command...

make && sudo make install

Verify Vim Installation

Run vim --version, You should see something like this...

vim --version
VIM - Vi IMproved 8.2 (2019 Dec 12, compiled Aug 21 2020 06:18:45)