Может ли быстрая сортировка быть стабильной?

Если во время быстрой сортировки учитываются также значения, равные центральной точке, можно ли это назвать устойчивой сортировкой? Вот моя реализация быстрой сортировки:

def isOrdered(aList):
ordered = True
for i in range(len(aList)-1):
    if aList[i] > aList[i+1]:
        ordered = False
        break
return ordered

def partition(List,pivotIndex):
    pivot=List[pivotIndex]
    less=[]
    equal=[]
    greater=[]
    if pivotIndex<len(List):
        for i in List:
            if i<pivot:
                less.append(i)
            elif i==pivot:
                equal.append(i)
            else:
                greater.append(i)
    returnlist= [less,equal,greater]
    return returnlist

def quicksort(List,pivotIndex=0):
    sortedList = []
    if pivotIndex>=len(List):
        pivotIndex%=len(List)
    for i in partition(List,pivotIndex):
        for j in i:
            sortedList.append(j)
    pivotIndex+=1
    if isOrdered(sortedList):
        return sortedList
    else:
        return quicksort(sortedList,pivotIndex)

Можно ли улучшить стабильность и одновременно поддерживать скорость вычислений для быстрой сортировки?

0 ответов

Другие вопросы по тегам