插入排序与选择排序 [英] Insertion Sort vs. Selection Sort

问题描述

我试图理解插入排序和选择排序之间的区别。

I am trying to understand the differences between Insertion Sort and Selection Sort.

它们似乎都具有两个组成部分：未排序列表和排序列表。他们似乎都从未排序列表中选取一个元素，并将其放入适当位置的已排序列表中。我已经看到一些网站/书籍说选择排序是通过一次交换一个来实现的，而插入排序只是找到正确的位置并插入它。但是，我看过其他文章说了一些话，说插入排序也互换了。因此，我感到困惑。

They both seem to have two components: an unsorted list and a sorted list. They both seem to take one element from the unsorted list and put it into the sorted list at the proper place. I have seen some sites/books saying that selection sort does this by swapping one at a time while insertion sort simply finds the right spot and inserts it. However, I have seen other articles say something, saying that insertion sort also swaps. Consequently, I am confused. Is there any canonical source?

推荐答案

选择排序：

给出列表，获取当前元素并将其与当前元素右侧的最小元素交换。

Selection Sort:

Given a list, take the current element and exchange it with the smallest element on the right hand side of the current element.

给出一个列表，获取当前元素并将其插入到列表的适当位置，并在每次插入时调整列表。这类似于在纸牌游戏中排列纸牌。

Given a list, take the current element and insert it at the appropriate position of the list, adjusting the list every time you insert. It is similar to arranging the cards in a Card game.

时间复杂度选择排序始终为 n（n-1）/ 2 ，而插入排序的时间复杂度更高，因为其最坏情况下的复杂度为 n（n-1 ）/ 2 。通常情况下，与 n（n-1）/ 2 进行比较或得出的结果较少。

Time Complexity of selection sort is always n(n - 1)/2, whereas insertion sort has better time complexity as its worst case complexity is n(n - 1)/2. Generally it will take lesser or equal comparisons then n(n - 1)/2.

来源： http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

这篇关于插入排序与选择排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！