[Powered by Google Translate] TOMMY: Chúng ta hãy xem xét lựa chọn loại, một thuật toán dành một danh sách các số và phân loại chúng. Một thuật toán, hãy nhớ, chỉ đơn giản là một bước-by-step thủ tục để hoàn thành một nhiệm vụ. Ý tưởng cơ bản đằng sau loại lựa chọn là để phân chia danh sách của chúng tôi thành hai phần - một phần được sắp xếp và một phần được phân loại. Tại mỗi bước của thuật toán, một số được chuyển từ phân loại phần phần được sắp xếp cho đến khi cuối cùng các toàn bộ danh sách được sắp xếp. Vì vậy, đây là danh sách sáu con số - 23, 42, 4, 16, 8, và 15. Ngay bây giờ được coi là toàn bộ danh sách được phân loại. Mặc dù một số giống như 16 có thể đã được chính xác của nó vị trí, thuật toán của chúng tôi không có cách nào biết rằng cho đến khi toàn bộ danh sách được sắp xếp. Vì vậy, chúng tôi sẽ xem xét tất cả các số được được phân loại cho đến khi chúng tôi sắp xếp nó chính mình. Chúng tôi biết rằng chúng tôi muốn danh sách có thứ tự tăng dần. Vì vậy, chúng tôi sẽ muốn xây dựng phần sắp xếp danh sách của chúng tôi từ trái sang phải, nhỏ đến lớn. Để làm được điều đó, chúng tôi sẽ cần phải tìm thấy các yếu tố tối thiểu được phân loại và đặt nó ở cuối của phần được sắp xếp. Kể từ khi danh sách này không được sắp xếp, cách duy nhất để làm điều đó là để nhìn vào mỗi phần tử trong phần phân loại, ghi nhớ yếu tố là thấp nhất và so sánh mỗi yếu tố đó. Vì vậy, chúng tôi sẽ xem xét đầu tiên vào 23. Đây là yếu tố đầu tiên mà chúng tôi đã nhìn thấy, vì vậy chúng tôi sẽ nhớ nó như là tối thiểu. Tiếp theo chúng ta sẽ xem xét ở mức 42. 42 là lớn hơn 23, do đó, 23 là tối thiểu. Tiếp theo là 4 mà là ít hơn 23, vì vậy chúng tôi sẽ nhớ 4 như là tối thiểu mới. Tiếp theo là 16 mà là lớn hơn 4, 4 vẫn là tối thiểu. 8 lớn hơn 4, và 15 là lớn hơn 4, do đó, 4 phải được yếu tố được phân loại nhỏ nhất. Vì vậy, mặc dù là con người, chúng tôi ngay lập tức có thể thấy, có 4 là các yếu tố tối thiểu, thuật toán của chúng tôi cần phải xem xét tất cả các yếu tố được phân loại, ngay cả sau khi chúng tôi đã tìm thấy 4 - tối thiểu yếu tố. Vì vậy, bây giờ mà chúng tôi đã tìm thấy các yếu tố tối thiểu, 4, chúng tôi sẽ muốn để di chuyển nó vào phần sắp xếp danh sách. Vì đây là bước đầu tiên, điều này có nghĩa là chúng tôi muốn đặt 4 tại đầu của danh sách. Ngay bây giờ 23 là lúc bắt đầu của danh sách, do đó, chúng ta hãy trao đổi 4 và số 23. Vì vậy, bây giờ danh sách của chúng tôi trông như thế này. Chúng ta biết rằng 4 phải được ở vị trí cuối cùng của nó, bởi vì nó là cả hai yếu tố nhỏ nhất và yếu tố đầu của danh sách. Vì vậy, điều này có nghĩa rằng chúng ta không bao giờ cần để di chuyển nó một lần nữa. Vì vậy, hãy lặp lại quá trình này để thêm một yếu tố để sắp xếp phần của danh sách. Chúng ta biết rằng chúng ta không cần phải nhìn vào 4, bởi vì nó đã được sắp xếp. Vì vậy, chúng ta có thể bắt đầu từ số 42, mà chúng ta sẽ nhớ tối thiểu yếu tố. Vì vậy, tiếp theo chúng ta sẽ nhìn vào 23 ít hơn 42, vì vậy chúng tôi hãy nhớ 23 là mức tối thiểu mới. Tiếp theo, chúng ta thấy số 16 là ít hơn 23, do đó, 16 là tối thiểu mới. Bây giờ chúng ta nhìn vào 8 là ít hơn 16, vì vậy 8 là tối thiểu mới. Và cuối cùng 8 là ít hơn 15, vì vậy chúng tôi biết rằng 8 là một tối thiểu phân loại yếu tố. Vì vậy, điều đó có nghĩa là chúng ta nên gắn thêm 8 để sắp xếp phần của danh sách. Ngay bây giờ 4 là yếu tố duy nhất được sắp xếp, vì vậy chúng tôi muốn đặt sau 8 cho 4. Kể từ khi 42 là yếu tố đầu tiên trong phần phân loại của danh sách, chúng tôi sẽ muốn trao đổi 42 và 8. Vì vậy, bây giờ danh sách của chúng tôi trông như thế này. 4 và 8 đại diện cho phần sắp xếp danh sách, và số còn lại đại diện cho các phân loại phần của danh sách. Vì vậy, chúng ta hãy tiếp tục lặp đi lặp lại khác. Chúng tôi bắt đầu với 23 thời gian này, vì chúng ta không cần phải nhìn vào 4 và 8 nữa bởi vì họ đã đã được sắp xếp. 16 là ít hơn 23, vì vậy chúng tôi sẽ nhớ 16 là tối thiểu mới. 16 là ít hơn 42, nhưng 15 là ít hơn 16, 15 phải tối thiểu được phân loại thành phần. Vì vậy, bây giờ chúng tôi muốn trao đổi 15 và 23 đến cung cấp cho chúng tôi danh sách này. Phần sắp xếp danh sách bao gồm 4, 8 và 15, và những yếu tố này vẫn còn được phân loại. Nhưng nó chỉ như vậy sẽ xảy ra rằng yếu tố được phân loại tiếp theo, 16, đã được sắp xếp. Tuy nhiên, không có cách nào cho các thuật toán của chúng tôi biết rằng 16 là đã có trong vị trí chính xác của nó, do đó, chúng ta vẫn cần lặp lại chính xác cùng một quá trình. Vì vậy, chúng ta thấy rằng 16 là ít hơn 42, và 16 là ít hơn 23, vì vậy 16 phải là yếu tố tối thiểu. Nó không thể trao đổi yếu tố này với chính nó, vì vậy chúng tôi có thể chỉ đơn giản là để nó ở vị trí này. Vì vậy, chúng ta cần phải vượt qua thêm một thuật toán của chúng tôi. 42 là lớn hơn 23, vì vậy 23 phải là tối thiểu được phân loại yếu tố. Sau khi chúng tôi trao đổi số 23 và số 42, chúng tôi kết thúc với cuối cùng của chúng sắp xếp danh sách - 4, 8, 15, 16, 23, 42. Chúng tôi biết 42 phải được địa điểm chính xác vì đó là chỉ có yếu tố còn lại, và đó là lựa chọn loại. Bây giờ chúng ta chính thức hóa thuật toán của chúng tôi với một số giả. Trên một dòng, chúng ta có thể thấy rằng chúng ta cần phải tích hợp trên mọi phần tử của danh sách. Ngoại trừ yếu tố cuối cùng, vì các yếu tố 1 danh sách đã được sắp xếp. On line hai, chúng tôi xem xét các yếu tố đầu tiên của phân loại phần của danh sách để là tối thiểu, như chúng ta đã làm với chúng tôi Ví dụ, vì vậy chúng tôi có một cái gì đó để so sánh với. Dòng 3 bắt đầu một vòng lặp thứ hai mà chúng ta lặp qua mỗi phần tử được phân loại. Chúng ta biết rằng sau khi tôi lặp đi lặp lại, phần sắp xếp danh sách của chúng tôi phải có i yếu tố trong nó kể từ khi mỗi bước các loại một phần tử. Vì vậy, các phân loại yếu tố đầu tiên phải được ở vị trí của tôi cộng với 1. On line 4, chúng ta so sánh các yếu tố hiện ở mức tối thiểu yếu tố mà chúng tôi đã thấy cho đến nay. Nếu phần tử hiện tại nhỏ hơn mức tối thiểu phần tử, sau đó chúng ta nhớ đến yếu tố mới hiện nay tối thiểu trên dòng 5. Cuối cùng, trên các tuyến đường sáu và bảy, chúng tôi trao đổi tối thiểu phần tử với các yếu tố được phân loại đầu tiên, do đó thêm nó vào phần sắp xếp danh sách. Một khi chúng ta có một thuật toán, một câu hỏi quan trọng để hỏi mình là lập trình viên được bao lâu đã làm điều đó? Đầu tiên chúng ta sẽ đặt câu hỏi làm thế nào lâu cho điều này thuật toán để chạy trong trường hợp xấu nhất? Nhớ lại chúng tôi đại diện cho điều này đang chạy thời gian bằng các ký hiệu O lớn. Để xác định các yếu tố tối thiểu được phân loại, về cơ bản đã có để so sánh từng phần tử trong danh sách để mọi phần tử khác trong danh sách. Bằng trực giác, âm thanh này giống như một O hoạt động bình n. Nhìn giả của chúng tôi, chúng tôi cũng có một vòng lặp lồng vào bên trong một vòng lặp, mà thực sự âm thanh như một O hoạt động bình n. Tuy nhiên, hãy nhớ rằng chúng tôi không cần phải xem qua toàn bộ danh sách khi xác định các yếu tố tối thiểu được phân loại? Một khi chúng ta biết rằng 4 đã được sắp xếp, ví dụ, chúng tôi đã không cần phải nhìn vào nó một lần nữa. Vì vậy, thực hiện điều này thấp hơn thời gian chạy? Đối với danh sách của chúng tôi có chiều dài 6, chúng tôi cần thiết để làm cho 5 so sánh các yếu tố đầu tiên, bốn so sánh cho Yếu tố thứ hai, và như vậy. Điều đó có nghĩa là tổng số của các bước là tổng của các số nguyên từ 1 đến chiều dài của danh sách trừ đi 1. Chúng tôi có thể đại diện cho điều này với một tổng kết. Chúng tôi sẽ không đi vào summations ở đây. Nhưng nó quay ra rằng tổng kết này là bằng n lần n trừ đi 1 trên 2. Hoặc tương đương, n bình phương hơn 2 trừ đi n hơn 2. Khi nói về thời gian chạy tiệm cận, điều này hạn bình n sẽ chi phối hạn n. Vì vậy, lựa chọn loại O n bình phương. Nhớ lại rằng trong ví dụ của chúng tôi, lựa chọn loại vẫn cần thiết để kiểm tra xem một số đã được đã được sắp xếp cần thiết để được di chuyển. Vì vậy, đó có nghĩa là nếu chúng ta chạy lựa chọn Sắp xếp trên một đã sắp xếp danh sách, nó sẽ yêu cầu số lượng tương tự các bước như sẽ khi chạy trên một danh sách hoàn toàn được phân loại. Vì vậy, lựa chọn loại có hiệu suất trường hợp tốt nhất của n bình phương, mà chúng tôi đại diện với omega n bình phương. Và đó là nó để sắp xếp lựa chọn. Chỉ là một trong rất nhiều các thuật toán chúng ta có thể sử dụng để sắp xếp một danh sách. Tên tôi là Tommy, và điều này là CS50.