选择排序算法

Question

选择排序：

​

​

我已经创建了一个选择排序算法，但有人对我说，它不是正确的选择排序。

如果不对，那是什么类型的排序？以及它与选择排序有何不同。

代码：

void selection_Sort(int arr[] , int size){
    int temp , length = size;
    for(int i = 0; i < size ; i++){
        for(int j = i + 1; j < size ; j++){
            if(arr[i] > arr[j]){
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }   
        }
    }
}

请告诉我如何改进它？

Answer 1

要将此代码转换为选择排序，您必须在内部循环中找到最小元素的索引，并在内部循环完成后在这个索引处与第一个元素交换元素。

因此，掉期的总数量不超过N(而当前的代码可以产生大约N^2/2的掉期)

Answer 2

您已经实现了气泡排序。

选择排序意味着您应该在内部循环中找到最低(或最大的)元素，然后用元素将其切换到左侧/右侧，该元素位于选择的边缘(如图片中)。

有三种类似的排序方法--选择排序、插入排序和气泡排序--您可以在这里看到它们的行为：http://i.imgur.com/fq0A8hx.gif

Answer 3

必须在外层for循环之后实现最小元素。以下是代码：

def selectionSort(arr)：

对于范围内的I(len(Arr))：

# Find the minimum element in remaining 
# unsorted array
min_idx = i
for j in range(i+1, len(arr)):
  if arr[min_idx] >  arr[j]:
    min_idx = j

# Swap the found minimum element with 
# the first element        
arr[i], arr[min_idx] = arr[min_idx], arr[i]

返回arr = 7,4,5,9,8,2,1

打印(selectionSort(Arr))

选择排序是如何工作的？

1. 从第一个元素开始，我们搜索数组中最小的元素，并将其替换为位于第一个位置的元素。
2. 然后，我们继续到第二个位置，寻找子数组中存在的最小元素，从索引1开始，直到最后一个索引。
3. 我们在原始数组中的第二个位置替换元素，或者说在子数组的第一个位置用第二个最小的元素替换。4.这是重复的，直到数组被完全排序。