Учитывая массив положительных и отрицательных целых чисел, перестройте его так, чтобы у вас были положительные целые числа на одном конце и отрицательные целые числа на другом

Ответ 1

Чтобы достичь этого результата в постоянном пространстве (но в квадратичном времени), вы можете использовать подход с двумя очередями, поставив одну очередь на каждом конце массива (подобно алгоритму Голландского национального флага). Чтение элементов слева направо: добавление элемента в левую очередь означает его оставить в покое, добавление элемента в нужную очередь означает перенос всех элементов, не находящихся в очереди слева на один, и размещение добавленного элемента в конце. Затем, чтобы объединить очереди, просто измените порядок элементов во второй очереди.

Выполняет операцию O (n) (перемещение элементов слева) до O (n) раз, что дает время работы O (n²).

Используя метод, подобный сортировке слиянием, вы можете добиться более низкой сложности O (n log n): срезайте массив в две половины, рекурсивно сортируйте их в форме [N P] [N P], затем поменяйте первый P на второй N в O (n) времени (он становится немного сложным, когда у них нет точно такого же размера, но он все еще линейный).

Я не имею абсолютно никакого представления о том, как это сделать до времени O (n).

РЕДАКТИРОВАТЬ: на самом деле, ваш список ссылок правильно. Если данные предоставляются как дважды связанный список, вы можете реализовать стратегию с двумя очередями в O (n) времени, O (1):

sort(list):
  negative = empty
  positive = empty
  while (list != empty)
     first = pop(list)
     if (first > 0) 
         append(positive,first)
     else
         append(negative,first)
  return concatenate(negative,positive)

С реализацией связанного списка, которая удерживает указатели на первый и последний элементы, тогда pop, append и concatenate являются операциями O (1), поэтому общая сложность O (n). Что касается пространства, ни одна из операций не выделяет какую-либо память (append просто использует память, выпущенную pop), поэтому O (1) в целом.

Ответ 2

Здесь представлена ​​версия пространственного решения O (n) времени O (1), предположительная maxValue * (maxValue + 1) меньше Integer.MAX_VALUE, где maxValue является результатом значения maxmum минус minmum значение в массив. Он использует исходный массив в качестве временного массива для хранения результата.

public static void specialSort(int[] A){
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for(int i=0; i<A.length; i++){
        if(A[i] > max)
            max = A[i];
        if(A[i] < min)
            min = A[i];
    }
    //Change all values to Positive
    for(int i=0; i<A.length; i++)
        A[i]-= min;

    int newMax = max-min+1;

    //Save original negative values into new positions
    int currNegativeIndex = 0;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax < (-min))
            A[currNegativeIndex++] += (A[i]%newMax)*newMax;
    //Save original positive values into new positions
    int currPositiveIndex = currNegativeIndex;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax > (-min))
            A[currPositiveIndex++] += (A[i]%newMax)*newMax;
    //Recover to original value 
    for(int i=0; i<A.length; i++){
        A[i] = A[i]/newMax + min; 
    }
}

Ответ 3

Я не уверен, что правильно понял вопрос, поскольку ответ кажется слишком простым:

• Пройдите по массиву и подсчитайте отрицательные числа - O (n)
• Создайте новый массив размера O (n)
• Пройдите через исходный массив и поместите числа в новый массив. Используйте известное количество отрицательных чисел для компенсации положительных - O (n)

Вот быстрый способ сделать это в Python. Он немного отличается от приведенного выше, сначала создавая массив для негативов, а затем добавляя положительные значения. Так что это не так эффективно, но все же O (n).

>>> a = [1,7,-5,9,-12,15]
>>> print [x for x in a if x < 0] + [y for y in a if y >= 0]
[-5, -12, 1, 7, 9, 15]

Изменить: Хорошо, теперь с O (1) космической сложностью становится намного сложнее. Меня интересует, как добиться этого в O (n) временной сложности. Если это помогает, вот способ удержания сложности O (1), но требует сложности времени O (n ^ 2):

