2 排序基础 - 1选择排序法

写在Selection Sort之前：

我们先来学习O(n^{2)时间复杂度的排序算法，对于排序算法，最优的是O(nlogn)时间复杂度的排序算法，那么我们为什么学习O(n}2)的排序算法呢？

重视学习O(n^2)的排序算法原因：

• 相对基础
  （很多时候，在遇到一个问题时，我们都要先尝试用简单的方法尝试解决，这个过程可以加深我们对问题本身的理解 进而提出更加复杂的方法或者来优化我们原来设想的简单解法，启发：要是对于一些面试问题一时没有思路，不妨先尝试简单的方法，虽然这个简单的方法有问题，但是我们先摆出来，摆的过程中可能就会想到优化的方法，同时也可让面试官看到我们思考问题的过程）
• 编码简单，易于实现，是一些简单情景的首选
  （有些情况下我们使用的不是高级程序设计语言，在底层我们可能使用汇编，这种情况下O(n^2)的排序算法便于实现就成为了首选）
• 在一些特殊情况下，简单的排序算法更有效
• 简单的排序算法思想可以衍生出复杂的排序算法
  （比如希尔排序是在插入排序下进行了一次优化实现）
• 可作为子过程，改进更复杂的排序算法
  注意：以上有不理解，不要太在意，相信通过后续学习的深入可对其有更深的理解

我们首先来学习选择排序（Selection Sort）

Selection Sort 思路：

对于给定的数组：

1.png

首先我们在整个数组中找到第一名的位置（假设我们从小到大排），然后在数组中找到最小的数：

2.png

然后将1和现在的第一名的位置上的数（8）进行交换：

3.png

经过这样的一次交换，1所处的位置就是其最终的位置了：（以后就不用管1了，省心的孩子....）

4.png

之后，我们在剩下的位置（即除去1的6到4）找到此时最小的数：2，把2和相应的第2个位置上的元素（6）进行交换：

5.png

此时1和2的顺序已好：

6.png

此过程依此类推，继续在剩下的部分（6到4）找最小的数：

7.png 8.png 9.png

再看第4个：

10.png 11.png

下面5：

12.png 13.png

6：

14.png 15.png

7：

16.png

7不用动：（可以理解自己和自己进行了一次交换，结果是没有动）

17.png

对于8：（和7情况一样）

18.png

C++代码：

#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代码：

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};
        SelectionSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
        System.out.println();
    }
}