Сортировать массив чисел (первый номер будет выбран динамически, а оставшийся массив должен быть отсортирован по возрастанию)

Question

int[] array = {1,1,0,1,2,2,0,0};
int  firstNumber = 1;// dynamic can be 0 or 1 or 2
int numberOfOccurances = 0;

//Basic sort functionality
for(int i = 0 ; i< array.length; ++i)
{
    if(array[i] == firstNumber)
    {
        numberOfOccurances++;
    }
    for(int j = i+1; j<array.length; ++j)
    {   
        if(array[j] < array[i])
        {   
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}
int[] requiredArray= new int[array.length]; 
for(int i = array.length-1 ; i >= 0; i--)
{
    if(array[i] != firstNumber)
    requiredArray[i] = array[i];

}
for(int i =0;i<array.length;i++)
{
    if(i<numberOfOccurances)
    requiredArray[i]= firstNumber;
}

//Print Output
for (int i = 0; i<requiredArray.length; i++)
System.out.print(requiredArray[i] + "  ");

Выход: 1 1 1 1 0 0 2 2

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

Answer 1

В зависимости от вашего размера чисел, вы можете подсчитать каждое вхождение числа и распечатать число, сколько раз вы его посчитали. Это алгоритм O(n).

arrayToBeSorted = {collection of numbers}
firstNumber = arrayToBeSorted[0]
countArray = new int[max(arrayToBeSorted)]; //everything defaults to 0 in most languages
for i:= 0 -> N
    countArray[arrayToBeSorted[i]]++;

for i:= 0 ->countArray[firstNumber]
    print(firstNumber)

for i: = 0 ->countArray.length
    if (i == firstNumber)
        continue;
    for j:= 0 -> countArray[i]
        print(i)

Answer 2

Это простое решение. Измените номер, если: - другой номер firstNumber - другой номер младший и не первый номер

    int[] array = {1,1,0,1,2,2,0,0,3,2,1,0,0,1,2,3,2,3};

    int firstNumber = 1, temp;

    for(int i=0;i<array.length-1;i++) {
        for(int j=i+1;j<array.length;j++) {

            if( (array[j] < array[i] && array[i]!=firstNumber) || array[j]==firstNumber) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }

Answer 3

Существует лучший способ. В частности, ваш алгоритм сортировки

1. Не оптимально по сложности (O(n^2)), см. известные алгоритмы сортировки для O(n * log n) альтернативы ( https://en.wikipedia.org/wiki/Sorting_algorithm см. MergeSort и QuickSort для популярных). На практике стандартная библиотека вашего языка в любом случае будет содержать хорошую реализацию.
2. Работа над n элементы еще. Если у вас много "первого", вам на самом деле нужно только m = n - number_of_first элементы и что можно сделать в O(m * log m),

Обычно второй момент не важен. Если это так, вы могли бы иметь дело с несколькими различными элементами, и тогда было бы также неплохо использовать что-то вроде еще лучшего удобства https://en.wikipedia.org/wiki/Counting_sort

Игнорируя случай с несколькими различными элементами, я бы порекомендовал вам один раз просмотреть массив и скопировать все элементы, которые не являются "firstNumber", в другой массив. Затем вы сортируете этот другой массив, используя стандартный алгоритм сортировки - предпочтительно встроенный.

Наконец, ваш вывод array.length - otherArray.length раз firstNumber с последующим содержанием отсортированного otherArray