Thuật toán merge sort c++

Chào ace, bài này chúng ta sẽ khám phá về một trong các thuật toán thu xếp được áp dụng nhiều trong xây dựng và thực tiễn nhất sẽ là Merge Sort, tiếp sau đây shopbcs.net sẽ trình làng và chia sẻ chi tiết(khái niệm, áp dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Merge Sort thông qua các phần sau.

Bạn đang xem: Thuật toán merge sort c++

1. Giới thiệu

Giống như QuickSort, Merge Sort là 1 trong thuật toán phân tách và Chinh phục. Nó chia mảng đầu vào thành nhị nửa, gọi thiết yếu nó mang lại hai nửa và tiếp nối hợp nhất hai nửa đã chuẩn bị xếp. Hàm merge () được thực hiện để hợp duy nhất hai nửa. Hợp duy nhất (arr, l, m, r) là vượt trình quan trọng đặc biệt giả định rằng arr và arr được bố trí và hợp tốt nhất hai mảng con đã bố trí thành một. Xem cách thực hiện C sau để hiểu biết thêm chi tiết.

MergeSort (arr <>, l, r)Nếu r> l 1. Tìm điểm giữa để phân chia mảng thành nhì nửa: Ở giữa m = (l + r) / 2 2. Hợp độc nhất vô nhị cuộc gọi bố trí cho nửa đầu: call mergeSort(arr, l, m) 3. Hợp độc nhất vô nhị cuộc gọi thu xếp cho nửa sau: gọi mergeSort(arr, m + 1, r) 4. Hợp nhất hai nửa được sắp xếp ở cách 2 với 3: hotline merge(arr, l, m, r)Sơ đồ tiếp sau đây từ wikipedia cho thấy quy trình bố trí hợp nhất hoàn chỉnh cho một mảng ví dụ 38, 27, 43, 3, 9, 82, 10. Nếu bọn họ xem xét kỹ rộng sơ đồ, chúng ta có thể thấy rằng mảng được chia đệ quy làm hai nửa cho đến khi size trở thành 1. Khi form size trở thành 1, các quy trình hợp duy nhất sẽ hoạt động và ban đầu hợp nhất các mảng trở lại cho tới khi mảng hoàn chỉnh đã thích hợp nhất.

Xem thêm: Xem Phim Hoạt Hình Mỹ Hay Nhất, Please Wait

Hình hình ảnh minh hoạ

2. Code lấy ví dụ trên các ngôn ngữ

C++

// C++ program for Merge Sort #include using namespace std; // Merges two subarrays of arr<>. // First subarray is arr // Second subarray is arr void merge(int arr<>, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; // Create temp arrays int L, R; // Copy data to temp arrays L<> và R<> for(int i = 0; i C

/* C program for Merge Sort */#include #include // Merges two subarrays of arr<>. // First subarray is arr // Second subarray is arr void merge(int arr<>, int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* create temp arrays */ int L, R; /* Copy data to temp arrays L<> và R<> */ for (i = 0; i Java

/* Java program for Merge Sort */class MergeSort { // Merges two subarrays of arr<>. // First subarray is arr // Second subarray is arr void merge(int arr<>, int l, int m, int r) { // Find sizes of two subarrays khổng lồ be merged int n1 = m - l + 1; int n2 = r - m; /* Create temp arrays */ int L<> = new int; int R<> = new int; /*Copy data lớn temp arrays*/ for (int i = 0; i Python3

# Python program for implementation of MergeSort def mergeSort(arr): if len(arr) >1: mid = len(arr)//2 # Finding the mid of the array L = arr<:mid> # Dividing the array elements R = arr # into 2 halves mergeSort(L) # Sorting the first half mergeSort(R) # Sorting the second half i = j = k = 0 # Copy data to lớn temp arrays L<> và R<> while i Kết quả

Given array is12 11 13 5 6 7Sorted array is5 6 7 11 12 13

3. Độ phức tạp

Độ phức hợp về thời gian: Sắp xếp những mảng trên các máy khác nhau. Merge Sort là một trong những thuật toán đệ quy với độ phức tạp thời gian có thể được biểu thị như sau.

T (n) = 2T (n / 2) + θ (n)Sự lặp lại trên hoàn toàn có thể được giải quyết bằng cách sử dụng phương pháp tree lặp lại hoặc cách thức Master. Nó phía trong trường hòa hợp II của cách thức Master và nghiệm của việc tái diễn là θ (nLogn). Độ phức tạp thời gian của thu xếp hợp nhất(Merge Sort) là θ (nLogn) vào cả 3 trường vừa lòng (xấu nhất, vừa phải và xuất sắc nhất) vì thu xếp hợp nhất luôn chia mảng thành nhì nửa và mất thời hạn tuyến tính để hợp tuyệt nhất hai nửa.

Không gian phụ trợ: O (n)

Mô hình thuật toán: phân tách và Chinh phục

Ổn định: Có

4. Ứng dụng

Merge Sort rất có lợi để sắp đến xếp các danh sách được links trong thời gian O (nLogn). Vào trường hợp danh sách được liên kết, trường hòa hợp này khác biệt chủ yếu bởi sự khác biệt trong phân bổ bộ nhớ lưu trữ của mảng và list được liên kết. Không y như mảng, những nút list liên kết rất có thể không liền kề trong cỗ nhớ. Không hệt như một mảng, trong list liên kết, bạn cũng có thể chèn các mục vào thân trong O (1) không khí thừa cùng O (1) thời gian. Bởi đó chuyển động hợp tốt nhất của bố trí hợp nhất rất có thể được triển khai mà không tồn tại thêm dung lượng cho list được liên kết. Vào mảng, bạn cũng có thể thực hiện truy vấn ngẫu nhiên lúc các phần tử nằm kề nhau trong bộ nhớ. Giả sử họ có một mảng A số nguyên (4 byte) cùng đặt add của A <0> là x thì để truy vấn A , bạn cũng có thể truy cập thẳng vào bộ lưu trữ tại (x + i * 4). Không giống như mảng, bọn họ không thể triển khai truy cập bỗng dưng trong danh sách liên kết. Sắp xếp nhanh yêu cầu không hề ít loại truy cập. Vào danh sách links để truy vấn chỉ mục đồ vật i, họ phải dịch rời từng nút từ trên đầu đến nút sản phẩm công nghệ i vì chúng ta không gồm khối bộ nhớ liên tục. Bởi đó, giá thành tăng đối với nhanh chóng. Thu xếp hợp nhất truy vấn dữ liệu một giải pháp tuần trường đoản cú và yêu cầu truy cập hốt nhiên thấp.Vấn đề hòn đảo ngược số lượngĐược áp dụng trong thu xếp bên ngoài

Nguồn cùng Tài liệu giờ đồng hồ anh tham khảo:

Tài liệu từ bỏ shopbcs.net:

Nếu các bạn thấy hay cùng hữu ích, bạn có thể tham gia các kênh sau của shopbcs.net để nhận được nhiều hơn nữa: