我的目標是將串列分為不需要排序的兩個小節。
想象一下，我有一個長度為 10 的串列，其中包含值 0-9。
arr = [50, 30, 20, 10, 90, 40, 100, 70, 60, 80]
我希望以索引 0 到 4 包含任何順序的值 10、20、30、40 和 50 的方式對其進行排序。
例如：
# SPLIT HERE V
[40, 30, 20, 50, 10, 70, 60, 80, 90, 100]
我研究了各種分而治之的排序演算法，但我不確定在這種情況下哪一個最適合使用。
我目前的想法是使用快速排序，但我相信有更好的方法來做我正在尋找的事情，因為不需要對所有內容進行精確排序，而是在“一般”意義上進行排序，即所有值都在各自的一邊任何排序中的中位數。
uj5u.com熱心網友回復：
對我來說，這似乎可以解決問題，除非您確實需要輸出無序：
arr = [50, 30, 20, 10, 90, 40, 100, 70, 60, 80]
sorted_arr = sorted(arr)
median_index = len(arr)//2
sub_list1, sub_list2 = sorted_arr[:median_index],sorted_arr[median_index:]
這輸出：
[10, 20, 30, 40, 50] [60, 70, 80, 90, 100]
uj5u.com熱心網友回復：
該statistics軟體包有一種查找數字串列中位數的方法。從那里，您可以使用for回圈根據值是否大于中位數將值分成兩個單獨的串列：
from statistics import median
arr = [50, 30, 20, 10, 90, 40, 100, 70, 60, 80]
med = median(arr)
result1 = []
result2 = []
for item in arr:
if item <= med:
result1.append(item)
else:
result2.append(item)
print(result1)
print(result2)
這輸出：
[50, 30, 20, 10, 40]
[90, 100, 70, 60, 80]
uj5u.com熱心網友回復：
如果您想從頭開始解決問題，您可以實作Median of Medians 演算法以在線性時間內找到未排序陣列的中位數。那么這取決于你的目標是什么。
如果您想重新排序，您可以使用 Median of Medians 演算法的結果為磁區演算法選擇一個 Pivot（快速排序的一部分）。
另一方面，使用 python，您可以遍歷陣列并將值分別附加到左陣列或右陣列。
uj5u.com熱心網友回復：
其他當前的其他答案將串列分為兩個串列，根據您的示例，我的印象是有兩個分組，但輸出是一個串列。
import numpy as np
# setup
arr = [50, 30, 20, 10, 90, 40, 100, 70, 60, 80]
# output array
unsorted_grouping = []
# get median
median = np.median(arr)
# loop over array, if greater than median, append. Append always assigns
# values at the end of array
# else insert it at position 0, the beginning / left side
for val in arr:
if val >= median:
unsorted_grouping.append(val)
else:
unsorted_grouping.insert(0, val)
# output
unsorted_grouping
[40, 10, 20, 30, 50, 90, 100, 70, 60, 80]
uj5u.com熱心網友回復：
您可以使用該statistics模塊計算中位數，然后使用它將每個值添加到一組或另一組：
import statistics
arr = [50, 30, 20, 10, 90, 40, 100, 70, 60, 80]
median = statistics.median(arr)
bins = [], [] # smaller and bigger values
for value in arr:
bins[value > median].append(value)
print(bins[0]) # -> [50, 30, 20, 10, 40]
print(bins[1]) # -> [90, 100, 70, 60, 80]
uj5u.com熱心網友回復：
您可以使用 numpy 執行此操作（如果 arr 很大，則速度要快得多）：
import numpy as np
arr = [50, 30, 20, 10, 90, 40, 100, 70, 60, 80]
arr = np.array(arr)
median = np.median(arr)
result1 = arr[arr <= median]
result2 = arr[arr > median]
輸出：
array([50, 30, 20, 10, 40])
array([ 90, 100, 70, 60, 80])
如果你想要一個串列作為輸出，你可以這樣做：
[*result1, *result2]
輸出：
[50, 30, 20, 10, 40, 90, 100, 70, 60, 80]
uj5u.com熱心網友回復：
我的第一個 Python 程式，請多多包涵。
基本上按照您的建議進行快速排序，但僅對包含中值索引的磁區進行子排序。
arr = [50, 30, 20, 10, 90, 40, 100, 70, 60, 80]
def partition(a, left, right):
pivot = (left right)//2
a[left],a[pivot] = a[pivot], a[left] # swap
pivot = left
left = 1
while right >= left :
while left <= right and a[left] <= a[pivot] :
left = 1
while left <= right and a[right] > a[pivot] :
right -= 1
if left <= right:
a[left] , a[right] = a[right], a[left]
left = 1
right -= 1
else:
break
a[pivot], a[right] = a[right] , a[pivot]
return right
def medianSplit(array):
left = 0;
right = len(array) - 1;
med = len(array) // 2;
while (left < right):
pivot = partition(array, left, right)
if pivot > med:
right = pivot - 1;
else:
left = pivot 1;
def main():
medianSplit(arr)
print(arr)
main()
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/462134.html
上一篇：比較兩個陣列的順序
下一篇：插入排序演算法，奇怪的行為