1. Overview

本教程旨在讲解在虚幻引擎(UE4) C++中实现蓝图(Blueprint)可调用的任意类型数组排序的蓝图节点。纯蓝图方法实现任意类型数组排序方法，请查看上一期 UE4 蓝图实现任意类型数组排序。以下泛型数组排序节点Array_Sort基于快速排序算法（Quick Sort）原理，冒泡排序（Bubble Sort）版见知乎链接：第2期 UE4 C++实现任意类型数组蓝图排序节点。编者水平有限，如有错漏敬请谅解。

2. Introduction

快速排序（Quick Sort）的平均时间复杂度为O(nlog₂n)，冒泡排序（Bubble Sort）的平均时间复杂度为O(n²)，若以时间复杂度作为评价二种排序算法的优劣标准的话，快速排序明显优于冒泡排序。所以在已经介绍了冒泡版泛型数组排序方法，再次补充一个快速排序版泛型数组排序方法。同样地，以Sort by Function和Sort by Property作为比较数组成员大小的二种方式，分别编写了Sort Array by Function和Sort Array by Proerty二个泛型数组排序节点。
本文主要讲解UE4 C++泛型数组的快速排序蓝图节点的实现方法，以及该泛型快排节点与STL 排序方法的比较。

3. Sort Approach

3.1 基于SortBy Function，实现泛型数组排序

(1) h文件，Array_Sort函数声明：

	/** Generic sort array by function using quick sort algorithm.
	*
	*	@param	Array	Target array to sort
	*	@param	Object	The owner of  CompareBy function,(DefaultToSelf)
	*	@param	SortBy	Function name of overloads operator "<" function
							The signature of the comparison function should be equivalent to the following:
							bool cmp(const Type1 &a, const Type2 &b); return value should named "ReturnValue"(bool)
	*/
	UFUNCTION(BlueprintCallable, CustomThunk, meta = (DisplayName = "Sort Array by Function", CompactNodeTitle = "Sort", ArrayParm = "Array", AutoCreateRefTerm = "Array", DefaultToSelf = "Object", AdvancedDisplay = "Object"), Category = "Utilities|Array")
		static void Array_SortV1(const TArray<int32>& Array, UObject* Object, FName SortBy);

	// generic quick sort array by function name
	static void GenericArray_SortByFunction(UObject* OwnerObject, UFunction* ComparedBy, void* TargetArray, UArrayProperty* ArrayProp);
	// Low  --> Starting index,  High  --> Ending index
	static void QuickSortByFunction_Recursive(UObject* OwnerObject, UFunction* ComparedBy, UProperty* InnerProp, FScriptArrayHelper& ArrayHelper, int32 Low, int32 High);
	// swapping items in place and partitioning the section of an array
	static int32 QuickSortByFunction_Partition(UObject* OwnerObject, UFunction* ComparedBy, UProperty* InnerProp, FScriptArrayHelper& ArrayHelper, int32 Low, int32 High);
	// Check that the CompareBy function is appropriate
	static bool IsSuitableFunction(UFunction* ComparedBy, UArrayProperty* ArrayProp);

(2) h文件，Array_SortV1函数的自定义CustomThunk函数体

	// sort array by function name
	DECLARE_FUNCTION(execArray_SortV1)
	{
		Stack.MostRecentProperty = nullptr;
		Stack.StepCompiledIn<UArrayProperty>(NULL);
		void* ArrayAAddr = Stack.MostRecentPropertyAddress;
		UArrayProperty* ArrayProperty = Cast<UArrayProperty>(Stack.MostRecentProperty);
		if (!ArrayProperty)
		{
			Stack.bArrayContextFailed = true;
			return;
		}

		P_GET_OBJECT(UObject, OwnerObject);
		P_GET_PROPERTY(UNameProperty, SortBy);
		if (!OwnerObject)
		{
			return;
		}
		UFunction* const SortFunction = OwnerObject->FindFunction(SortBy);
		if ((!SortFunction || (SortFunction->NumParms != 3)))
		{
			return;
		}

		P_FINISH;

		P_NATIVE_BEGIN;
		GenericArray_SortByFunction(OwnerObject, SortFunction, ArrayAAddr, ArrayProperty);
		P_NATIVE_END;
	}

