选择排序法 - Selection Sort

简单记录-bobo老师的玩转算法系列–玩转算法 -排序基础

排序算法

O(n^2)的排序算法

为什么要学习O(n^2)的排序算法？

为什么要学习O(n^2)的排序算法？

• 基础

• 基础

• 编码简单，易于实现，是一些简单情景的首选

• 在一些特殊情况下，简单的排序算法更有效

• 简单的排序算法思想衍生出复杂的排序算法

• 作为子过程，改进更复杂的排序算法

Selection Sort 选择排序

选择排序算法思想

选择排序算法思想：

Selection Sort 选择排序

选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。选择是找出最小的元素。
选择排序就是从序列中找到最小的元素，和第一个位置的元素互换。
然后从第二个位置开始，剩下的元素中找到最小的元素，和第二个位置的元素互换。
…

or (每一趟在 n- i + 1（i = 1,2,3…,n-1）个元素中选取关键字最小的元素与第 i 个元素交换，并作为有序序列中的第 i 个元素。)

例如：{10,9,8,7,6,5,4,3,2,1}

第一趟: 就是在10个元素选择关键字最小的元素也就是1与第1个元素交换，1就是作为有序序列中的第1个元素。

第二趟：剩下的9个元素中继续这种选择和交换，选择关键字最小的元素也就是2与第2个元素进行交换，2就是作为有序序列中的第2个元素了。

…

操作：选择排序代码实现

操作：选择排序代码讲解

01-Selection-Sort main.cpp

#include <iostream>
#include <algorithm>using namespace std;void selectionSort(int arr[], int n){for(int i = 0 ; i < n ; i ++){// 寻找[i, n)区间里的最小值int minIndex = i;for( int j = i + 1 ; j < n ; j ++ )if( arr[j] < arr[minIndex] )minIndex = j;swap( arr[i] , arr[minIndex] );}}int main() {int a[10] = {10,9,8,7,6,5,4,3,2,1};selectionSort(a,10);for( int i = 0 ; i < 10 ; i ++ )cout<<a[i]<<" ";cout<<endl;return 0;
}

Java版

package algo;public class SelectionSort {// 我们的算法类不允许产生任何实例private SelectionSort(){}public static void sort(int[] arr){int n = arr.length;for( int i = 0 ; i < n ; i ++ ){// 寻找[i, n)区间里的最小值的索引int minIndex = i;for( int j = i + 1 ; j < n ; j ++ )if( arr[j] < arr[minIndex] )minIndex = j;swap( arr , i , minIndex);}}private static void swap(int[] arr, int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void main(String[] args) {int[] arr = {10,9,8,7,6,5,4,3,2,1};System.out.println("SelectionSort选择排序：");for( int i = 0 ; i < arr.length ; i ++ ){System.out.print(arr[i]);System.out.print(' ');}System.out.println();}
}

Result

D:\Environments\jdk-11.0.2\bin\java.exe -javaagent:D:\Java\ideaIU-2019.2.win\lib\idea_rt.jar=5368:D:\Java\ideaIU-2019.2.win\bin -Dfile.encoding=UTF-8 -classpath D:\IdeaProjects\imooc\Play-with-Algorithms\02-Sorting-Basic\out\production\01-Selection-Sort algo.SelectionSort
SelectionSort选择排序：
10 9 8 7 6 5 4 3 2 1 Process finished with exit code 0