版本记录

版本号	时间
V1.0	2017.09.05

前言

将数据结构和算法比作计算机的基石毫不为过，追求程序的高效是每一个软件工程师的梦想。下面就是我对算法方面的基础知识理论与实践的总结。感兴趣的可以看上面几篇。
1. 算法简单学习（一）—— 前言
2. 算法简单学习（二）—— 一个简单的插入排序
3. 算法简单学习（三）—— 分治法与合并排序
4. 算法简单学习（四）—— 冒泡排序
5. 算法简单学习（五）—— 函数的增长
6. 算法简单学习（六）—— 常用的几种相关函数
7. 算法简单学习（七）—— 递归式
8. 算法简单学习（八）—— 堆排序
9. 算法简单学习（九）—— 建堆与堆排序算法
10. 算法简单学习（十）—— 基于堆的优先级队列
11. 算法简单学习（十一）—— 快速排序算法

基本了解

以下部分内容来自百度

选择排序法 是对 定位比较交换法（也就是冒泡排序法） 的一种改进。选择排序的基本思想是：每一趟在n - i + 1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

简单选择排序的基本思想：第1趟，在待排序记录r[1] ~ r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2] ~ r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

---

基本思想

选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

简单选择排序的基本思想：第1趟，在待排序记录r[1] ~ r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2] ~ r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
以下为简单选择排序的存储状态，其中大括号内为无序区，大括号外为有序序列：

初始序列：**{**49 27 65 97 76 12 38**}**　　
第1趟：12与49交换：12**{**27 65 97 76 49 38**}**　　
第2趟：27不动　：12 27**{**65 97 76 49 38**}**　　
第3趟：65与38交换：12 27 38**{**97 76 49 65**}**　　
第4趟：97与49交换：12 27 38 49**{**76 97 65**}**　　
第5趟：76与65交换：12 27 38 49 65**{**97 76**}**　　
第6趟：97与76交换：12 27 38 49 65 76 97 完成

---

算法分析

简单选择排序算法分析：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，需要移动记录的次数最多为3（n-1）（此情况中待排序记录并非完全逆序，给完全逆序记录排序的移动次数应为(n/2)3，其中n/2向下取整*）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n2)。

在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解，设有10个数分别存在数组元素a[0]～a[9]中。定位比较交换法是由大到小依次定位a[0]～a[9]中恰当的值（和武林大会中的比武差不多），a[9]中放的自然是最小的数。如定位a[0],先假定a[0]中当前值是最大数，a[0]与后面的元素一一比较，如果a[4]更大，则将a[0]、a[4]交换，a[0]已更新再与后面的a[5]～a[9]比较，如果a[8]还要大，则将a[0]、a[8]交换，a[0]又是新数，再与a[9]比较。一轮比完以后，a[0]就是最大的数了，本次比武的武状元诞生了，接下来从a[1]开始，因为状元要休息了，再来一轮a[1]就是次大的数，也就是榜眼，然后从a[2]开始，比出探花，真成比武大会了，当比到a[8]以后，排序就完成了。

---

算法实现

我这里就用C语言实现以下选择排序算法。

#include <stdio.h>
#include <string.h>
#include <time.h>

int main(int argc, const char * argv[])
{
    /**
     选择排序算法
     */
    int k = 0;
    int a[10] = {10, 8, 1, 9, 2, 4, 3, 5, 13, 7};
    //10个数，所以只需比9次
    for (int i = 0; i < 9; i ++) {
        k = i;
        for (int j = i + 1; j < 10; j ++) {
            if (a[k] < a[j]) {
                //使a[k]中始终是最大数
                k = j;
            }
        }
        if (k != i) {
            a[i] = a[i] ^ a[k];
            a[k] = a[i] ^ a[k];
            a[i] = a[i] ^ a[k];
        }
    }
    
    for (int i = 0; i < 10; i ++) {
        printf("%d\n", a[i]);
    }
}

下面看输出结果

13
10
9
8
7
5
4
3
2
1
Program ended with exit code: 0

后记

注意区分以下和冒泡排序还有快速排序的原理上的差别，实现并不难，主要是理解思想，未完，待续~~~