【排序基础】1、选择排序法 - Selection Sort

时间：2023-03-08 17:05:25

选择排序法 - 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

相关文章