Name: 0.3 數據結構與算法：選擇排序 (0.3 Data Structures & Algorithms: Selection Sort)
Uploaded: 2025-01-06T13:33:29.000Z
Duration: 7 min 5 s

Okay, so let's talk about this idea of sorting integers.

好了，讓我們來談談整數排序的概念。

So, I'm going to look at a specific example problem.

下面，我將舉一個具體的例子來說明這個問題。

So, we're going to look at sorting a couple of different numbers, and then we'll kind of build off of this idea and look at sorting more data.

是以，我們將對幾個不同的數字進行排序，然後在此基礎上對更多數據進行排序。

Okay, so for our simple problem, we've got the numbers 89, 3, and 1.

好了，對於這個簡單的問題，我們有 89、3 和 1 三個數字。

So we could come up with some sort of an algorithm to try and sort these.

是以，我們可以想出某種算法來嘗試對這些數據進行排序。

So, one of the simplest things we could do is we could just try all possible combinations until we find one that's sorted.

是以，我們可以做的最簡單的事情之一，就是嘗試所有可能的組合，直到找到一個排序正確的組合。

So basically, we could go through every possible ordering of these until we identify one that's clearly sorted.

是以，基本上，我們可以對所有可能的排序進行排查，直到找出一個排序明確的排序。

So I could start with whatever order I was initially given, and then I could swap two elements.

是以，我可以從最初給我的任何順序開始，然後交換兩個元素。

然後，也許我會把 3 號車廂移到前面。

And eventually, we'll stumble across the perfectly sorted order.

最終，我們會偶然發現完美的排序順序。

Of course, obviously, this seems very, very, very inefficient.

當然，很顯然，這似乎非常、非常、非常低效。

With just a simple problem like this, it was probably obvious to you what the order should have been when you just first glanced at it.

對於這樣一個簡單的問題，當你第一眼看到它的時候，你可能就會明白它的順序應該是怎樣的。

The human brain is incredible at pattern matching.

人腦的模式匹配能力令人難以置信。

But for the rest of our discussion here, we'll want to think very, very concretely and think about each individual step so we could translate it into code rather than relying on our instantaneous intuition about what the problem should be.

但是，在接下來的討論中，我們要非常、非常具體地思考每一個步驟，以便將其轉化為代碼，而不是依靠我們對問題的直覺。

Okay, our first sorting algorithm seems a little bit cumbersome.

好吧，我們的第一種排序算法似乎有點麻煩。

So let's add in some more data here, and we'll talk about a second type of sorting algorithm.

是以，讓我們在這裡添加更多數據，我們將討論第二種排序算法。

So now we're going to take a look at what's called a selection sort.

現在我們來看看所謂的選擇排序。

So a selection sort is called a selection sort because a lot of the work takes place in selecting a value.

是以，選擇排序之所以被稱為選擇排序，是因為很多工作都是在選擇一個值。

So the way a selection sort works is it's going to try and select the value that belongs in our next available position.

是以，選擇排序的工作方式是嘗試選擇屬於下一個可用位置的值。

So by that, I mean we'll start off trying to find the value that belongs in the very beginning of the array.

是以，我的意思是，我們將首先嚐試找到屬於數組最開頭的值。

Once we've found the value that belongs in the beginning of the array, we'll move on and we'll try and find the value that belongs in the second position of the array.

找到屬於數組開頭的值後，我們將繼續嘗試找到屬於數組第二個位置的值。

After we've done that, we'll try and find the value that belongs in the third position of the array.

完成上述操作後，我們將嘗試查找屬於數組第三個位置的值。

So let's go back and talk about that first step.

We want to know what belongs in the first position of the array.

我們想知道數組的第一個位置是什麼。

The thing that belongs in the very first position will end up being the smallest number overall, the minimum value.

屬於第一個位置的東西最終將是最小的數字，即最小值。

So let's think about the steps that a computer program is going to have to go through in order to find the minimum value.

是以，讓我們來想想計算機程序要找到最小值需要經過哪些步驟。

Now, when we see this visually, our brain is so good that it just instantly looks at the values and identifies the first one.

現在，當我們直觀地看到這一點時，我們的大腦非常靈敏，會立即查看數值並識別出第一個數值。

But remember that a computer program isn't visual.

但請記住，計算機程序並不是可視化的。

It's looking at an individual box and then somehow comparing it and contrasting it with others.

它是在觀察一個單獨的盒子，然後以某種方式將其與其他盒子進行比較和對比。

So when our program first looks at this box, it has nothing to compare it to.

是以，當我們的程序第一次看到這個方框時，它沒有任何東西可以與之比較。

That might be the thing that belongs in the beginning of this array.

這可能是屬於這個陣列開頭的東西。

So I'm going to use my pencil here to keep track of which item I'm evaluating.

是以，我要用鉛筆記錄我正在評估的項目。

And I'm going to indicate the one that seems like my candidate for the best possible value by slightly offsetting it.

我將通過略微抵消的方式，指出我認為最有價值的候選方案。

So when we get to 34, that's no better than 2.

是以，當我們達到 34 時，這並不比 2 好。

And I'm going to continue on, even though we know visually that 1 is our best value.

儘管我們都知道 1 是我們的最佳價值，但我還是要繼續下去。

Remember, the computer is processing step by step.

記住，計算機是一步一步處理的。

There could be a negative number out here or a 0.

So I get to 3, no better than 1. 89, no better than 1. 13, no better than 1. 55, no better than 1.

所以我到了 3，不比 1. 89 好，不比 1. 13 好，不比 1. 55 好，不比 1.

So I've gone all the way through my data and I've found the minimum value overall.

是以，我通過數據找到了最小值。

And I know that that belongs in the very first position of my array.

我知道，這屬於我的陣列的第一個位置。

所以我要把這兩個人對調一下。

Not only that, I'm going to kind of set this off to the side and kind of ignore it.

不僅如此，我還打算把它放在一邊，視而不見。

I know that that belongs in the very first position of my array.

我知道，這屬於我的數組的第一個位置。

Oh, at this point, I can repeat the process starting from the second position.

哦，此時，我可以從第二個位置開始重複這個過程。

So I've already removed the overall minimum value and kind of set it off to the side.

是以，我已經刪除了總的最小值，並把它放在一邊。

Now if I process the remainder of my array in the exact same way and find the minimum value of what's remaining, that's going to be my second minimum value and belong in the second position of the array.

現在，如果我用完全相同的方法處理數組的剩餘部分，並找出剩餘部分的最小值，這將是我的第二個最小值，屬於數組的第二個位置。

So let's go through this exercise a few more times. 34 seems pretty good when I first look at it, but then I move on to 2 and that's much better. 3 is no better than 2. 89 is no better than 2. 13 is no better than 2. 55 is no better than 2.

那麼，讓我們多做幾次這樣的練習。當我第一次看到 34 時，它似乎很不錯，但我接著看 2，它就好得多了。3 不比 2 好，89 不比 2 好，13 不比 2 好，55 不比 2 好。

So we get to the end and now we know that 2 belongs in that second position.

現在我們知道，2 屬於第二個位置。

And again, I'm leaving a little gap here so I can kind of tell where my unsorted data begins and where my sorted data is at.

同樣，我在這裡留了一點空隙，這樣我就能知道未排序數據從哪裡開始，排序數據又在哪裡。

Now I'm at the third position of the array.

I've removed the minimum overall and the second minimum.

我刪除了最低總分和第二最低分。

So let's go through the process again. 34 seems pretty good until I see 3. 89, 13, and 55.

讓我們再來一次。34 看起來不錯，直到我看到 3、89、13 和 55。

Now I've got fully sorted data for 3 items and then I've got my unsorted set.

現在我得到了 3 個項目的完全排序數據，然後是未排序的數據集。

That's okay. 89, oh, 13 is better than my 34. 55 is no better.

沒關係89，哦，13比我的34好。55 也比不上

Swap my minimum value with my first value.

將我的最小值與第一個值對調。

Repeat the process. 89 seems pretty good until I happen to stumble across the 34. 55 is no better than 34.

重複這個過程。89 看起來很不錯，直到我偶然發現了 34。55 不比 34 好。

I have my sorted set and my unsorted set. 89 seems pretty good until I see 55.

我有我的分類集和我的未分類集。在我看到 55 之前，89 看起來還不錯。

現在我的排序表上已經有 55 個了。

My unsorted set only has one number so we'll just go ahead and add that on.

我的未排序集合只有一個數字，所以我們就把它加上去。

At this point I'm done and it's completely sorted.

至此，我的工作完成了，問題也徹底解決了。

So remember that I was doing the bulk of the work in this process of selecting the next item, which is why this is called selection sort.

請記住，在選擇下一個項目的過程中，大部分工作都是由我來完成的，這就是為什麼我們稱之為選擇排序。

Okay, of course, this process isn't limited to just numbers.

當然，這個過程並不侷限於數字。

We could also use this idea of selection sort with words or anything else that we can construct a total ordering out of.

我們也可以把這種選擇排序的想法用在單詞或其他任何我們可以構建總排序的東西上。

So these are the surnames of some relatively famous computer scientists.

這些就是一些比較著名的計算機科學家的姓氏。

So starting with Hopper seems like a good candidate for a first overall.

是以，從霍普開始，似乎是總成績第一的好人選。

Turing's no earlier in the alphabet than Hopper.

圖靈在字母表中的位置並不比霍普早。

Then we get to Corman, and Corman doesn't come any earlier than Allen, so Allen goes to the front.

然後我們到了科曼，科曼沒有比艾倫來得更早，所以艾倫走在最前面。

Hopper gets swapped back to where Allen was just at.

霍普被換回艾倫剛才所在的位置。

Turing seems pretty good until we see Rivest.

在看到 Rivest 之前，圖靈似乎還不錯。

 Okay, anyway, so the basic idea is that we can even do this sorting process with other types of data, not just with integers, so it does generalize.

好了，不管怎麼說，我們的基本想法是，我們甚至可以對其他類型的數據進行排序，而不僅僅是整數，所以它確實具有通用性。