01/10/2018, 08:25
CTDL>: Heap Sort
E đang học ctdl + gt. Hnay mới thử tìm hiểu cái heap sort vs viết thử cái chương trình. A chị nào rảnh thì giúp e kiểm tra xem nó đã đúng chưa vs ạ
#include <stdio.h>
#include <conio.h>
int swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
return 0;
}
int main()
{
int array[100], i, j, top, left, right, max;
int n = 50;
int m = 50;
int x = 50;
for(i = 0; i < n; i++) //Tạo mảng chưa được sắp xếp
{
array[i] = x;
x--;
}
while(n > 1)
{
for(i = n/2 - 1; i >= 0; i-- )
{
left = i*2 + 1;
max = i;
top = i;
max = array[max] > array[left] ? max : left;
if(i*2 + 2 <= n - 1)
{
right = i*2 + 2;
max = array[max] > array[right] ? max : right;
}
while(max != top)
{
swap(&array[max], &array[top]);
top = max;
if(top*2 + 1 <= n - 1) left = top*2 + 1;
max = array[max] > array[left] ? max : left;
if(top*2 + 2 <= n - 1)
{
right = top*2 + 2;
max = array[max] > array[right] ? max : right;
}
}
}
swap(&array[0], &array[n - 1]); // Hoán vị 2 phần tử
n--;
}
n = m;
for(i = 0; i < m; i++)
{
i == m - 1 ? printf("%d.
") : printf("%d, ", array[i]);
}
getch();
return 0;
}
Bài liên quan
Waw. Ý tưởng không dùng đệ quy để lan truyền thay đổi sau khi hiệu chỉnh Heap.
chia hàm ra để quản lý và còn sửa lỗi nếu gặp cho dễ bạn.