(3) cpp文件，GenericArray_SortByFunction()函数体

void UGenericArrayLibrary::GenericArray_SortByFunction(UObject* OwnerObject, UFunction* ComparedBy, void* TargetArray, UArrayProperty* ArrayProp)
{
	if (!ComparedBy || !OwnerObject || !TargetArray)
	{
		return;
	}
	else if (!IsSuitableFunction(ComparedBy, ArrayProp))
	{
		return;
	}
	// Optimal
	UKismetArrayLibrary::GenericArray_Shuffle(TargetArray, ArrayProp);
	// Begin sort array
	FScriptArrayHelper ArrayHelper(ArrayProp, TargetArray);

	if (ArrayHelper.Num() < 2)
	{
		return;
	}
	else
	{
		UProperty* InnerProp = ArrayProp->Inner;
		QuickSortByFunction_Recursive(OwnerObject, ComparedBy, InnerProp, ArrayHelper, 0, ArrayHelper.Num() - 1);
	}
}

其中，快排算法优化：

	// Optimal
	UKismetArrayLibrary::GenericArray_Shuffle(TargetArray, ArrayProp);

(4) cpp文件，快排递归循环

void UGenericArrayLibrary::QuickSortByFunction_Recursive(UObject* OwnerObject, UFunction* ComparedBy, UProperty* InnerProp, FScriptArrayHelper& ArrayHelper, int32 Low, int32 High)
{
	if (Low < High)
	{
		int32 Pivot = QuickSortByFunction_Partition(OwnerObject, ComparedBy, InnerProp, ArrayHelper, Low, High);
		QuickSortByFunction_Recursive(OwnerObject, ComparedBy, InnerProp, ArrayHelper, Low, Pivot - 1);
		QuickSortByFunction_Recursive(OwnerObject, ComparedBy, InnerProp, ArrayHelper, Pivot + 1, High);
	}
}

(5) cpp文件，快排拆分

int32 UGenericArrayLibrary::QuickSortByFunction_Partition(UObject* OwnerObject, UFunction* ComparedBy, UProperty* InnerProp, FScriptArrayHelper& ArrayHelper, int32 Low, int32 High)
{
	const int32 PropertySize = InnerProp->ElementSize * InnerProp->ArrayDim;
	UBoolProperty* ReturnProp = Cast<UBoolProperty>(ComparedBy->GetReturnProperty());

	// CompareBy function parameters address, 2 input parameter(array item) and 1 return parameter (bool)
	uint8* FuncParamsAddr = (uint8*)FMemory::Malloc(ComparedBy->ParmsSize); /// note:ParamsSize = PropertySize* 2 +1

	FMemory::Memzero(FuncParamsAddr, ComparedBy->ParmsSize);

	/** Based on quick sort of stl */
	InnerProp->CopyCompleteValueFromScriptVM(FuncParamsAddr, ArrayHelper.GetRawPtr(High)); //Params1: LastSmallElem = Array[High]

	int32 i = Low - 1;
	for (int32 j = Low; j < High; j++)
	{
		InnerProp->CopyCompleteValueFromScriptVM(FuncParamsAddr + PropertySize, ArrayHelper.GetRawPtr(j)); // Param2: Array[i]
		OwnerObject->ProcessEvent(ComparedBy, FuncParamsAddr);
		if (ReturnProp && ReturnProp->GetPropertyValue(FuncParamsAddr + PropertySize * 2))
		{
			i++;
			ArrayHelper.SwapValues(i, j);
		}
	}
	ArrayHelper.SwapValues(i + 1, High);
	// release memory
	FMemory::Free(FuncParamsAddr);

	return i + 1;
}

(6) cpp文件，判断用于比较数组元素大小的蓝图函数是否合乎要求

