Сортировка повторяющихся номеров

Question

int a[] = {0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 2, 1, 1, 0, 0, 0, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0}; 

Каков наилучший подход к сортировке таких серий? Имейте в виду, что я хочу минимальную сложность.

Answer 1

Вы можете использовать функцию qsort.

Answer 2

Вы можете использовать Counting Sort сортировать по:

Answer 3

Если числа имеют небольшой верхний предел, вы можете использовать сортировку подсчета: подсчитывайте, сколько раз каждый элемент появляется в массиве, затем пройдите через массив и введите столько элементов, сколько вы подсчитали для каждого из значения.

Например, в вашем случае вы бы указали 17 нулей, 7 единиц и 4 двойки. Установите первые 17 элементов на 0, следующие 7 на 1 и оставшиеся 4 на 2, чтобы получить отсортированный массив.

Этот подход имеет линейную сложность.

Answer 4

Если числовая серия действительно ограничена значениями 0-2, то лучше всего использовать подсчитанный стиль.

void CountedSortMaxThree(int* array, size_t length) { 
    int count0 = 0; 
    int count1 = 0; 
    int count2 = 0; 

    for (int i = 0; i < length; i++) { 
    switch(array[i]) { 
     case 0: count0++; break; 
     case 1: count1++; break; 
     case 2: count2++; break; 
    } 
    } 

    int index = 0; 
    while (count0-- > 0) array[index++] = 0; 
    while (count1-- > 0) array[index++] = 1; 
    while (count2-- > 0) array[index++] = 2; 
} 

Чтобы повторно использовать, вы хотите, чтобы определить массив ведер, равный максимальный по сравнению с жестким закодированными числами

void CountedSort(int* array, int length, int max) { 
    int* buckets = malloc(sizeof(int) * max); 
    for (int i = 0; i < length; i++) { 
    bucket[array[i]]++; 
    } 

    int index = 0; 
    for (int i = 0; i < max; i++) { 
    while (buckets[i]-- > 0) { 
     array[index++] = i; 
    } 
    } 
    free(buckets); 
} 

Обратите внимание, что вы должны использовать только разметку рода, когда диапазон значений мал. В вашем примере диапазон составляет 3 (от 0 до 2 включительно), поэтому созрел для подсчета сортировки. Если диапазон был значительно выше (думаю Int32.Max), то вы бы в конечном итоге выделение гигантский массив ведро, которое будет в конечном итоге довольно неэффективный

Answer 5

void sort012Dutch(int A[],int n) 
{ 
int pos0=0,pos2=n-1,i=0; 
    while(i<n) 
{ 
    if(A[i]==0) 
    { 
     A[i]=A[pos0]; 
     A[pos0]=0; 
     pos0++; 
    } 
    if(A[i]==2&&i<pos2) 
    { 
     A[i]=A[pos2]; 
     A[pos2]=2; 
     pos2--; 
     i--;//0 could be swapped 
    } 
    i++; 
} 
} 

pos0 указывает следующий индекс в массиве, где 0 должен быть вставлен
pos2 указывает следующий индекс в массиве, где должно быть вставлено 2