[Powered by Google Translate] [Hợp nhất Sắp xếp] [Rob Bowden - Đại học Harvard] [Đây là CS50. - CS50.TV] Hãy nói chuyện về loại hợp nhất. Vì vậy, đến nay bạn đã nhìn thấy bong bóng loại, sắp xếp chèn và sắp xếp lựa chọn. Mặc dù tôi sẽ loại sóng tay của tôi vào những gì tôi có nghĩa là tốt hơn, hợp nhất loại nói chung thực hiện tốt hơn so với bất kỳ của 3 loại. 

Nhưng trước khi nói về loại hợp nhất, chúng ta hãy nói về việc sáp nhập 2 danh sách được sắp xếp. Chúng tôi sẽ gọi quá trình lấy 2 danh sách được sắp xếp như thế này, và thực hiện một danh sách được sắp xếp duy nhất trong số họ - kết hợp các danh sách. Làm thế nào chúng ta có thể làm điều này? Vâng, một trong những ý tưởng là chỉ dính một danh sách vào cuối của danh sách khác và sau đó sắp xếp danh sách kết quả. 

Trong khi điều này hoạt động, nó rất nhiều công việc không cần thiết. Chúng tôi có thể làm điều đó nhanh hơn là chỉ sắp xếp. Chú ý rằng sai một ý tưởng là để chỉ đưa ly xen kẽ từ mỗi danh sách. Trong khi đó có vẻ như rằng các công trình lần đầu tiên, làm điều đó chúng tôi kết thúc với 4, 8, 15, 23, 16 - thông báo rằng 16 và 23 ra khỏi vị trí. Điều này là do 2 yếu tố đó sẽ xuất hiện liên tiếp trong danh sách sáp nhập đang ở trong cùng một danh sách ban đầu. Cả hai 15 và 16 trong danh sách bên trái. Bí quyết là để tận dụng lợi thế của một thực tế rằng cả hai danh sách đã được sắp xếp. Điều này có nghĩa rằng nếu chúng ta chỉ cần nhìn vào các yếu tố đầu tiên của cả hai danh sách - ở đây, 4 và 8 - một trong số họ cũng phải có yếu tố đầu tiên của danh sách sáp nhập. Vâng, tại sao vậy? Cả hai của các danh sách đã được sắp xếp, và do đó, hoặc 4 hoặc 8 phải là phần tử nhỏ nhất khi chúng ta kết hợp 2 danh sách. Trong trường hợp này, nhỏ nhất là 4, vì vậy chúng tôi có thể đưa ra 4 và làm cho nó là yếu tố đầu tiên của danh sách sáp nhập của chúng tôi. Bây giờ chúng ta tiếp tục hợp nhất 3 yếu tố còn lại của danh sách đầu tiên và 4 yếu tố của danh sách thứ hai. 

Một lần nữa, chúng ta chỉ cần nhìn vào các yếu tố đầu tiên của cả hai danh sách. Các nhỏ hơn trong 2 phải là yếu tố thứ hai của danh sách sáp nhập của chúng tôi. Thời gian này, từ 8 đến 15 nhỏ nhất là 8, và vì vậy chúng tôi chèn như là phần tử thứ hai của danh sách được sắp xếp của chúng tôi. Chúng tôi có thể tiếp tục so sánh các yếu tố đầu tiên của cả hai danh sách và loại bỏ nhỏ hơn trong 2. So sánh 15 và 23, 15 là nhỏ hơn và do đó yếu tố thứ ba của chúng tôi. Bây giờ so sánh 16 và 23, 16 là nhỏ hơn. Vì vậy, đó là yếu tố thứ tư. 

Chú ý rằng 2 yếu tố đến từ cùng một danh sách trong một hàng. Đây là lý do tại sao danh sách sáp nhập có thể không chỉ thay thế các yếu tố từ 2 danh sách. So sánh 50 và 23, 23 là nhỏ hơn, do đó, chúng tôi chọn điều đó. Giữa 50 và 42, 42 là nhỏ hơn. Từ 50 và 108, 50 là nhỏ hơn. Và, cuối cùng, chúng tôi chỉ có 108, vì vậy nó phải đi vào cuối danh sách của chúng tôi. Chú ý rằng chúng tôi có một danh sách, tốt đẹp được sắp xếp. Mỗi khi chúng ta so sánh 2 yếu tố đầu tiên của 2 danh sách chúng tôi đã có thể xác định các yếu tố tiếp theo của danh sách sáp nhập. Điều này có nghĩa rằng nếu danh sách cuối cùng chứa số n, trong đó n ở đây là 8, sau đó chúng ta cần ở hầu hết các so sánh n để có được tất cả những con số này vào đúng chỗ. Một thuật toán như vậy được cho là để chạy trong thời gian tuyến tính, nhưng đừng lo lắng về điều đó ở đây. 

