[Thuật toán] Các thuật toán sắp xếp trong lập trình C - Heap Sort - Vun đống


  1. Bubble sort. (Nổi bọt, nổi bong bóng)
  2. Quick sort. (Sắp xếp nhanh)
  3. Simple selection sort. (Sắp xếp chọn)
  4. Heap sort. (Sắp xếp vun đống)
  5. Simple insertion sort.(Sắp xếp chèn)
  6. Shell sort.
  7. Merge sort. (Sắp xếp hòa nhập)

 Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).
Thuật toán sắp xếp vun đống - tinhoccoban.net
Thuật toán sắp xếp vun đống

C++ Code:
  1. #include < iostream.h >
  2. #include < conio.h >
  3. int heapSize = 10;
  4. void print(int a[])
  5. {
  6.   for (int i = 0; i <= 9; i++)
  7.  {
  8.     cout << a[i] << "-";
  9.   }
  10.   cout << endl;
  11. }
  13. int parent(int i)
  14. {
  15. if(i==1)
  16. return 0;
  18. if(i%2==0)
  19.     return ( (i / 2)-1);
  20. else
  21.     return ( (i / 2));
  22. }
  24. int left(int i)
  25. {
  26.   return (2 * i) + 1;
  27. }
  29. int right(int i)
  30. {
  31.   return (2 * i) + 2;
  32. }
  34. void heapify(int a[], int i)
  35. {
  36.   int l = left(i), great;
  37.   int r = right(i);
  38.   if ( (a[l] > a[i]) && (l < heapSize))
  39.  {
  40.     great = l;
  41.   }
  42.   else {
  43.     great = i;
  44.   }
  45.   if ( (a[r] > a[great]) && (r < heapSize))
  46.  {
  47.     great = r;
  48.   }
  49.   if (great != i)
  50.  {
  51.     int temp = a[i];
  52.     a[i] = a[great];
  53.     a[great] = temp;
  54.     heapify(a, great);
  55.   }
  56. }
  58. void BuildMaxHeap(int a[])
  59. {
  60.  for (int i = (heapSize - 1) / 2; i >= 0; i--)
  61.  {
  62.     heapify(a, i);
  63.     print(a);
  64.   }
  65. }
  67. void HeapSort(int a[]) {
  68.   BuildMaxHeap(a);
  69.   for (int i = heapSize; i > 0; i--)
  70.  {
  71.     int temp = a[0];
  72.     a[0] = a[heapSize - 1];
  73.     a[heapSize - 1] = temp;
  74.     heapSize = heapSize - 1;
  75.     heapify(a, 0);
  76.   }
  78. }
  80. void main()
  81. {
  82.   int arr[] = {2, 9, 3, 6, 1, 4, 5, 7, 0, 8};
  83.   HeapSort(arr);
  84.   print(arr);
  85. }

Bài đăng phổ biến

Bài viết mới nhất

Tin học cơ bản - Nền tảng của mọi kỹ năng

Mọi thông tin trên blog đều được giữ bản quyền bởi Tin học cơ bản. Các bạn nếu muốn lấy thông tin từ blog vui lòng ghi rõ nguồn Tinhoccoban.net

TIN HỌC CƠ BẢN