排序算法python实现
The Selection Sort Algorithm sorts the elements of an array. In this article, we shall look at the core algorithm and how we can implement it inPython, Java, C++, and C.
选择排序算法对数组的元素进行排序。 在本文中，我们将研究核心算法以及如何在Python，Java，C ++和C中实现它。
核心算法 (The Core Algorithm)
The Selection Sort Algorithm is very simple.
选择排序算法非常简单。
Seti = 0initially, since that is the starting point.首先设置i = 0，因为那是起点。 Find the minimum element of the unsorted sub-array[i..end]查找未排序子数组[i..end]的最小元素 We then swap this with the element at the positiona[i].然后，我们将其与a [i]位置的元素交换。 We then incrementi, and repeat the above steps untili == n然后，我们增加i，并重复上述步骤，直到i == n
In pseudo-code, we can represent it like this:
用伪代码，我们可以这样表示：
PROCEDURE SELECTION_SORT(arr):i = -1while i < size(arr):idx = find_min(arr[i+1..size(arr)])swap(i, idx)i++return arr
显示算法的工作 (Showing the working of the Algorithm)
Let’s now understand how this algorithm works, by applying it on an array!
现在，通过将其应用到数组上来了解该算法的工作原理！
Let’s consider the below array.
让我们考虑下面的数组。
Initially, the unsorted array looks like this:
最初，未排序的数组如下所示：
In the first iteration, we find the minimum element from the remaining array (from{12, 7, 6, 16, 4}), which is 4. We now swaparr[i]with4.
在第一次迭代中，我们从其余数组（来自{12，7，6，6，16，4}）中找到了最小元素4。现在，我们将arr [i]与4交换。
In the next iteration, we find the minimum element from the subarray{7, 6, 16, 12}, which is 6. So let’s swap 6 and 7.
在下一次迭代中，我们从子数组{7，6，16，12}中找到最小元素，即6。因此，让我们交换6和7。
Now, we move to the next element of the updated array and again do the same steps.
现在，我们移至更新数组的下一个元素，并再次执行相同的步骤。
In the previous iteration, there was no change, since 7 is the minimum element in the remaining sub-array.
在上一个迭代中，没有变化，因为7是其余子数组中的最小元素。
Now finally, we reach the end of the array, and now the complete array is sorted!
现在终于到了数组的末尾，现在已经对整个数组进行了排序！
Let’s apply the Selection Sort Algorithm to sort the above array in Python, C++, and C.
让我们应用选择排序算法对上述数组进行Python，C ++和C排序。
选择在Python中排序 (Selection Sort in Python)
The below snippet shows the working of the algorithm using Python.
以下代码段显示了使用Python的算法的工作方式。
def find_min(arr, start, end):minimum = arr[start]min_idx = startfor idx in range(start, end):if arr[idx] < minimum:minimum = arr[idx]min_idx = idxreturn min_idxdef selection_sort(arr):i = 0arr_size = len(arr)while i < arr_size:# Find minimum of remaining unsorted subarraymin_idx = find_min(arr, i, arr_size)# Swap with arr[i]arr[min_idx], arr[i] = arr[i], arr[min_idx]i += 1return arra = [12, 7, 6, 16, 4]print(selection_sort(a))
Output
输出量
[4, 6, 7, 12, 16]
选择Java排序 (Selection Sort in Java)
public class SelectionSort {int find_min(int arr[], int start, int end) {int min_idx = start;int minimum = arr[start];for (int i=start; i<end; i++) {if (arr[i] < minimum) {min_idx = i;minimum = arr[i];}}return min_idx;}void selection_sort(int arr[], int arr_len) {// Selection Sort on an Array// Pass by reference int start = 0;int min_idx;while (start < arr_len) {min_idx = find_min(arr, start, arr_len);// Swap arr[start] and arr[min_idx]int temp = arr[start];arr[start] = arr[min_idx];arr[min_idx] = temp;start++;}}public static void main(String[] args) {int arr[] = {12, 7, 6, 16, 4};SelectionSort sel_sort = new SelectionSort();sel_sort.selection_sort(arr, 5);System.out.println("Array after sorting:");for (int i=0; i<5; i++) {System.out.printf("%d ", arr[i]);}System.out.println();}}
Save the above code as SelectionSort.java.
将上面的代码另存为SelectionSort.java。
Output
输出量
Array after sorting:4 6 7 12 16
选择在C ++中排序 (Selection Sort in C++)
Here is another implementation of the algorithm in C++
这是C ++中算法的另一种实现
#include <iostream>using namespace std;int find_min(int arr[], int start, int end) {int min_idx = start;int minimum = arr[start];for (int i=start; i<end; i++) {if (arr[i] < minimum) {min_idx = i;minimum = arr[i];}}return min_idx;}void selection_sort(int arr[], int arr_len) {// Selection Sort on an Array// Pass by reference int start = 0;int min_idx;while (start < arr_len) {min_idx = find_min(arr, start, arr_len);// Swap arr[start] and arr[min_idx]int temp = arr[start];arr[start] = arr[min_idx];arr[min_idx] = temp;start++;}}int main() {int arr[] = {12, 7, 6, 16, 4};selection_sort(arr, 5);cout << "Array after sorting:\n";for (int i=0; i<5; i++) {cout << arr[i] << " ";}cout << endl;return 0;}
Output
输出量
Array after sorting:4 6 7 12 16
选择按C排序 (Selection Sort in C)
#include <stdio.h>int find_min(int arr[], int start, int end) {int min_idx = start;int minimum = arr[start];for (int i=start; i<end; i++) {if (arr[i] < minimum) {min_idx = i;minimum = arr[i];}}return min_idx;}void selection_sort(int arr[], int arr_len) {// Selection Sort on an Arrayint start = 0;int min_idx;while (start < arr_len) {min_idx = find_min(arr, start, arr_len);// Swap arr[start] and arr[min_idx]int temp = arr[start];arr[start] = arr[min_idx];arr[min_idx] = temp;start++;}}int main() {int arr[] = {12, 7, 6, 16, 4};selection_sort(arr, 5);printf("Array after sorting:\n");for (int i=0; i<5; i++) {printf("%d ", arr[i]);}printf("\n");return 0;}
Output
输出量
Array after sorting:4 6 7 12 16
时间复杂度 (Time Complexity)
Since the algorithm performs 2 loops iterating over the array, it has a time complexity ofO(n^2).
由于该算法对数组执行2个循环，因此其时间复杂度为O（n ^ 2）。
If that’s not clear, the total number of operations performed, if the array hasnelements is:
如果不清楚，则在数组具有n元素的情况下执行的操作总数为：
(n + (n-1) + (n-2) + (n-3) + … + 1) = n * (n + 1)/2 = O(n^2)
（n +（n-1）+（n-2）+（n-3）+…+ 1）= n *（n + 1）/ 2 = O（n ^ 2）
So, while this is not a very good sorting algorithm, it is very easy to implement, and can be used to sort arrays with low number of elements.
因此，尽管这不是一个很好的排序算法，但它很容易实现，可用于对元素数量较少的数组进行排序。
必须阅读 (Must Reads)
Bubble Sort Algorithm气泡排序算法 Merge Sort Algorithm with Java, Python, and C implementation合并排序算法与Java，Python和C实现参考资料 (References)
Wikipedia Article on Selection Sort维基百科有关选择排序的文章翻译自: /36355/selection-sort-algorithm
排序算法python实现
