【python】数组的定位排序？

题目：给定一个数组A以及下标i，将数组元素进行调整，使得所有比A[i]小的元素排在前面，接着是所有等于A[i]的元素，最后排列的是比A[i]大的元素。要求算法不能分配新内存，时间复杂度是O(n)。

分析：我们先用一个变量pivot来指定数组元素A[i]。算法分两部走：第一步将数组分成两部分，第一部分元素都小于pivot，第二部分都大于或等于pivot；第二步，对第二部分进行调整将其分成两部分，第一部分所有元素都等于pivot，第二部分所有元素都大于pivot。具体思路：用两个指针begin和end分别指向数组的开始和末尾，如果A[begin] >= pivot,那么将A[begin]与A[end]互换，然后指针end向前移动一个元素；如果A[beign] <pivot，指针begin向后移动一个元素；当两个指针相遇时，算法结束。

code：

def rearrangeByPivot(arr, begin, end, pivot, checkEqual):

    if end <= begin:

        return

    while begin < end:

        # 如果checkEqual为真，那么交换条件是大于等于，为假则元素交换条件为大于

        if  (checkEqual is True and arr[begin] >= pivot) or (checkEqual is False and arr[begin] > pivot):

            temp = arr[begin]

            arr[begin] = arr[end]

            arr[end]  = temp

            end -= 1

        else:

            begin += 1

    return arr

def rearrangeArray(arr, i):

    if (len(arr) <= 1):

        return arr

    pivot = arr[i]

    # 先执行算法第一步，将数组元素分为两部分，第一部分小于pivot，第二部分大于等于pivot

    arr = rearrangeByPivot(arr, 0, len(arr) - 1, pivot, True)

    # 找到第一部分和第二部分的分界点

    for j in range(len(arr)):

        if arr[j] >= pivot:

            break

    # 执行算法的第二步

    arr = rearrangeByPivot(arr, j, len(arr) - 1, pivot, False)

    return arr

S = [6, 5, 5, 7, 9, 4, 3, 3, 4, 6, 8, 4, 7, 9, 2, 1]

i = 5

S = rearrangeArray(S, i)

print(S)

程序运行结果：
[1, 2, 3, 3, 4, 4, 4, 6, 8, 7, 7, 9, 5, 5, 6, 9]