Sử dụng thuật toán của chúng tôi cho việc sáp nhập, chúng ta có thể thực hiện một thuật toán hợp nhất loại nhanh. Vì vậy, chúng ta hãy thiết lập lại danh sách của chúng tôi. Có 2 bước lớn trong quá trình hợp nhất loại. Thứ nhất, liên tục chia danh sách các cốc vào nửa cho đến khi chúng tôi có một loạt các danh sách với chỉ 1 chén trong họ. Đừng lo lắng nếu một danh sách có chứa một số lẻ và bạn không thể làm cho một cắt hoàn toàn sạch giữa chúng. Chỉ cần tùy tiện chọn danh sách để bao gồm thêm chén. Vì vậy, chúng ta hãy phân chia các danh sách này. Bây giờ chúng tôi có 2 danh sách. Bây giờ chúng tôi có 4 danh sách. 

Và bây giờ chúng tôi có 8 danh sách với một ly duy nhất trong mỗi danh sách. Vì vậy, đó là nó cho bước 1. Đối với bước 2, chúng tôi liên tục hợp nhất cặp danh sách bằng cách sử dụng các thuật toán hợp nhất chúng tôi đã học được trước. Sáp nhập 108 và 15, chúng tôi kết thúc với danh sách 15, 108. Sáp nhập 50 và 4, chúng tôi kết thúc với 4, 50. Sáp nhập 8 và 42, chúng tôi kết thúc với 8, 42. Và sáp nhập 23 và 16, chúng tôi kết thúc với 16, 23. Bây giờ tất cả các danh sách của chúng tôi là kích thước 2. Chú ý rằng mỗi trong 4 danh sách được sắp xếp. 

Vì vậy, chúng ta có thể bắt đầu sáp nhập các cặp danh sách một lần nữa. Sáp nhập 15 và 108 và 4 và 50 - đầu tiên lấy 4, sau đó là 15, sau đó là 50, sau đó số 108. Sáp nhập 8, 42 và 16, 23, chúng tôi lần đầu tiên mất 8, sau đó số 16, sau đó số 23, số 42. Vì vậy, bây giờ chúng tôi có 2 danh sách các kích thước 4, mỗi trong số đó được sắp xếp. Vì vậy, bây giờ chúng tôi hợp nhất 2 danh sách này. Trước tiên, lấy 4. Sau đó, chúng tôi đi 8. Sau đó, chúng tôi mất 15 và 16, sau đó 23, sau đó 42, sau đó 50, sau đó 108. Và chúng tôi đang làm. Bây giờ chúng ta có một danh sách được sắp xếp. Vì vậy, làm thế nào nhanh chóng được điều này, chính xác? Trong điều kiện kỹ thuật, hợp nhất sắp xếp là O (n log n), trong khi đó tất cả các loại bong bóng, sắp xếp chèn và sắp xếp lựa chọn là O (n ²). Trong thực tế, bạn sẽ học sớm, bạn sẽ không có thể để đến với một loại thực hiện tốt hơn so với O (n log n) trong trường hợp chung. Một lần nữa, đừng lo lắng về điều này ký hiệu O lớn nếu bạn không nhìn thấy nó. 

Chỉ biết rằng điều này có nghĩa là nếu chúng ta muốn sắp xếp một danh sách thực sự lớn bong bóng sắp xếp, sắp xếp chèn, và lựa chọn loại có khả năng có thể mất lâu hơn đáng kể hơn so với hợp nhất loại. Nó không có nghĩa rằng loại hợp nhất sẽ nhanh hơn cho tất cả các danh sách hoặc ngay cả đối với bất kỳ danh sách duy nhất theo một kích thước nhất định. Ví dụ, chèn loại có thể là các loại nhanh nhất cho tất cả các danh sách nhỏ hơn 5 yếu tố. Trong thực tế, loại hợp nhất thường là nhanh hơn cho các danh sách nhỏ như 50 phần tử. 

Tuy nhiên, tốc độ này không đến mà không có một mức giá. Không giống như các loại khác của chúng tôi, có một danh sách và sửa đổi danh sách ở vị trí cho đến khi chúng tôi nhận được một danh sách được sắp xếp, hợp nhất loại cần thêm một số không gian hợp nhất 2 danh sách với nhau. Chúng ta có thể không ngay lập tức sử dụng danh sách đang được sáp nhập để lưu trữ các danh sách sáp nhập kể từ khi chúng tôi có thể ghi đè lên các yếu tố vẫn cần phải được sáp nhập. Không gian này là một chút của một mức giá, nhưng nó thường không phải là không hợp lý. Và đó là nó cho hợp nhất loại. 

Tên tôi là Rob Bowden, và đây là CS50. [CS50.TV] Và lựa chọn sắp xếp. [Cười] Oh, có đi mà ra quá vì tôi chuyển sang làm thế nào tôi đã trình bày nó. Danh sách bên trái. Đó là một lỗi đánh máy. [Misspoke Tôi hơi say lên - [Cười] Tôi không biết những gì