public class contactPaginationController {
    //variable used in page.
    Public Integer size{get;set;}
    Public Integer noOfRecords{get; set;}
    public List<SelectOption> paginationSizeOptions{get;set;}
    public static final Integer QUERY_LIMIT = 10000;
    public static final Integer PAGE_SIZE = 5;
    
    public List <WrapperClass> wrapperRecordList{get;set;}
    Map<Id, WrapperClass> mapHoldingSelectedRecords{get;set;}
    
    //constructor calling init method.
    public contactPaginationController(){
        mapHoldingSelectedRecords = new Map<Id, WrapperClass>();
        init();
        
    }
    
    //Init method which queries the records from standard set controller.
    public void init() {
        wrapperRecordList = new List<WrapperClass>();
        for (Account cont : (List<Account>)setCon.getRecords()) {
            if(mapHoldingSelectedRecords != null && mapHoldingSelectedRecords.containsKey(cont.id)){
                wrapperRecordList.add(mapHoldingSelectedRecords.get(cont.id));
                
            }
            else{
                wrapperRecordList.add(new WrapperClass(cont, false));
            }
        }
    }
    
    /** Instantiate the StandardSetController from a query locater*/
    public ApexPages.StandardSetController setCon {
        get {
            if(setCon == null) {
                setCon = new ApexPages.StandardSetController(Database.getQueryLocator([SELECT Id,Name, Phone FROM Account LIMIT : QUERY_LIMIT ]));
                
                // sets the number of records to show in each page view
                setCon.setPageSize(PAGE_SIZE);
            }
            return setCon;
        }
        set;
    }
    
    /** indicates whether there are more records after the current page set.*/
    public Boolean hasNext {
        get {
            return setCon.getHasNext();
        }
        set;
    }
    
    /** indicates whether there are more records before the current page set.*/
    public Boolean hasPrevious {
        get {
            return setCon.getHasPrevious();
        }
        set;
    }
    
    /** returns the page number of the current page set*/
    public Integer pageNumber {
        get {
            return setCon.getPageNumber();
        }
        set;
    }
    
    /** return total number of pages for page set*/
    Public Integer getTotalPages(){
        Decimal totalSize = setCon.getResultSize();
        Decimal pageSize = setCon.getPageSize();
        Decimal pages = totalSize/pageSize;
        return (Integer)pages.round(System.RoundingMode.CEILING);
    }
    
    /** returns the first page of the page set*/
    public void first() {
        updateSearchItemsMap();
        setCon.first();
        init();
    }
    
    /** returns the last page of the page set*/
    public void last() {
        updateSearchItemsMap();
        setCon.last();
        init();
    }
    
    /** returns the previous page of the page set*/
    public void previous() {
        updateSearchItemsMap();
        setCon.previous();
        init();
    }
    
    /** returns the next page of the page set*/
    public void next() {
        updateSearchItemsMap();
        setCon.next();
        init();
    }
    
    //This is the method which manages to remove the deselected records, and keep the records which are selected in map.
    private void updateSearchItemsMap() {
        for(WrapperClass wrp : wrapperRecordList){
            if(wrp.isSelected){
                mapHoldingSelectedRecords.put(wrp.contactRecord.id, wrp);
            }
            if(wrp.isSelected == false && mapHoldingSelectedRecords.containsKey(wrp.contactRecord.id)){
                mapHoldingSelectedRecords.remove(wrp.contactRecord.id);
            }
        }
    }
    
    //wrapper class being used for checkbox showing.
    public class WrapperClass {
        public Boolean isSelected {get;set;}
        public Account contactRecord {get;set;}
        public WrapperClass(Account contactRecord, Boolean isSelected) {
            this.contactRecord = contactRecord;
            this.isSelected = isSelected;
        }
    }
}

<apex:page controller="contactPaginationController" docType="html-5.0" tabStyle="Account">
   <apex:sectionHeader title="Contact" subtitle="Contact Pagination" />
    <apex:form id="theForm">
      <apex:pageBlock title="All Contacts" rendered="{!wrapperRecordList.size!=0}" id="pbId" >
        <apex:pageBlockTable value="{!wrapperRecordList}" var="cont">
           <apex:column headerValue="Select">
             <apex:inputCheckbox value="{!cont.isSelected}"/>
           </apex:column>
           <apex:column headerValue="Name">
             <apex:outputField value="{!cont.contactRecord.name}"/>
           </apex:column>
           
           <apex:column headerValue="Phone">
            <apex:outputField value="{!cont.contactRecord.Phone}"/>
           </apex:column>
       </apex:pageBlockTable>
          
          <apex:repeat value="{!mapHoldingSelectedRecords}" var="maper">
           <apex:outputText value="{!cont}" />
        <apex:outputText value="{!mapHoldingSelectedRecords[maper]}" />
       </apex:repeat>
 
 <!-- Action Buttons visible on bottom of page for pagination -->
       <apex:outputPanel style="text-align:center;" layout="block">
          <apex:commandButton value="First" reRender="pbId" action="{!first}" disabled="{!NOT(hasPrevious)}" status="paginationStatus"/>
          <apex:commandButton value="Previous" rerender="pbId" action="{!previous}" disabled="{!NOT(hasPrevious)}" status="paginationStatus"/>&nbsp;Page {!pageNumber} of {!totalPages}&nbsp;
          <apex:commandButton value="Next" rerender="pbId" action="{!next}" disabled="{!NOT(hasNext)}" status="paginationStatus"/>
          <apex:commandButton value="Last" rerender="pbId" action="{!last}" disabled="{!NOT(hasNext)}" status="paginationStatus"/>
          <apex:actionStatus id="paginationStatus">
             <apex:facet name="start">
                 Please wait...<img src="/img/loading32.gif" style="width: 18px;"/>
             </apex:facet>
          </apex:actionStatus>
       </apex:outputPanel>
 </apex:pageBlock>
 </apex:form>
</apex:page>