Partial Discharge (PD) detection based on Ultra-High-Frequency (UHF) measurements in Gas-Insulated Switchgear (GIS) is often used for fault location based on extraction of Time Differences of Arrival (TDoA), and the core technique is to obtain the precise time difference of each UHF signal. Usually, TDoA extraction algorithms can be categorized as cross-correlation function method (CCF), minimum energy method (ME), and threshold value method (TV) are not qualified to analyze the time difference with high accuracy and efficiency, especially the complicated UHF PD signals in the field. In this paper, multiple tests were carried out based on the real GIS UHF signals. Three typical algorithms (CCF, ME, and TV) were used to extract and calculate the TDoA of UHF signals. Afterwards, depending on the disassembly of equipment, the accuracy and effective range of the algorithms are analyzed by means of error and variance. To minimize the error and the variance, an average method with the combination (CA) and portfolio of traditional algorithms is proposed and verified in different situations. The results demonstrate that the improved algorithm could increase the accuracy of time difference extraction, less than 4.0%.