• Начните с самого левого отрицательного числа. Пройдите через массив, пока не найдете следующее отрицательное число.
• В новом цикле обмениваем отрицательное число на положительное число слева от него. Сделайте это, пока не достигнете других отрицательных чисел. Это гарантирует, что порядок номеров остается неизменным.
• Rince и повторите, пока вы не достигнете конца массива при поиске нового отрицательного числа.

Ответ 4

Это можно сделать в O (n) и пространстве O (1).

Нам нужно сканировать 3 раза через массив и осторожно менять некоторые значения.

Предположение: максимальное значение в массиве с размером N должно быть меньше (N+1) * Integer.MAX_VALUE.

Нам нужно это предположение, так как мы хорошо меняем некоторые положительные значения в массиве.

• В первом сканировании найдите # отрицательных и положительных значений и максимальный
• Во втором сканировании мы создаем отрицательный раздел массива следующим образом:

Мы начинаем с начала массива, и мы " swap" первое найденное положительное число (например, в индексе i) с первым найденным отрицательным числом (например, j). Поскольку отрицательные числа рассматриваются относительно их местоположения, своп будет в порядке.

Проблема - это положительные числа, потому что между i и j могут быть некоторые другие положительные числа. Чтобы справиться с этой проблемой, мы должны как-то закодировать индекс положительного числа в этом значении перед заменой. Итак, мы можем понять, где это было в первом пункте. Мы можем сделать это с помощью a[i]=(i+1)*(max)+a[i].

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

Вот код:

import java.util.Arrays;

public class LinearShifting {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = {-1,7,3,-5,4,-3,1,2};
        sort(a);
        System.out.println(Arrays.toString(a));  //output: [-1, -5, -3, 7, 3, 4, 1, 2]
    }
    public static void sort(int[] a){
        int pos = 0;
        int neg = 0;
        int i,j;
        int max = Integer.MIN_VALUE;
        for(i=0; i<a.length; i++){
            if(a[i]<0) neg++;
            else pos++;
            if(a[i]>max) max = a[i];
        }
        max++;
        if(neg==0 || pos == 0) return;//already sorted
        i=0;
        j=1;
        while(true){
            while(i<=neg && a[i]<0) i++;
            while(j<a.length && a[j]>=0) j++;
            if(i>neg || j>=a.length) break;
            a[i]+= max*(i+1);
            swap(a,i,j);
        }

        i = a.length-1;
        while(i>=neg){
            int div = a[i]/max;
            if(div == 0) i--;
            else{
                a[i]%=max;
                swap(a,i,neg+div-2);// minus 2 since a[i]+= max*(i+1);
            }
        }

    }
    private static void swap(int[] a, int i , int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}

Ответ 5

Изменить (5/29/2015): я упустил из виду требование поддержания порядка появления, поэтому нижеприведенный ответ не удовлетворяет всем требованиям вопроса. Тем не менее, я оставляю первоначальный ответ для общего интереса.

Это специальная версия очень важной подпрограммы quicksort, известной как "раздел". Определение: массив A, содержащий N числовых записей, разделен на значение K в индексе p, если A [i] K для 0 <= я < p и A [j] >= K для p <= j < N, если все записи меньше K (что означает p = N) или не меньше K (что означает p = 0). Для рассматриваемой задачи мы будем разбивать массив вокруг K = 0.

Вы можете разбить несортированный массив на любое значение K в O (n) раз, обращаясь к каждой записи в массиве только один раз, используя O (1) дополнительную память. Неформально вы проходите через массив с обоих концов, перемещая значения, которые находятся на неправильной стороне. Выполняйте своп, когда на каждой стороне массива обнаруживается одно неуместное значение, а затем продолжается шаг за шагом. Теперь код С++:

// Assume array A[] has size N
int K = 0; // For particular example partitioning positive and negative numbers
int i = 0, j = N-1; // position markers, start at first and last entries
while(1) { // Break condition inside loop
    while(i < N && A[i] < K) i++; // Increase i until A[i] >= K
    while(j >= 0 && A[j] >= K) j--; // Decrease j until A[j] < K
    if(i < j) 
        swap(A[i],A[j]);
    else
        break;
}
// A[] is now partitioned, A[0]...A[j] < K, unless i==0 (meaning all entries >= K).

