<p>Given an array of integers <code>nums</code>, sort the array in ascending order and return it.</p>

<p>You must solve the problem <strong>without using any built-in</strong> functions in <code>O(nlog(n))</code> time complexity and with the smallest space complexity possible.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,3,1]
<strong>Output:</strong> [1,2,3,5]
<strong>Explanation:</strong> After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,1,1,2,0,0]
<strong>Output:</strong> [0,0,1,1,2,5]
<strong>Explanation:</strong> Note that the values of nums are not necessairly unique.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>-5 * 10<sup>4</sup> &lt;= nums[i] &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # 导入所需要的库
        import random

        # 初始化一个栈，每个栈表示需要排序的序列的开始和结束（不包括结束）
        parts = [(0, len(nums))]

        while parts:
            # 取出一个待排序的部分
            start, end = parts.pop()
            part_length = end - start

            # 如果这个部分只有一个元素或者没有元素，则其一定是有序的，不对其进行排序
            if part_length <= 1:
                continue
            # 如果这个部分只有两个元素，则在前面元素大于后边元素时交换这两个元素位置，使这部分有序。
            elif part_length == 2:
                if nums[start] > nums[start + 1]:
                    nums[start + 1], nums[start] = nums[start], nums[start + 1]
                continue
            # 如果这个部分元素过少，则对其使用其他排序算法（这里使用选择排序）
            elif part_length <= 10:
                # 从这部分的第零个元素，到倒数第二个元素为止，找到适合这个位置的元素。
                for i in range(start, end - 1):
                    min_item, ordered = i, True
                    # 从右边的部分选出最小的元素
                    for j in range(i + 1, end):
                        # 更新最小元素的索引
                        if nums[min_item] > nums[j]:
                            min_item = j
                        # 记录右边的部分是不是有序
                        if nums[j] < nums[j - 1]:
                            ordered = False
                    # 将自身和最小的元素交换
                    nums[i], nums[min_item] = nums[min_item], nums[i]
                    # 如果检查到部分有序，则停止后面的交换
                    if ordered:
                        break
                continue

            # 从该部分随机选择一个元素，将该元素与开始元素交换位置。
            # 然后，取出该部分的第零个元素作为基准元素，将第零个元素的位置记为空。
            rand_item = random.randrange(start, end)
            nums[rand_item], nums[start] = nums[start], nums[rand_item]
            pivot = nums[start]
            # 查看本次排序前的数组
            # print(nums[start:end])
            # 初始化 lt, gt 指针：该部分中，lt 左边的部分（不包括 lt ）是小于基准数的数，gt 右边的部分（不包括 gt ）是大于基
            # 准数的数，lt 和 gt 中间的部分（包括 lt 和 gt ）是等于基准的数；初始化 curr 指针，表示当前正在检查的数。
            lt, gt, curr = start + 1, end - 1, start + 1
            # 遍历该部分中除了第一个数外的每一个数
            while curr <= gt:
                # 当前数字小于基准数，则将当前数字与 lt 位置的数字交换，同时增大 lt 的大小。一般情况下，lt <= curr，因此可以
                # 确定交换后的元素小于或者等于基准值，因此，交换完成后 curr 自增。
                if nums[curr] < pivot:
                    nums[lt], nums[curr] = nums[curr], nums[lt]
                    lt, curr = lt + 1, curr + 1
                # 当前数字等于基准数，什么都不做。然后 curr 自增。
                elif nums[curr] == pivot:
                    curr = curr + 1
                # 当前数字大于基准数，则将当前数字与 gt 位置的数字交换，同时减少 gt 的大小。由于交换过来的元素还没有检查过，
                # 不能确定交换来的元素和基准值的关系，因此 curr 不自增。
                elif nums[curr] > pivot:
                    nums[gt], nums[curr] = nums[curr], nums[gt]
                    gt = gt - 1
            # 将“小于基准值的部分”的最后一个元素和该部分的第零个元素（基准）交换位置，使第零个元素位于等于基准值部分。
            nums[lt - 1], nums[start] = nums[start], nums[lt - 1]
            # 查看本次排序结果
            # print(nums[start:end])
            # 排序“小于基准值的部分”和“大于基准值的部分”
            parts.append((start, lt))
            parts.append((gt + 1, end))

        # 返回排序后的列表
        return nums

23795