bool UGenericArrayLibrary::IsSuitableFunction(UFunction* ComparedBy, UArrayProperty* ArrayProp)
{
	// check CompareBy function's parameter number
	if ((!ComparedBy || (ComparedBy->NumParms != 3)))
	{
		UE_LOG(LogTemp, Warning, TEXT("IsSuitableFunction -> CompareBy function should only have 3 parameters !"));
		return false;
	}

	//Get return property of CompareBy function.
	UBoolProperty* ReturnProp = Cast<UBoolProperty>(ComparedBy->GetReturnProperty());
	if (!ReturnProp)
	{
		/// The return Property of max function must be bool and named "ReturnValue"
		UE_LOG(LogTemp, Warning, TEXT("IsSuitableFunction -> Return value of CompareBy function should be bool type, and named ReturnValue."));
		return false;
	}

	// Get all parameters of CompareBy function
	TArray<UProperty*> ParamterList;
	for (TFieldIterator<UProperty> It(ComparedBy); It; ++It)
	{
		UProperty* FuncParameter = *It;
		ParamterList.Emplace(FuncParameter);
	}
	// Make sure the first/second input parameters of Compare function is same to array inner
	if (!ParamterList[0]->SameType(ArrayProp->Inner) || !ParamterList[1]->SameType(ArrayProp->Inner))
	{
		/// The  property of 1st input parameter of max function must be same as array member
		UE_LOG(LogTemp, Warning, TEXT("IsSuitableFunction -> The parameters type of CompareBy should be same to array member."));
		return false;
	}
	return true;
}

3.2 基于SortBy Property，实现泛型数组排序

(1) h文件，Array_Sort函数声明：

	/** Generic sort array by property using quick sort algorithm.
	*
	*	@param	Array	Target array to sort
	*	@param	PropertyName	Name is the variable to sort by for struct or object array. Otherwise, the parameter is ignored.
	*	@param	bAscending	If true, sort by ascending order.
	*/
	UFUNCTION(BlueprintCallable, CustomThunk, meta = (DisplayName = "Sort Array by Property", CompactNodeTitle = "Sort", ArrayParm = "Array", AutoCreateRefTerm = "Array", bAscending = "true"), Category = "Utilities|Array")
		static void Array_SortV2(const TArray<int32>& Array, FName PropertyName, bool bAscending);


	// generic quick sort array by property
	static void GenericArray_SortV2(void* TargetArray, UArrayProperty* ArrayProp, FName PropertyName, bool bAscending);
	// Low  --> Starting index,  High  --> Ending index
	static void QuickSort_RecursiveByProperty(FScriptArrayHelper& ArrayHelper, UProperty* InnerProp, UProperty* SortProp, int32 Low, int32 High, bool bAscending);
	// swapping items in place and partitioning the section of an array
	static int32 QuickSort_PartitionByProperty(FScriptArrayHelper& ArrayHelper, UProperty* InnerProp, UProperty* SortProp, int32 Low, int32 High, bool bAscending);
	// generic compare two element of array by property
	static bool GenericComparePropertyValue(FScriptArrayHelper& ArrayHelper, UProperty* InnerProp, UProperty* SortProp, int32 j, int32 High, bool bAscending);

(2) h文件，Array_SortV2函数的自定义CustomThunk函数体

	// sort array by property
	DECLARE_FUNCTION(execArray_SortV2)
	{
		Stack.MostRecentProperty = nullptr;
		Stack.StepCompiledIn<UArrayProperty>(NULL);
		void* ArrayAddr = Stack.MostRecentPropertyAddress;
		UArrayProperty* ArrayProperty = Cast<UArrayProperty>(Stack.MostRecentProperty);
		if (!ArrayProperty)
		{
			Stack.bArrayContextFailed = true;
			return;
		}
		P_GET_PROPERTY(UNameProperty, PropertyName);
		P_GET_UBOOL(bAscending);
		P_FINISH;

		P_NATIVE_BEGIN;
		GenericArray_SortV2(ArrayAddr, ArrayProperty, PropertyName, bAscending);
		P_NATIVE_END;
	}