Обратите внимание, что если все элементы равны K (в этом случае нуль), я никогда не увеличивается и j = 0 в конце. Утверждение проблемы предполагает, что этого никогда не произойдет. Раздел очень быстрый и эффективный, и эта эффективность является причиной того, что quicksort является самой популярной процедурой сортировки для больших массивов. Функция swap может быть std:: swap на С++ или вы можете легко написать свой собственный:

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

Или просто для удовольствия, цифры могут быть заменены на место без временной памяти, хотя помните о переполнении:

// This code swaps a and b with no extra space.  Watch out for overflow!
a -= b;
b += a;
a = b - a;

Существует множество вариантов разделения для особых случаев, таких как трехсторонний раздел для [элементов < K] [элементы == K] [элементы > K]. Алгоритм быстрой сортировки рекурсивно решает раздел, а значение раздела K обычно является первой записью в текущем подвале или вычисляется из нескольких записей (например, медиана из трех). См. Учебники: Алгоритмы Sedgewick и Wayne (4-е изд., Стр. 288) или "Искусство компьютерного программирования". 3 от Кнута (2-е изд., Стр. 113).

Ответ 6

Вы можете использовать 2 очереди и объединить их. Таким образом, вы повторяете только один раз в первом массиве и после каждой дополнительной очереди.

negatives = []
positives = []

for elem in array:
  if elem >= 0:
    positives.push(elem)
  else
    negatives.push(elem)

result = array(negatives, positives)

Ответ 7

Здесь решение с двумя итерациями:
Пусть говорят, что длина равна n.
И я буду использовать C как код, игнорировать синтаксические ошибки.

solution[n];
for (i= 0,j=0 ; i < n ; i++ ) {
     if (array[i] < 0) solution[j++] = array[i];
}
for (i = n-1,j=n-1 ; ; i > 0 ; i--) {
     if (array[i] >= 0) solution[j--] = array[i];
}

Идея состоит в том, чтобы разобраться с ней один раз и написать все негативы, с которыми мы сталкиваемся.
Затем перейдите к нему второй раз с конца и напишите положительные результаты с конца в начало.

Ответ 8

Это решение имеет сложность времени O (n) и сложность пространства O (1)

Идея:

• отслеживать индекс последнего увиденного отрицательного элемента (lastNegIndex).

• цикл через массив, чтобы найти отрицательные элементы, которым предшествует положительный элемент.

• Если такой элемент найден, поменяйте его между последнимNegIndex и текущим индексом на единицу. Затем обновите lastNegIndex (это будет следующий индекс).

Вот код:

public void rightRotate(int[] a, int n, int currentIndex, int lastNegIndex){
    int temp = a[currentIndex];
    for(int i = currentIndex; i > lastNegIndex+ 1; i--){
        a[i] = a[i-1];
    }
    a[lastNegIndex+1] = temp;
}

public void ReArrange(int[] a, int n){
    int lastNegIndex= -1;
    int index;

    if(a[0] < 0)
        lastNegIndex = 0;

    for(index = 1; index < n; index++){
         if (a[index] < 0 && a[index - 1] >= 0) {
             rightRotate(a, n, index, lastNegIndex);
             lastNegIndex = lastNegIndex + 1;
         }
    }
}

Ответ 9

Если структура в начале не должна быть массивом, она еще проще.

Если у вас есть исходные номера в связанном списке, это легко.

Вы можете перенастроить связанный список, каждый раз указывать минус рядом со следующим отрицательным и положительным рядом со следующим положительным.

Снова C как код, игнорировать синтаксис. (может потребоваться нулевая проверка здесь и там, но это идея)

Cell firstPositive;
Cell* lastPoisitive;
lastPoisitive = &firstPositive;
Cell firstNegative;
Cell* lastNegative;
lastNegative = &firstNegative;
Cell* iterator;
for(Iterator = list.first ; Iterator != null ; Iterator = Iterator->next) {
   if (Iterator->value > 0 ) lastPoisitive->next = Iterator;
   else lastPoisitive->next = Iterator;
}
list.first = firstNegative->next;
list.last.next = firstPositive->next;

Ответ 10

