Làm thế nào để sắp xếp lại một mảng theo cách như vậy mà mỗi phần tử lớn/nhỏ hơn so với các nước láng giềng

Question

Ví dụ, nếu các số là:

30, 12, 49, 6, 10, 50, 13 

Mảng sẽ là:

[10, 6, 30, 12, 49, 13, 50] 

Như bạn có thể thấy:

• 6 là nhỏ hơn so với cả 10 và 30 và
• 49 là rất tốt er hơn 12 và 13 và cứ tiếp tục như vậy.

Các con số đều khác nhau và thực tế. Tôi cần thuật toán hiệu quả nhất.

Answer 1

Điều này có thể được thực hiện trong thời gian O (n):

1. Tìm trung bình trong thời gian O (n) (mô tả có sẵn trong Wikipedia
2. Đặt mọi phần tử lớn hơn so với trung bình trên những nơi kỳ lạ và mọi phần tử nhỏ hơn - ngay cả những nơi

Tất nhiên, điều này giả định rằng tất cả các yếu tố này là khác biệt, nếu không đôi khi nó sẽ thất bại.

Answer 2

Giả sử tất cả các số đều khác nhau, cách dễ nhất có thể là sắp xếp các số sau đó xen kẽ nửa đầu tiên và thứ hai của danh sách được sắp xếp. Điều này sẽ đảm bảo mẫu cao/thấp/cao/thấp/cao/thấp/.... mà bạn cần.

Thuật toán này là O(n log n) cần đủ hiệu quả cho hầu hết các mục đích và có thể hưởng lợi từ các thường trình sắp xếp được tối ưu hóa trong thư viện chuẩn của bạn.

Nếu con số này không rõ rệt, sau đó nó có thể là không có giải pháp (ví dụ nếu các con số đều bình đẳng)

Answer 3

Tôi không quá am hiểu về sự phức tạp, nhưng đây là ý tưởng của tôi. đang

For even length lists: 

(For our odd length example, 
put 30 aside to make the list even) 

1. Split the list into chunks of 2 => [[12,49],[6,10],[50,13]] 
2. Sort each chunk     => [[12,49],[6,10],[13,50]] 
3. Reverse-sort the chunks by 
    comparing the last element of 
    one to the first element of 
    the second       => [[12,49],[13,50],[6,10]] 

For odd length lists: 
4. Place the removed first element in 
    the first appropriate position  => [30,12,49,13,50,6,10] 

Haskell:

import Data.List (sortBy) 
import Data.List.Split (chunksOf) 

rearrange :: [Int] -> [Int] 
rearrange xs 
    | even (length xs) = rearrangeEven xs 
    | null (drop 1 xs) = xs 
    | otherwise  = place (head xs) (rearrangeEven (tail xs)) 
where place x (y1:y2:ys) 
     | (x < y1 && y1 > y2) || (x > y1 && y1 < y2) = (x:y1:y2:ys) 
     | otherwise         = place' x (y1:y2:ys) 
     place' x (y1:y2:ys) 
     | (x < y1 && x < y2) || (x > y1 && x > y2) = (y1:x:y2:ys) 
     | otherwise        = y1 : (place' x (y2:ys)) 
     rearrangeEven = concat 
        . sortBy (\a b -> compare (head b) (last a)) 
        . map sort 
        . chunksOf 2 

Output:

*Main> rearrange [30,12,49,6,10,50,13] 
[30,12,49,13,50,6,10] 

*Main> rearrange [1,2,3,4] 
[3,4,1,2] 

Answer 4

Một người nào đó đã đăng câu hỏi này làm bản dupe cho this nhưng giải pháp ở đó tốt hơn giải pháp được chấp nhận ở đây vì vậy tôi nghĩ tôi sẽ đăng câu hỏi ở đây.

Về cơ bản, khóa là cho mỗi ba số trong đó phải giữ số đó a <b> c bạn xem chuỗi và hoán đổi số lớn nhất vào giữa. Sau đó, bạn tăng thêm 2 để đến chuỗi tiếp theo như a <b> c và thực hiện tương tự.

Về mặt kỹ thuật, giải pháp vẫn chạy trong O (n) như giải pháp được chấp nhận, nhưng nó là một O (n) tốt hơn và nó đơn giản hơn nhiều vì trung bình algo là khó thực hiện. Hy vọng rằng bất cứ ai yêu thích vấn đề này sẽ ít nhất là xem giải pháp này, tôi có thể đăng mã nếu có ai quan tâm.