Bang hộiTiền mặt: 0 Xu Trò chơiHộp quà giáng sinhThứ Sáu, 03:15:01 - 22/11/2024
Chia sẻ kiến thức ngôn ngữ lập trình C, C++, C#, Java, Python, PHP, JS, SQL ...

Các điều hành viên: Mod, SMod, Admin

[C++] Các thuật toán sắp xếp cơ bản thường sử dụng

Re: [C++] Các thuật toán sắp xếp cơ bản thường sử dụng

#4 » Gửi bài gửi bởi nghiammo1992 » 12/09/2021 12:36 » @523439

Thuật toán sắp xếp trộn Merge Sort (nên ưu tiên dùng thuật toán Quick Sort hơn)


Mã: Chọn tất cả
#include <iostream>


using namespace std;


// Gộp hai mảng con arr[l...m] và arr[m+1..r]
void merge(int arr[], int lint mint r)
{
    
int ijk;
    
int n1 1;
    
int n2 =  m;

    
/* Tạo các mảng tạm */
    
int L[n1], R[n2];

    
/* Copy dữ liệu sang các mảng tạm */
    
for (0n1i++)
        
L[i] = arr[i];
    for (
0n2j++)
        
R[j] = arr[1j];

    
/* Gộp hai mảng tạm vừa rồi vào mảng arr*/
    
0// Khởi tạo chỉ số bắt đầu của mảng con đầu tiên
    
0// Khởi tạo chỉ số bắt đầu của mảng con thứ hai
    
l// IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả
    
while (n1 && n2)
    {
        if (
L[i] <= R[j])
        {
            
arr[k] = L[i];
            
i++;
        }
        else
        {
            
arr[k] = R[j];
            
j++;
        }
        
k++;
    }

    
/* Copy các phần tử còn lại của mảng L vào arr nếu có */
    
while (n1)
    {
        
arr[k] = L[i];
        
i++;
        
k++;
    }

    
/* Copy các phần tử còn lại của mảng R vào arr nếu có */
    
while (n2)
    {
        
arr[k] = R[j];
        
j++;
        
k++;
    }
}

/* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */
void mergeSort(int arr[], int lint r)
{
    if (
r)
    {
        
// Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn
        
int m l+(r-l)/2;

        
// Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng
        
mergeSort(arrlm);
        
mergeSort(arrm+1r);

        
merge(arrlmr);
    }
}


int main()
{

    
int arr[] {32,71,12,45,26,80,53,33,-7,99,1,5,2,-3,-100};

    
int n sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    
mergeSort(arr0n-1);

    
cout << "So luong phan tu trong mang: " << << endl;

    for (
int i arr) {
        
cout << << " ";
    }

    return 
0;
}


 
nghiammo1992
Hình đại diện của thành viên
Rank: ☀️2/30☀️
Cấp độ:
Tu luyện:
Like:
Online:
Bang hội: Tiếu Ngạo
Xếp hạng Bang hội: ⚡5/46⚡
Level:
Chủ đề đã tạo: 🩸4141/4141🩸
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝⚝⚝Truyền Thuyết⚝⚝⚝
Giới tính:
Ngày tham gia:
Đến từ:
Thiết bị:
Số điện thoại:
(Google Chrome 94.0.460)

- Chia sẻ bài viết:

- Xem full chủ đề: http://chiase123.com/viewtopic.html?t=38279

- Link bài viết: http://chiase123.com/topic38279-3.html#p523439

Quay về C, C++, C#, Java, Python, PHP, JS, SQL ...