VietTuts

Tự Học Lập Trình Online

  • Home
  • Java
  • Servlet
  • JSP
  • Struts2
  • Hibernate
  • Spring
  • MyBatis
  • Java WS
  • C
  • C++
  • C#
  • Python
  • PHP
  • Excel
  • VBA
  • Web
    • JavaScript
    • JQUERY
    • JSON
    • AJAX
    • CSS
    • HTML
    • HTML5
    • Node.js
    • Angular 7
  • SQL
    • MySQL
    • SQL Server
  • Misc
    • Eclipse
    • Phần mềm tiện ích
    • Cấu trúc DL&GT
    • Selenium Test

Cấu Trúc Dữ Liệu & Giải Thuật

Tổng quan về cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu là gì? Giải thuật là gì? Cài đặt môi trường

Giải Thuật

Giải thuật tiệm cận Giải thuật tham lam Giải thuật chia để trị Giải thuật qui hoạch động

Cấu Trúc Dữ Liệu Mảng

Cấu trúc dữ liệu mảng

Danh sách liên kết - Linked list

Cấu trúc dữ liệu Linked List Cấu trúc dữ Doubly Linked List Cấu trúc dữ Circular Linked List

Ngăn Xếp & Hàng Đợi

Cấu trúc dữ liệu ngăn xếp - Stack Cấu trúc dữ hàng dợi - Queue

Một Số Giải Thuật Tìm Kiếm

Tìm kiếm tuyến tính - Linear Search Tìm kiếm nhị phân - Binary Search Tìm kiếm nội suy - Interpolation Search Cấu trúc dữ liệu Hash Table

Một Số Giải Thuật Sắp Xếp

Giải thuật sắp xếp Sắp xếp nổi bọt - Bubble Sort Sắp xếp chèn - Insertion Sort Sắp xếp chọn - Selection Sort Sắp xếp trộn - Merge Sort Sắp xếp nhanh - Quick Sort Giải thuật Shell Sort Giải thuật quay lui - Back Tracking

Cấu Trúc Dữ Liệu Đồ Thị (Graph)

Cấu trúc dữ liệu đồ thị Tìm kiếm theo chiều sâu - Depth First Search Tìm kiếm theo chiều sâu - Breadth First Search
1 / 3
❮ ❯

Giải thuật sắp xếp trộn (Merge Sort)


Giải thuật sắp xếp chọn (Selection Sort)
Giải thuật sắp xếp nhanh (Quick Sort)

Nội dung chính

  • Sắp xếp trộn (Merge Sort) là gì?
  • Cách giải thuật sắp xếp trộn (Merge Sort) làm việc
  • Giải thuật cho Sắp xếp trộn (Merge Sort)
  • Giải thuật mẫu cho Sắp xếp trộn (Merge Sort)

Sắp xếp trộn (Merge Sort) là gì?

Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Conquer). Với độ phức tạp thời gian trường hợp xấu nhất là Ο(n log n) thì đây là một trong các giải thuật đáng được quan tâm nhất.

Đầu tiên, giải thuật sắp xếp trộn chia mảng thành hai nửa và sau đó kết hợp chúng lại với nhau thành một mảng đã được sắp xếp.


Cách giải thuật sắp xếp trộn (Merge Sort) làm việc

Dưới đây là các hình minh họa cách giải thuật sắp xếp trộn làm việc. Giả sử chúng ta có mảng sau:

Giải thuật sắp xếp trộn (Merge Sort)

Đầu tiên, giải thuật sắp xếp trộn chia toàn bộ mảng thành hai nửa. Tiến trình chia này tiếp tục diễn ra cho đến khi không còn chia được nữa và chúng ta thu được các giá trị tương ứng biểu diễn các phần tử trong mảng. Trong hình dưới, đầu tiên chúng ta chia mảng kích cỡ 8 thành hai mảng kích cỡ 4.

Giải thuật sắp xếp trộn (Merge Sort)

Tiến trình chia này không làm thay đổi thứ tự các phần tử trong mảng ban đầu. Bây giờ chúng ta tiếp tục chia các mảng này thành 2 nửa.

Giải thuật sắp xếp trộn (Merge Sort)

Tiến hành chia tiếp cho tới khi không còn chia được nữa.

Giải thuật sắp xếp trộn (Merge Sort)

Bây giờ chúng ta tổ hợp chúng theo như đúng cách thức mà chúng được chia ra.

Đầu tiên chúng ta so sánh hai phần tử trong mỗi list và sau đó tổ hợp chúng vào trong một list khác theo cách thức đã được sắp xếp. Ví dụ, 14 và 33 là trong các vị trí đã được sắp xếp. Chúng ta so sánh 27 và 10 và trong list khác chúng ta đặt 10 ở đầu và sau đó là 27. Tương tự, chúng ta thay đổi vị trí của 19 và 35. 42 và 44 được đặt tương ứng.