(3) cpp文件，GenericArray_SortV2()函数体

void UGenericArrayLibrary::GenericArray_SortV2(void* TargetArray, UArrayProperty* ArrayProp, FName PropertyName, bool bAscending)
{
	if (!TargetArray)
	{
		return;
	}
	// Optimal
	UKismetArrayLibrary::GenericArray_Shuffle(TargetArray, ArrayProp);
	FScriptArrayHelper ArrayHelper(ArrayProp, TargetArray);

	UProperty* SortProperty = nullptr;
	if (ArrayHelper.Num() < 2)
	{
		return;
	}
	else if (const UObjectProperty* ObjectProperty = Cast<const UObjectProperty>(ArrayProp->Inner))
	{
		SortProperty = FindField<UProperty>(ObjectProperty->PropertyClass, PropertyName);
	}
	else if (const UStructProperty* StructProperty = Cast<const UStructProperty>(ArrayProp->Inner))
	{
		SortProperty = SortAlgorithm::FindField<UProperty>(StructProperty->Struct, PropertyName);
	}
	else
	{
		SortProperty = ArrayProp->Inner;
	}

	if (SortProperty)
	{
		QuickSort_RecursiveByProperty(ArrayHelper, ArrayProp->Inner, SortProperty, 0, ArrayHelper.Num() - 1, bAscending);
	}
}

(4) cpp文件，快排递归循环

void UGenericArrayLibrary::QuickSort_RecursiveByProperty(FScriptArrayHelper& ArrayHelper, UProperty* InnerProp, UProperty* SortProp, int32 Low, int32 High, bool bAscending)
{
	if (Low < High)
	{
		int32 Pivot = QuickSort_PartitionByProperty(ArrayHelper, InnerProp, SortProp, Low, High, bAscending);

		QuickSort_RecursiveByProperty(ArrayHelper, InnerProp, SortProp, Low, Pivot - 1, bAscending);
		QuickSort_RecursiveByProperty(ArrayHelper, InnerProp, SortProp, Pivot + 1, High, bAscending);
	}
}

(5) cpp文件，快排拆分

int32 UGenericArrayLibrary::QuickSort_PartitionByProperty(FScriptArrayHelper& ArrayHelper, UProperty* InnerProp, UProperty* SortProp, int32 Low, int32 High, bool bAscending)
{
	int32 i = Low - 1;

	for (int32 j = Low; j < High; j++)
	{
		if (GenericComparePropertyValue(ArrayHelper, InnerProp, SortProp, j, High, bAscending))
		{
			i++;
			ArrayHelper.SwapValues(i, j);
		}
	}
	ArrayHelper.SwapValues(i + 1, High);
	return i + 1;
}

(6) cpp文件，比较数组中下标为j和High的成员大小

