сортировать массив по относительной позиции

Question

Дайте массив, который имеет отрицательные и положительные целые числа, реализуйте алгоритм, который стоит O (n) времени и O (1) пробелов , чтобы сделать все отрицательные целые числа перед всеми положительными целыми числами, и сохранить относительное положение например: {1,7, -5,9, -12,15} -----> {-5, -12,1,7,9,15}

у вас есть идеи?

Answer 1

Вы запрашиваете стабильную функцию разбиения на месте.

В статье Стабильное разбиение минимального пространства в линейном времени (1992) утверждает, что имеет такой алгоритм, но некоторые другие SO вопросы вызвали сомнения в его целесообразности.

Answer 2

моя идея для алгоритма:

имеет точку опоры, аналогичную общей выборке на основе разделов.http://en.wikipedia.org/wiki/Selection_algorithm

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

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

Каждый раз, когда вы меняли местами два числа ... меняйте знак числа.

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

negs = -4,-5,-6
pos = 1,2,3
ans = -4,-5,-6,1,2,3

1,2,-4,-5,3,-6

i->-4  j->-5
-4 and -5 are both negative.. decrease i by one

1,2,-4,-5,3,-6
i->2 j->-5
swap.

1,5,-4,-2,3,-6
i->1 j->3
1 and 3 are both positive, increase j by one (take turns at changing i,j)

1,5,-4,-2,3,-6
i->1 j->-6
swap.

6,5,-4,-2,3,-1

#now we have negs at start, pos at end of array.
#now do corrections using signs as notification of what was swapped
#we had a counter that told us there were 3 negs.and 3 pos.
#fix first 3 negs.. 6,5,-4 should go to -4,-5,-6
(can tell order by. non swapped negs always come before swapped negs..in the order they are in.. negs are in reverse order)
i'll leave you to implement algorithm for it.

Answer 3

Это можно сделать с помощью изменения функции слияния в алгоритме сортировки слиянием .

Ввод: int [] A, int low, int mid, int high

Цикл дисперсии перед запуском: A [низкий] - A [средний] имеет -ve числа, следующие после + ve, и имеет номера, которые изначально присутствовали в диапазоне от [[низкий] до A [средний].
Вышеупомянутое условие выполняется для A [mid + 1] - A [high]

Этапы объединения:

1. пропустить все элементы между низкими и средними, которые являются -ve, сохраните начальную точку числа + ve, скажем, в переменной j.
2. скопируйте остальные элементы, которые находятся + ve перед серединой, во временный массив
3. скопируйте все элементы -ve в диапазоне mid + 1 ввысокий, начиная с A [j], при увеличении j
4. копировать элементы, хранящиеся во временном массиве, обратно в A, продолжая с j

5. + ve элементы во второй половине A уже находятся вместо, поэтому не нужно ничего делать

   public static void rearrange(int[] a){
       merge_arrange(a, 0, a.length-1);
   }
   
   public static void merge_arrange(int[] a, int low, int high){
       if(low < high){
           int mid = (low+high)/2;
           merge_arrange(a, low, mid);
           merge_arrange(a, mid+1, high);
   
           merge(a, low, mid, high);
       }
   }
   
   public static void merge(int[] a, int low, int mid, int high){
       ArrayList<Integer> temp = new ArrayList<Integer>();
   
       int i;
       for(i=low;i<=mid && a[i]<0;i++);
   
       int j=i;
       while(i<=mid){
           temp.add(a[i++]);
       }
   
       int k;
       for(k=mid+1;k<=high && a[k]<0;k++){
           a[j] = a[k];
           j++;
       }
   
       for(int num:temp){
           a[j] = num;
           j++;
       }
   }
   

Answer 4

Этот код по большей части там. Я просто не сделал ту часть, где он меняет местами поменяемые значения между x, j и между j, y. (можно поменять местами .. я еще этого не сделал).

Во всяком случае .. У меня нет времени, чтобы завершить это, я боюсь, но, надеюсь, вы можете:

def brute_force(nums):
    neg = [i for i in nums if i<0]
    pos = [i for i in nums if i>=0]
    return neg+pos

def in_place(nums,i,j,depth):
    x,y = i,j
    print 'running on ',nums[i:j+1]
    if j-i==1:
        a,b = nums[i],nums[j]
        if a>=0 and b<0:
            nums[i],nums[j] = b,a
        return None
    #print i,j
    while i<j:
        a,b = nums[i],nums[j]
        if (a<0 and b>=0):
            i+=1
            j-=1
        elif (a>=0 and b<0):
            nums[i],nums[j]=-b,-a
            i+=1
            j-=1
        elif a<0:
            i+=1
        else:
            j-=1
    print "changed1 to ", nums
    print nums[x:j+1],nums[j+1:y+1]
    start = (i for i in reversed(nums[x:j+1]) if i>=0)
    for i in range(x,j):
        if nums[i]>=0:
            nums[i]=next(start)
    print "changed2 to ", nums
    end = (i for i in reversed(nums[j+1:y+1]) if i<0)
    for i in range(j+1,y+1):
        if nums[i]<0:
            nums[i]=next(end)
    print "changed3 to ", nums
    if depth == 0:
        in_place(nums,0,j,depth+1)
        in_place(nums,j+1,len(nums)-1,depth+1)







nums = [1,2,-4,-5,3,-6]

print brute_force(nums)
in_place(nums,0,len(nums)-1,0)
print nums
print "going z"
#z = [-2,3,-1]
#in_place(z,0,2,0)
#print z

Дальнейший пример:

_list = [1,-4,2,-5,3,-6]

def in_place(nums,i,j,depth):
    x,y = i,j
    print 'running on ',nums[i:j+1]
    if j-i==1:
        a,b = nums[i],nums[j]
        if a>=0 and b<0:
            nums[i],nums[j] = b,a
        return None
    #print i,j
    while i<j:
        a,b = nums[i],nums[j]
        if (a<0 and b>=0):
            i+=1
            j-=1
        elif (a>=0 and b<0):
            nums[i],nums[j]=-b,-a
            i+=1
            j-=1
        elif a<0:
            i+=1
        else:
            j-=1
    print "changed1 to ", nums

in_place(_list,0,len(_list)-1,0)

>>>
running on  [1, -4, 2, -5, 3, -6]
changed1 to  [6, -4, 5, -2, 3, -1]