Giải thuật sắp xếp trộn (Merge Sort)

Vòng lặp tiếp theo là để kết hợp từng cặp list một ở trên. Chúng ta so sánh các giá trị và sau đó hợp nhất chúng lại vào trong một list chứa 4 giá trị, và 4 giá trị này đều đã được sắp thứ tự.

Giải thuật sắp xếp trộn (Merge Sort)

Sau bước kết hợp cuối cùng, danh sách sẽ trông giống như sau:

Giải thuật sắp xếp trộn (Merge Sort)

Phần tiếp theo chúng ta tìm hiểu một số khía cạnh khác của giải thuật sắp xếp trộn.


Giải thuật cho Sắp xếp trộn (Merge Sort)

Giải thuật sắp xếp trộn tiếp tục tiến trình chia danh sách thành hai nửa cho tới khi không thể chia được nữa. Theo định nghĩa, một list mà chỉ có một phần tử thì list này coi như là đã được sắp xếp. Sau đó, giải thuật sắp xếp trộn kết hợp các sorted list lại với nhau để tạo thành một list mới mà cũng đã được sắp xếp.

Output:

Bước 1: Nếu chỉ có một phần tử trong list thì list này được xem như là đã được 
sắp xếp. Trả về list hay giá trị nào đó.
Bước 2: Chia list một cách đệ qui thành hai nửa cho tới khi không thể chia được nữa.
Bước 3: Kết hợp các list nhỏ hơn (đã qua sắp xếp) thành list mới (cũng đã được sắp xếp).

Giải thuật mẫu cho Sắp xếp trộn (Merge Sort)

Có thể nói rằng với giải thuật sắp xếp trộn, bạn cần chú ý hai điểm chính: chia và hợp.

Bởi vì giải thuật sắp xếp trộn làm việc theo phương thức đệ qui nên phần triển khai giải thuật chúng ta cũng nên sử dụng đệ qui để biểu diễn.


Bắt đầu giải thuật sắp xếp trộn mergesort( biến a là một mảng )
   if ( n == 1 )
	   return a
   khai báo biến l1 là một mảng = a[0] ... a[n/2]
   khai báo biến l2 là một mảng = a[n/2+1] ... a[n]
   l1 = mergesort( l1 )
   l2 = mergesort( l2 )
   return merge( l1, l2 ) // gọi hàm merge()
Kết thúc giải thuật
Bắt đầu hàm merge( Mảng a, mảng b )
   khai báo biến c là một mảng
   while ( a và b có phần tử )
      if ( a[0] > b[0] )
         Thêm b[0] vào cuối mảng c
         Xóa b[0] từ b
      else
         Thêm a[0] vào cuối mảng c
         Xóa a[0] từ a
      kết thúc if
   kết thúc while
   
   while ( a có phần tử )
      Thêm a[0] vào cuối mảng c
      Xóa a[0] từ a
   kết thúc while
   
   while ( b có phần tử )
      Thêm b[0] vào cuối mảng c
      Xóa b[0] từ b
   kết thúc while
   
   return c
 
Kết thúc hàm

Giải thuật sắp xếp chọn (Selection Sort)
Giải thuật sắp xếp nhanh (Quick Sort)

Recent Updates

Xuất dữ liệu ra màn hình console trong JavaCài đặt môi trường JavaJava Swing - Bài tập quản lý sinh viên trong javaLinkedList trong javaArrayList trong javaBài tập java có lời giảiXác thực dữ liệu (Data Validation) trong ExcelSắp xếp dữ liệu trong ExcelLọc dữ liệu (Data Filter) trong ExcelHeader và Footer trong ExcelMàu văn bản và màu nền (background) trong ExcelCăn chỉnh văn bản trong ExcelSắp Tết 2026 Rồi! - Còn bao nhiêu ngày nữa là đến tết 2026?

VietTuts on facebook

Học Lập Trình Online Miễn Phí - VietTuts.Vn
Danh Sách Bài Học

Học Java | Hibernate | Spring
Học Excel | Excel VBA
Học Servlet | JSP | Struts2
Học C | C++ | C#
Học Python
Học SQL

Bài Tập Có Lời Giải

Bài tập Java
Bài tập C
Bài tập C++
Bài tập C#
Bài tập Python
Ví dụ Excel VBA

Câu Hỏi Phỏng Vấn

201 câu hỏi phỏng vấn java
25 câu hỏi phỏng vấn servlet
75 câu hỏi phỏng vấn jsp
52 câu hỏi phỏng vấn Hibernate
70 câu hỏi phỏng vấn Spring
57 câu hỏi phỏng vấn SQL

Scroll back to top

Copyright © 2016 VietTuts.Vn all rights reserved. | Liên hệ | Chính sách - riêng tư | sitemap.html | sitemap_index.xml