DOUG LLOYD: Vì vậy, trong CS50 chúng tôi đã học về một loạt các phân loại và tìm kiếm các thuật toán. Và đôi khi nó có thể được một chút khó khăn để giữ theo dõi của những thuật toán làm gì. Chúng tôi đã thực sự chỉ sưa bề mặt quá, có rất nhiều tìm kiếm khác và phân loại các thuật toán. Vì vậy, trong video này chúng ta hãy chỉ mất một vài phút để cố gắng và chưng cất mỗi thuật toán xuống đến các yếu tố cốt lõi của nó vì vậy bạn có thể nhớ nhất thông tin quan trọng về họ và có thể trình bày rõ sự khác biệt, nếu cần thiết. 

Việc đầu tiên là sắp xếp chọn. Ý tưởng cơ bản đằng sau sắp xếp chọn đang tìm các phần tử nhỏ nhất không được phân loại trong một mảng và trao đổi nó với yếu tố không được phân loại đầu tiên của mảng đó. Chúng tôi cho rằng, trường hợp xấu nhất chạy thời điểm đó đã được n bình phương. Và nếu bạn muốn gọi lại lý do tại sao, mất một nhìn vào video sắp xếp chọn. Các trường hợp tốt nhất thời gian chạy cũng được n bình phương. 

Bubble sort, ý tưởng đằng sau đó một là để trao đổi cặp liền kề. Vì vậy, đó là chìa khóa giúp bạn nhớ sự khác biệt ở đây. Sắp xếp chọn là, cho đến nay, tìm thấy những bong bóng smallest-- loại là trao đổi cặp liền kề. Chúng tôi trao đổi cặp liền kề của các nguyên tố nếu họ là ra lệnh, mà hiệu quả Bong bóng yếu tố lớn hơn bên phải, và đồng thời nó cũng bắt đầu để di chuyển các phần tử nhỏ hơn bên trái. Các trường hợp xấu nhất trường hợp thời gian chạy các bong bóng sắp xếp được n bình phương. Các trường hợp tốt nhất thời gian chạy các bong bóng sắp xếp là n. Bởi vì trong tình huống đó chúng tôi không actually-- chúng ta có thể không cần đến thực hiện bất kỳ giao dịch hoán đổi ở tất cả. Chúng tôi chỉ phải làm một vượt qua trên tất cả các yếu tố n. 

Trong sắp xếp chèn, các Ý tưởng cơ bản ở đây đang dịch chuyển. Đó là các từ khóa cho các sắp xếp chèn. Chúng ta sẽ bước qua một lần các mảng từ trái sang phải. Và như chúng tôi, chúng tôi sẽ thay đổi các yếu tố chúng ta đã thấy để nhường chỗ cho những cái nhỏ hơn cần để phù hợp với một nơi nào đó trở lại trong đó phần được sắp xếp. Vì vậy, chúng tôi xây dựng các mảng được sắp xếp một yếu tố tại một thời gian, trái sang phải, và chúng tôi thay đổi mọi thứ để làm cho căn phòng. Thời gian chạy trường hợp xấu nhất của sắp xếp chèn được n bình phương. Các trường hợp tốt nhất thời gian chạy là n. 

Merge sort-- từ khóa ở đây được phân chia và hợp nhất. Chúng tôi chia các mảng đầy đủ, cho dù đó là sáu yếu tố, tám yếu tố, 10.000 elements-- chúng tôi chia nó xuống một nửa, một nửa, một nửa, cho đến khi chúng tôi có theo mảng của n một mảng phần tử. Một tập hợp của n một mảng phần tử. Vì vậy, chúng ta bắt đầu với một 1.000 phần tử mảng, và chúng tôi nhận được đến điểm mà chúng ta có 1.000 mảng một phần tử. Sau đó, chúng ta bắt đầu kết hợp những mảng phụ trở lại với nhau theo thứ tự đúng. Vì vậy, chúng tôi mất hai mảng một phần tử và tạo ra một mảng hai yếu tố. Chúng tôi có hai mảng hai phần tử và tạo ra một mảng bốn phần tử và như vậy và như vậy cho đến khi chúng tôi đã một lần nữa xây dựng lại một mảng n phần tử. 

Thời gian chạy trường hợp xấu nhất của hợp nhất phân loại là n lần log n. Chúng tôi có n phần tử, nhưng quá trình tái hợp này mất log n bước để có được sao để một mảng đầy đủ. Các trường hợp tốt nhất thời gian chạy cũng là n log n bởi vì quá trình này không thực sự quan tâm cho dù mảng là sắp xếp hay không để bắt đầu. Quá trình này là giống nhau, có không có cách nào để mọi thứ ngắn mạch. Vì vậy, n log n trong trường hợp xấu nhất, n log n trong trường hợp tốt nhất. 

Chúng tôi nói về hai tìm kiếm các thuật toán. Vì vậy, tìm kiếm tuyến tính là khoảng iterating. Chúng tôi tiến hành trên mảng một lần, từ trái sang phải, cố gắng để tìm số mà chúng ta đang tìm kiếm. Lần trường hợp xấu nhất chạy là O lớn của n. Nó có thể đưa chúng ta lặp qua mọi yếu tố duy nhất để tìm các phần tử chúng tôi đang tìm kiếm cho, hoặc là ở vị trí cuối cùng, hoặc không gì cả. Nhưng chúng tôi không thể xác nhận rằng cho đến khi chúng tôi đã xem xét tất cả mọi thứ. m là trường hợp tốt nhất, chúng tôi tìm thấy ngay lập tức. Thời gian chạy nhất trường hợp của tìm kiếm tuyến tính là omega của 1. 

Cuối cùng, có tìm kiếm nhị phân, trong đó yêu cầu các loại mảng. Hãy nhớ rằng một rất xem xét quan trọng khi làm việc với tìm kiếm nhị phân. Đó là một điều kiện tiên quyết để sử dụng it-- mảng mà bạn đang tìm kiếm thông qua phải được sắp xếp. Nếu không, các từ khóa là phân chia và chinh phục. Chia mảng thành một nửa và loại bỏ một nửa của các yếu tố mỗi khi bạn tiến hành thông qua. Vì sự ngăn cách và chinh phục và tách thứ trong nửa phương pháp tiếp cận, trường hợp xấu nhất thời gian chạy tìm kiếm nhị phân là log n, đó là đáng kể tốt hơn so với n tìm kiếm tuyến tính của. Các trường hợp tốt nhất chạy thời gian vẫn là một. 

Chúng tôi có thể tìm thấy nó ngay lập tức Lần đầu tiên chúng tôi làm cho một bộ phận, nhưng, một lần nữa, hãy nhớ rằng mặc dù tìm kiếm nhị phân là tốt hơn đáng kể so với tìm kiếm tuyến tính nhờ được log n so n, bạn có thể phải đi qua công việc phân loại mảng đầu tiên của bạn, mà có thể làm cho nó kém hiệu quả phụ thuộc vào kích thước của iterating sắp xếp. 

Tôi Doug Lloyd, đây là CS50.