Wikipedia

Khác biệt giữa bản sửa đổi của “Sắp xếp vun đống”

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
Xóa link phần demo của vun đống vì nó dẫn vào một trang quảng cáo
Sửa đổi mã theo cấu trúc dữ liệu để có thể áp dụng trong nhiều bài toán khác nhau và nhiều dự án lớn.
Dòng 48:
* Mảng còn lại chỉ một phần tử. Quá trình sắp xếp đã xong.
 
==Mã giả bằng ngôn ngữ C có sử dụng câu trúc dữ liệu: ==
==Mã giả ==
 
<source lang="c" line="1">
#include <stdio.h>
function heapSort(a[1..count], count) {
#include <conio.h>
var int end:= count
MakeHeap(a,count)
while end > 0
swap(a[end], a[1])
end:= end - 1
DownHeap(a,0, end)
}
 
const int n = 10;
function MakeHeap(a, count) {
typedef int keytype;
var int start:= Int(count/2)
typedef float othertype;
typedef struct recordtype{
while start > 0
keytype DownHeap(a,key; start, count)
othertype start:= start - 1otherfields;
};
}
// khai bao mang a co n phan tu
recordtype a[n];
function DownHeap(a, start, count) {
 
var int i:= start, j
void Swap(recordtype &x, recordtype &y)
j:= i * 2
{
while j <= count {
recordtype temp;
if j+1 <= count and a[j] < a[j + 1]
temp j:= j + 1x;
x = if a[i] < a[j]y;
y = swap(a[i], a[j])temp;
}
i:= j
 
j:= j * 2
void PushDown(int first, int last)
else
{
return
//while (r <= (last - 1) / 2)
}
if (first == last || first > (last - 1) / 2) return;
}
if (last == 2 * first + 1) {
if (a[first].key > a[last].key)
Swap(a[first], a[last]);
//first = last;
return;
}else
if ((a[first].key > a[2*first+1].key) && (a[2*first+1].key <= a[2*first+2].key))
{
Swap(a[first], a[2*first+1]);
PushDown(2 * first + 1, last);
}else
if ((a[first].key > a[2*first+2].key) && (a[2*first+2].key < a[2*first+1].key))
{
Swap(a[first], a[2*first+2]);
PushDown(2 * first + 2, last);
}
else return; //first = last;
}
 
void HeapSort(void)
{ int i;
/*1*/ for(i = (n-2) / 2; i >= 0; i--)
/*2*/ PushDown(i, n-1);
/*3*/ for(i = n-1; i>=2; i--) {
/*4*/ Swap(a[0], a[i]);
/*5*/ PushDown(0, i-1);
}
/*6*/ Swap(a[0], a[1]);
}
 
 
void readList(recordtype a[])
{
for (int i = 0; i < n; i++)
{
printf("Phan tu %d = ", i+1);
scanf("%d",&a[i]);
}
}
void printList(recordtype a[])
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
}
int main()
{
printf("Nhap %d phan tu cho danh sach.\n", n);
readList(a);
printf("Danh sach sau khi duoc nhap: \n");
printList(a);
HeapSort();
printf("\nDanh sach sau khi duoc sap xep: \n");
printList(a);
getch();
return 0;
}
</source>
 
Lấy từ “https://vi.wikipedia.org/wiki/Sắp_xếp_vun_đống”