In this paper, we propose a fast algorithm for the variable-order (VO) Caputo fractional derivative based on a shifted binary block partition and uniform polynomial approximations of degree r. Compared with the general direct method, the proposed algorithm can reduce the memory requirement from O(n) to O(rlogn) storage and the complexity from O(n) to O(rnlogn) operations, where n is the number of time steps. As an application, we develop a fast finite difference method for solving a class of VO time-fractional diffusion equations. The computational workload is of O(rmnlogn) and the active memory requirement is of O(rmlogn), where m denotes the size of spatial grids. Theoretically, the unconditional stability and error analysis for the proposed fast finite difference method are given. Numerical results of one and two dimensional problems are presented to demonstrate the well performance of the proposed method.