|
Читайте также: |
Heap_Sort (A, n)
1. 
A – массив
2. n – размерность массива
3. l = 
4. r 
n
5. Формирование пирамиды
6. while l >1
7. do l l -1
8. Shift (A, l, r)
9. Сортировка
10. while r >1
11. do x A[1]
12. A [1] A[ r ]
13. A [ r ] x
14. r r -1
15 Shift (A, 1, r)
Shift (A, l, r)
1. Просеивание в пирамиду
2. i l
3. j 2i
4. x A[i]
5. if j< r and A[j+1]<A[j]
6. then j j+1
7. while j 
r and A[j]<x
8. do A [i] A [j]
9. i j
10. j 2i
11. if j< r and A [j+1]< A [j]
12. then j j+1
13. A [i] x
Рекурсивный алгоритм сортировки разделением
QSort (A, l, r)
1. A – массив
2. l,r – левая и правая границы части
3. if l < r
4. then k Partition (A, l, r)
5. QSort (A, l, k)
6. QSort (A, k+1, r)
Partition (A, l, r)
1 x A (l + r)/2
2 i l- 1
3 j r+ 1
4 while TRUE
5 dorepeat j j-1
6 until A [j] x
7 repeat i i+1
8 until A [i] 
x
9 if i j
10 then t A [i]
11 A [i] A [j]
12 A [j] t
13 else return j
Итеративный алгоритм сортировки разделением
Itrative_QSort (A, n)
1 A – массив
2 n – размерность массива
3 stack[1..2 n ] – массив для стека
4 stack[1] 1
5 stack[2] n
6 top 1
Repeat
8 l stack[top]
9 r stack[top+1]
10 top top-2
11 if l < r
Then
Repeat
14 i l- 1
15 j r+ 1
16 x A (l + r)/2
Repeat
18 repeat i i+1
19 until A [i] x
20 repeat j j-1
21 until A [j] x
22 if i j
Then
24 t A [i]
25 A [i] A[j]
26 A [j] t
27 until i j
28 if i - l > r - i
29 then top top+2
30 stack[top] l
31 stack[top+1] i - 1
32 l i + 1
Else
34 top top+2
35 stack[top] i + 1
36 stack[top+1] r
37 r i - 1
38 until l r
39 until top = -1
Дата добавления: 2015-11-04; просмотров: 91 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Методические указания к выполнению задания | | | Итеративный алгоритм поразрядной LSD-сортировки |