[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.