Sort

計數排序法(Counting Sort)

輸入範例 1

10

12 56 44 21 33 15 64 48 98 25

0

輸出範例 1

12 15 21 25 33 44 48 56 64 98

輸入範例 2

5

5 4 3 2 1

6

15 6 31 42 8 1

7

18 34 25 65 84 16 55

0

輸出範例 2

1 2 3 4 5

1 6 8 15 31 42

16 18 25 34 55 65 84

onlinejudge

def countingSort(array,k):

max=0 #尋找LList最大元素

for i in array:

if i>max:

max=i

output = [0] * k #輸出陣列歸零(與原陣列等大)

#產生並初始化數字陣列C

count = [0] * (max+1)

#計算每個元素出現次數，存入數字陣列C

for i in range(0, k):

count[array[i]] += 1

#計算<=元素的次數(第二個C)

for i in range(1, max+1):

count[i] += count[i - 1]

#原陣列每個元素在數字陣列的索引

#將元素放入輸出陣列

i = k - 1

while i >= 0:

output[count[array[i]] - 1] = array[i]

count[array[i]] -= 1

i -= 1

#複製輸出陣列到原陣列

for i in range(0, k):

array[i] = output[i]


while(True):

size = int(input())

if size==0:

break

data = list(map(int,input().split()))

countingSort(data,size)

for i in data:

print(i,end=' ')

print()


colab

# Counting sort

def countingSort(array,k):

max=0 #尋找List最大元素

for i in array:

if i>max:

max=i

output = [0] * k #輸出陣列歸零(與原陣列等大)

#產生並初始化數字陣列C

count = [0] * (max+1)

#計算每個元素出現次數，存入數字陣列C

for i in range(0, k):

count[array[i]] += 1

#累計每個元素出現次數(第二個C)

for i in range(1, max+1):

count[i] += count[i - 1]

#原陣列每個元素在數字陣列的索引

#將元素放入輸出陣列

i = k - 1

while i >= 0:

output[count[array[i]] - 1] = array[i]

count[array[i]] -= 1

i -= 1

#複製輸出陣列到原陣列

for i in range(0, k):

array[i] = output[i]


while(True):

size = int(input())

if size==0:

break

data = list(map(int,input().split()))

countingSort(data,size)

for i in data:

print(i,end=' ')

print()

助教寫法

def counting_Sort(A,B,k):

C = [0 for i in range(k+1)]

for i in range(len(A)):

C[A[i]] += 1

for i in range(1,k+1):

C[i] += C[i-1]

for i in range(len(A)-1,-1,-1):

B[C[A[i]]] = A[i]

C[A[i]] -= 1

return B


while(True):

n = int(input())

if n==0:

break

A = list(map(int,input().split()))

k = max(A)

B = [0] * len(A)

sort_result = counting_Sort(A,B,k)

for i in n:

print(sort_result[i],end=' ')

print()