bool UGenericArrayLibrary::GenericComparePropertyValue(FScriptArrayHelper& ArrayHelper, UProperty* InnerProp, UProperty* SortProp, int32 j, int32 High, bool bAscending)
{
	bool bResult = false;
	void* LeftValueAddr = nullptr;
	void* RightValueAddr = nullptr;
	if (const UObjectProperty* ObjectProperty = Cast<const UObjectProperty>(InnerProp))
	{
		UObject* LeftObject = ObjectProperty->GetObjectPropertyValue(ArrayHelper.GetRawPtr(j));
		UObject* RightObject = ObjectProperty->GetObjectPropertyValue(ArrayHelper.GetRawPtr(High));

		LeftValueAddr = SortProp->ContainerPtrToValuePtr<void>(LeftObject);
		RightValueAddr = SortProp->ContainerPtrToValuePtr<void>(RightObject);
	}
	else
	{
		LeftValueAddr = SortProp->ContainerPtrToValuePtr<void>(ArrayHelper.GetRawPtr(j));
		RightValueAddr = SortProp->ContainerPtrToValuePtr<void>(ArrayHelper.GetRawPtr(High));
	}

	if (const UNumericProperty* NumericProp = Cast<const UNumericProperty>(SortProp))
	{
		if (NumericProp->IsFloatingPoint())
		{
			bResult = NumericProp->GetFloatingPointPropertyValue(LeftValueAddr) < NumericProp->GetFloatingPointPropertyValue(RightValueAddr);
		}
		else if (NumericProp->IsInteger())
		{
			bResult = NumericProp->GetSignedIntPropertyValue(LeftValueAddr) < NumericProp->GetSignedIntPropertyValue(RightValueAddr);
		}
	}
	else if (const UBoolProperty* BoolProp = Cast<const UBoolProperty>(SortProp))
	{
		bResult = !BoolProp->GetPropertyValue(LeftValueAddr) && BoolProp->GetPropertyValue(RightValueAddr);
	}
	else if (const UNameProperty* NameProp = Cast<const UNameProperty>(SortProp))
	{
		bResult = NameProp->GetPropertyValue(LeftValueAddr).ToString() < NameProp->GetPropertyValue(RightValueAddr).ToString();
	}
	else if (const UStrProperty* StringProp = Cast<const UStrProperty>(SortProp))
	{
		bResult = (StringProp->GetPropertyValue(LeftValueAddr) < StringProp->GetPropertyValue(RightValueAddr));
	}
	else if (const UTextProperty* TextProp = Cast<const UTextProperty>(SortProp))
	{
		bResult = (TextProp->GetPropertyValue(LeftValueAddr).ToString() < TextProp->GetPropertyValue(RightValueAddr).ToString());
	}

	return bResult == bAscending;
}

（7）为了使Array_Sort节点适用BP UStruct (蓝图结构体)数组，将内置的FindField()函数做了部分修改。

namespace SortAlgorithm
{

	template <class T> T* FindField(const UStruct* Owner, FName FieldName)
	{
		// We know that a "none" field won't exist in this Struct
		if (FieldName.IsNone())
		{
			return nullptr;
		}

		// Search by comparing FNames (INTs), not strings
		for (TFieldIterator<T>It(Owner); It; ++It)
		{
			if (It->GetFName() == FieldName)
			{
				return *It;
			}
			FName PropertyName = It->GetFName();
			//PropertyName of USTRUCT(struct is defined in Blueprint) will contains invalid string,
			//such as "Name_6_9093759148F93FCBBBF96AB8D348EC58".
			if (PropertyName.ToString().Contains(FieldName.ToString(), ESearchCase::IgnoreCase, ESearchDir::FromStart))
			{
				return *It;
			}
		}

		// If we didn't find it, return no field
		return nullptr;
	}
}

4. Usage

上述代码编译成功后，可在蓝图图表中找到以上二个SORT节点。

下面以float 数组为例，进行简单测试，以对比Sort by Propery和Sort by Function和Sort（STL）三种方式排序时间的差异;

随机获取一个浮点型数组，分别调用SORT节点，并打印排序时间

Print Duration宏蓝图代码如下

Sort by Function的SortBy函数应包含二个输入参数（变量类型与数组成员类型相同），以及一个名为ReturnValue（bool）的返回值，以上float数组的SortBy函数如下所示：

执行结果

小结：

1. 效率高低次序：STL > Sort by Propery >> Sort by Function;
2. 当数组长度length<100时，三种排序方法在时间上没有明显差异，均可适用；当数length<10000时，使用Sort by Propery和Sort by STL二种进行排序没有明显差异。
3. 由于Sort by Function排序方法使用了动态内存分配，并且调用了蓝图函数（SortBy），故效率最低；也正是因为使用蓝图函数比较大小，因此适用性更广，如二个以上排序变量的情形。

5. Conclusion

本文主要介绍了二种 UE4 泛型数组快速排序的蓝图节点的实现方法。经测试，该泛型蓝图排序节点性能虽然仍低于STL中的排序方法，但二者已处于同一层级。