Если целью является O (1) пространство (помимо самих элементов, которые считаются свободно изменяемыми) и O (NlgN), разделите проблему на задачу создания массивов, которые, как известно, имеют вид pnPN, где p и P представляют собой ноль или более положительных чисел, а n и N - 0 или более отрицательных чисел, в массивы вида pPnN. Любой двухэлементный массив будет автоматически иметь такую ​​форму. Для двух массивов этой формы найдите первое отрицательное число, следующее положительное число и последнее положительное число, и "открутите" средние два раздела массива (легко сделать в постоянном пространстве и время, пропорциональное размеру массива быть "открученным" ). Результатом будет массив вида pPnN. Два последовательных таких массива образуют больший массив формы pnPN.

Чтобы делать вещи в постоянном пространстве, начните с объединения всех элементов и помещения их в форму PN. Затем выполняйте все квартеты элементов, затем все октеты и т.д. До общего размера массива.

Ответ 11

Просто идея.. Рассмотрим более простую задачу:

Для массива, где первая часть (Np) содержит только положительные числа, а последняя часть (Nn): только отрицательные. Как обменивать эти части при сохранении относительного порядка?

Простейшим решением является использование инверсии:

inverse(array, Np + Nn); // whole array
inverse(array, Nn);      // first part
inverse(array+Nn, Np);   // second part

Он имеет сложность времени O (n) и сложность пространства O (1).

Ответ 12

Я очень сомневаюсь, что O (n) время и O (1) возможно с массивом . Некоторые из них предлагают связанный список, но для этого вам нужен специальный связанный список, в котором у вас есть прямой доступ к узлам, т.е. языковые встроенные списки не будут работать.

Здесь моя идея использует пользовательский двусвязный список, который удовлетворяет ограниченным сложностям, используя в качестве примера следующие варианты: [1, 7, -5, 9, -12, 15]:

Прокрутите список, если увидите отрицательный результат, отрежьте его и добавьте в конец отрицаний спереди. Каждая операция O (1), поэтому общее время O (n). Операции с объединенным списком выполняются на месте так, что O (1) пространство.

Подробнее:

last_negative_node = null;

at -5: 

cut off -5 by setting 7.next = 9, 

then add -5 to front by -5.next = 1, 

then update last_negative_node = 5 // O(1), the linked list is now [-5, 1, 7, 9, -12, 15]


at -12: 

cut off -12 by setting 9.next = 15, 

then add -12 to front by -12.next = last_negative_node.next, 

then update last_negative_node.next = -12,

then update last_negative_node = -12 //O(1), the linked list is now [-5, -12, 1, 7, 9, 15]

no more negatives so done.

Ответ 13

