【算法】选择排序算法

1.简介

    选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

2.算法思想

  选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。

例如：

一个初始序列为：8、6、2、3、1、5、7、4

遍历一遍序列，找到最小的元素为1，将元素1放在序列的第一位

第一趟排序之后结果： 1、6、2、3、8、5、7、4

在剩下的元素中寻找最小的元素，将其放在序列第二位，并依次类推

第二趟排序结果为： 1、2、6、3、8、5、7、4

第三趟排序结果为： 1、2、6、3、8、5、7、4

第四趟排序结果为： 1、2、3、6、8、5、7、4

第五趟排序结果为： 1、2、3、4、8、5、7、6

第六趟排序结果为： 1、2、3、4、5、8、7、6

第七趟排序结果为： 1、2、3、4、5、6、7、8

第八趟排序结果为： 1、2、3、4、5、6、7、8

  至此序列便排序完成，我们可以看到，实际上第七趟已经排序完成了，但是选择排序仍然会进行第八趟排序，只是不会交换元素。由此可见选择排序是一种O(n²)级别的排序，并且不能够提前终止循环的，这也是选择排序低效率的原因之一。

3.代码实现

void swap(int* a,int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void selectionSort(int arr[],int n)
{
    for(int i=0;i<n;i++){
        int min_index = i;
        for(int j= i+1;j<n;j++){
            if(arr[j] < arr[min_index]){
                min_index = j;
            }
        }
        swap(&arr[i],&arr[min_index]);
    }
}