Почему быстрая сортировка нестабильна

Question

Я знаю, что есть несколько подобных сообщений, но ни один из ответов не удовлетворяет, поэтому я хочу снова задать этот вопрос.

Рассмотрите приведенный ниже код. Это моя реализация быстрой сортировки в соответствии с CRLS Введение в алгоритмы

int partition(int* a, int s, int e) 
{ 
    int pivot = a[e]; 
    int q = s-1; 
    for (int i = s; i <= e; i++) 
    { 
     if (a[i] <= pivot) { 
      q++; 
      int tmp = a[q]; 
      a[q] = a[i]; 
      a[i] = tmp; 
     } 
    } 
    return q; 
} 

void quickSort(int* a, int s, int e) 
{ 
    if (e > s) { 
     int q = partition(a, s, e); 
     quickSort(a, s, q-1); 
     quickSort(a, q+1, e); 
    } 
} 

Устойчивые алгоритмы сортировки поддерживать относительный порядок записей с одинаковыми ключами (т.е. значения). Я не понимаю, почему быстрая сортировка не одна из них. Хотя в нем есть свопы между несвязанными элементами, но я до сих пор не понимаю, почему это может вызвать нестабильность. Я действительно надеюсь, что кто-то может привести примеры, чтобы объяснить это.

спасибо.

Answer 1

В стабильных алгоритмах сортировки замена или пружина происходит только с соседними элементами. Например, в mergesort элементы состоят из единиц единицы, которые затем сортируются соответственно с использованием функции слияния. Я думаю, что если u рассмотрит линейную сортировку, то она сама объяснит. Но это не так быстро.

Answer 2

попытка [1,1,1,5,5,5,5, , 1,1,4], поворот равен 4, и когда я встречаю сильнее "1", это обменивает первые 5 с этим «1»