O (n) решение Java

    private static void rearrange(int[] arr) {
    int pos=0,end_pos=-1;
    for (int i=0;i<=arr.length-1;i++){  
        end_pos=i;
        if (arr[i] <=0){
            int temp_ptr=end_pos-1;
            while(end_pos>pos){
                int temp = arr[end_pos];
                arr[end_pos]=arr[temp_ptr];
                arr[temp_ptr]=temp;
                end_pos--;
                temp_ptr--;
            }
            pos++;
        }

    }

Ответ 14

Вот реализация JavaScript qiwangcs:

function specialSort(A){
    let min = Number.MAX_SAFE_INTEGER, max = -Number.MAX_SAFE_INTEGER;
    for(let i=0; i<A.length; i++){
        if(A[i] > max)
            max = A[i];
        if(A[i] < min)
            min = A[i];
    }
    //Change all values to Positive
    for(let i=0; i<A.length; i++)
        A[i]-= min;
    const newMax = max-min+1;        
    //Save original negative values into new positions
    let currNegativeIndex = 0;
    for(let i=0; i<A.length; i++)
        if(A[i]%newMax < (-min))
            A[currNegativeIndex++] += (A[i]%newMax)*newMax;
    //Save original positive values into new positions
    let currPositiveIndex = currNegativeIndex;
    for(let i=0; i<A.length; i++)
        if(A[i]%newMax > (-min))
            A[currPositiveIndex++] += (A[i]%newMax)*newMax;
    //Recover to original value 
    for(let i=0; i<A.length; i++){
        A[i] = Math.floor(A[i]/newMax) + min; 
    }
}
// Demo
const A = [-3,-7,2,8,-5,-2,4];
specialSort(A);
console.log(A);

Ответ 15

Я думаю, что это сработало бы: вот простой способ, что постоянное пространство (но квадратичное время). Скажем, что массив - длина N. Пройдите вдоль массива от я = 0 до я = N-2 проверяющего элемента я и я + 1. Если элемент я положителен, а элемент я + 1 отрицателен, замените их. Затем повторите этот процесс.

Каждый проход по массиву заставит негативы дрейфовать влево (и положительные отклонения вправо), вроде как сортировка пузырьков, пока (после достаточного количества проходов) все они находятся в правильном месте.

Кроме того, я думаю, что это сработало бы: это также постоянное пространство (но квадратичное время). Скажем, P - количество положительных результатов. Сканирование слева направо, когда вы обнаружите положительное x, остановите сканирование и "удалите его", сдвинув все элементы после того, как они останутся на одном. Затем поместите x в конец массива. Повторите процедуру сканирования P раз, чтобы переместить все положительные.

Ответ 16

Сначала подсчитайте число k отрицательных элементов. Затем вы знаете, что первые k числа массива (первая часть массива) должны быть отрицательными. Следующие элементы N - k должны быть положительными после сортировки массива.

Вы сохраняете два счетчика количества элементов, соблюдающих эти условия в обеих частях массива, и увеличивайте его на каждом шаге, пока не узнаете, что одна часть в порядке (счетчик равен размеру этой части). Тогда другая часть тоже ОК.

Это требует хранения O (1) и занимает время O (N).

Реализация в С++:

#include <iostream>
#include <vector>

using namespace std;

void swap(vector<int>& L, int i, int j) {
    int tmp = L[i];
    L[i] = L[j];
    L[j] = tmp;
}

void signSort(vector<int>& L) {
    int cntNeg = 0, i = 0, j = 0;
    for (vector<int>::iterator it = L.begin(); it < L.end(); ++it) {
        if (*it < 0) ++cntNeg;
    }
    while (i < cntNeg && cntNeg + j < L.size()) {
        if (L[i] >= 0) {
            swap(L, i, cntNeg + j);
            ++j;
        } else {
            ++i;
        }
    }
}

int main(int argc, char **argv) {
    vector<int> L;
    L.push_back(-1);
    L.push_back(1);
    L.push_back(3);
    L.push_back(-2);
    L.push_back(2);
    signSort(L);
    for (vector<int>::iterator it = L.begin(); it != L.end(); ++it) {
        cout << *it << endl;
    }
    return 0;
}

Ответ 17

Этот код работает с O (n) сложностью и O (1) пространством. Нет необходимости объявлять другой массив.

#include <stdio.h>

int* sort(int arr[], int size)
{
    int i;
    int countNeg = 0;
    int pos = 0;
    int neg = 0;

    for (i = 0; i < size; i++)
    {
        if (arr[i] < 0)
            pos++;
    }

    while ((pos < (size-1)) || (neg < size-(pos-1)))
    {
        if ((arr[pos] < 0) && (arr[neg] > 0))
        {
            arr[pos] = arr[pos] + arr[neg];
            arr[neg] = arr[pos] - arr[neg];
            arr[pos] = arr[pos] - arr[neg];
            pos++;
            neg++;
            continue;
        }
        if ((arr[pos] < 0) && (arr[neg] < 0))
        {
            neg++;
            continue;
        }
        if ((arr[pos] > 0) && (arr[neg] > 0))
        {
            pos++;
            continue;

        }
        if ((arr[pos] > 0) && (arr[neg] < 0))
        {
            pos++;
            neg++;
            continue;

        }
    }
    return arr;
}

void main()
{
    int arr[] = { 1, 7, -5, 9, -12, 15 };
    int size = sizeof(arr) / sizeof(arr[0]);
    sort(arr, size);
    int i;
    for (i = 0; i < size; i++)
    {
        printf("%d ,", arr[i]);
    }
    printf(" \n\n");
}

Ответ 18

#include <iostream>

using namespace std;

void negativeFirst_advanced (int arr[ ], int size)

{

    int count1 =0, count2 =0;

    while(count2<size && count1<size)
{

        if(arr[count1]>0 && arr[count2]<0)
        {       
            int temp = arr[count1];
            arr[count1] = arr[count2];
            arr[count2] = temp;
        }

        if (arr[count1]<0)
            count1++;
        if (arr [count2]>0)
            count2++;

    }
}

int main()
{

        int arr[6] = {1,7,-5,9,-12,15};
        negativeFirst_advanced (arr, 6);
        cout<<"[";
        for (int i =0; i<6;i++)
            cout<<arr[i]<<" , ";
        cout<<"]";

        system("pause");
        return 0;
}

Ответ 19

Вот мое решение в Python, используя рекурсию (у меня было задание вроде этого, где массив должен быть отсортирован относительно числа K. Если вы положили K = 0, у вас есть ваше решение, без сохраняя порядок внешнего вида):

def kPart(s, k):
    if len(s) == 1:
        return s
    else:
        if s[0] > k:
            return kPart(s[1:], k) + [s[0]]
        else:
            return [s[0]] + kPart(s[1:], k)

Ответ 20

Это не сложность O (1), а более простой подход. Сделайте комментарий

void divide (int *arr, int len) {
    int positive_entry_seen = 0;                                                                                             
    for (int j = 0; j < len ; j++) { 
        if (arr[j] >= 0 ) { 
            positive_entry_seen = 1;
        } else if ((arr[j] < 0 ) && positive_entry_seen) {
            int t = arr[j];
            int c = j;
            while ((c >= 1) && (arr[c-1] >= 0)) {
                arr[c] = arr[c-1];
                c--;
            }   
            arr[c] = t;
        }   
    }   
}

Ответ 21

Чрезвычайно простое решение ниже, но не в O (n). Я немного изменил алгоритм сортировки вставки. Вместо того, чтобы проверять, больше ли число или меньше, он проверяет, больше ли они или меньше нуля.

 int main() {

    int arr[] = {1,-2,3,4,-5,1,-9,2};

        int j,temp,size;

        size = 8;
        for (int i = 0; i <size ; i++){
            j = i;  
            //Positive left, negative right
            //To get opposite, change it to: (arr[j] < 0) && (arr[j-1] > 0)
            while ((j > 0) && (arr[j] >0) && (arr[j-1] < 0)){
                  temp = arr[j];
                  arr[j] = arr[j-1];
                  arr[j-1] = temp;
                  j--;
            }
        }

        //Printing
        for(int i=0;i<size;i++){
            cout<<arr[i]<<" ";      
        }
        return 0;
 }

Ответ 22

Простое и простое решение, которое работает в O (n) сложности времени.

    int left = 0;
    int right = arr.length - 1;

    while (left < right) {

        while (arr[left] >= 0) {
            left++;
        }

        while (arr[right] < 0) {
            right--;
        }

        if (left < right) {
            ArrayUtility.swapInArray(arr, left, right);
    }

    ArrayUtility.printArray(arr);

Ответ 23

При этом используется процесс разбиения QuickSort. Временная сложность этого решения составляет O (n2), а вспомогательное пространство - O (1). Этот подход поддерживает порядок появления и не использовал никакой другой структуры данных. Это в рубине

def sortSeg(intArr)
    intArr.each_with_index do |el, idx|
        # if current element is pos do nothing if negative,
        # shift positive elements of arr[0..i-1],
        # to one position to their right */
        if el < 0
            jdx = idx - 1;
            while (jdx >= 0 and intArr[jdx] > 0)
                intArr[jdx + 1] = intArr[jdx];
                jdx = jdx - 1;
            end
            # Insert negative element at its right position
            intArr[jdx + 1] = el;
        end
    end
end

Ответ 24

int [] input = {1, 7, -5, 9, -12, 15};
int [] output = new int [input.length];
int negativeIdx = 0;
int positiveIdx = input.length - 1;
for(int i = 0; i < input.length ; i++) {
    if(input[i] < 0) {
        output [negativeIdx++] = input[i];
    } else {
        output [positiveIdx--] = input[i];
    }
}
System.out.println

(Arrays.toString(output));

Выход:

[-5, -12, 15, 9, 7, 1]

Ответ 25

Это можно сделать, выполнив следующие шаги в O (n), не используя лишнее пространство

int count = 0;
//data is the array/vector in sort container having given input.
if(data[0] < 0)
    count++;
for(int i = 1; i < n; i++)
{
    if(data[i] < 0)
    {
        int j = i;
        while(j> count)
        {
            data[j-1] += data[j];
            data[j] = (data[j-1]-data[j]);
            data[j-1] -= data[j];
            j--;
        }
        count++;
    }
}

полную реализацию можно найти здесь https://gist.github.com/Shravan40/8659568

Ответ 26

Я жестко закодировал значения массива. Однако он будет работать с любым набором целых чисел.

    int[] n={2,-3,1,5,-10,-8};
    int k=0;
    for(int i=1;i<n.length;i++)
    {
        int temp=0;
        if(n[i]<0)
        {
            temp=n[k];
            n[k]=n[i];
            n[i]=temp;
            k++;
        }
    }

        for(int j=0;j<n.length;j++)
    {
        System.out.println(n[j]);
    }

Ответ 27

Надеюсь, это поможет. У этого есть временная сложность O (n ^ 2)

#include <stdio.h>

int main() {
    int a[] = {-3, 2, -5, 9, -2, -8, 6, 8, -1, 6};

    int length = (sizeof(a) / sizeof(int));
    int i, j = 0;

    printf("Size of array: %d\n", sizeof(a));

    for (i = 0; i < length; i++) {
        if (i % 2 == 0 && a[i] < 0) {
            for (j = i + 1; j < length; j++) {
                if (a[j] > 0) {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                    break;
                }
            }
        } else if (i % 2 == 1 && a[i] > 0) {
            for (j = i + 1; j < length; j++) {
                if (a[j] < 0) {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                    break;
                }
            }
        }
    }

    for (i = 0; i < length; i++) {
        printf("Value at %d: %d\n", i, a[i]);
    }

    return 0;
}

РЕДАКТИРОВАТЬ 1 Это зависит от того, что числа больше нуля всегда имеют четный индекс, а числа, меньшие нуля, всегда имеют нечетный индекс

РЕДАКТИРОВАТЬ 2 Немного улучшил код

Ответ 28

здесь мой ответ - два отдельных положительных и отрицательных значения в одном массиве, это поможет вам

int[] singleArray= {300, -310, 320, 340, 350,
                -330, 420, 370, -360, 390,
                340, -430, 320, -463, 450}; 
public double[] getPositive_SingleArray() {
            double minValue = 0;
            double positiveValue=0;
            int count=0;
            for (int i = 0; i < singleArrayData.length; i++) {
                if ( singleArrayData[i]>0)
                    count++;
            }
            positiveSingleArrayData=new double[count];
            int k=0;
            for (int i = 0; i < singleArrayData.length; i++) {
                if ( singleArrayData[i]>0){
                positiveSingleArrayData[k] = singleArrayData[i];
                k++;
                }
             }
            System.out.println("single array of positve values "+Arrays.toString(positiveSingleArrayData));
            return positiveSingleArrayData;
        }

Ответ 29

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

int main()
{
    int array[TAM], num, i=0, j=0;

    printf("Ingrese arreglo: ");

    for(i=0; i < TAM -1 && num != 0; i++)
    {
        scanf("%d", &num);
        array[i]=num;
    }

    for(i=0; array[i] != 0 ; i++)
    {
        j++;
    }

    Alternar(array, j);

    //MOSTRAR
    for(i=0; i < j; i++)
    {
        printf("%d ", array[i]);
    }


    return 0;
}

void Alternar(int array[], int j)
{
    int i=0, aux, pasadas=1;

    for(pasadas=1; pasadas < j; pasadas++)
    {
        for(i=0; i < j - pasadas ; i++)
        {
            if(array[i] > 0 && array[i+1] < 0)
            {
                aux = array[i];
                array[i] = array[i+1];
                array[i+1] = aux;
            }
        }
    }

}

Ответ 30

Посмотрите на Heapsort в таблице алгоритмов сортировки в Википедии: http://en.wikipedia.org/wiki/Sorting_algorithm