选择排序

    选择排序也是一种常见的算法，小编觉得直接讲太多文字有点啰嗦，我们直接从例子入手，来看看选择的实现过程，从实现过程来看看该算法的特征，并分析其时间复杂度。

一、例子讲解

    有以下数组array[8]={6，3，2，1，8，9，7，5}。

array数组

    第一轮排序开始。此时所有元素处于无序区域。在无序区域中找出最小的元素1。并且把元素1与无序区域内的第一个元素交换。元素1即被加入到有序区域。

第一轮排序

    第二轮排序开始。在无序区域所有元素中找出最小的元素2，并且把元素2与无序区域内的第一个元素交换。元素2即被加入到有序区域。

第二轮排序

    第三轮排序开始。在无序区域所有元素中找出最小的元素3，由于元素3就是无序区域的第一个元素，因此不交换。元素3加入到有序区域。

第三轮排序

    第四轮排序开始。在无序区域所有元素中找出最小的元素5，并且把元素5与无序区域内的第一个元素交换。元素5即被加入到有序区域。

第四轮排序

    第五轮排序开始。在无序区域所有元素中找出最小的元素6，并且把元素6与无序区域内的第一个元素交换。元素6即被加入到有序区域。

第五轮排序

    第六轮排序开始。在无序区域所有元素中找出最小的元素7，并且把元素7与无序区域内的第一个元素交换。元素7即被加入到有序区域。

第六轮排序

    第七轮排序开始。在无序区域所有元素中找出最小的元素8，并且把元素8与无序区域内的第一个元素交换。元素8即被加入到有序区域。

第七轮排序

    此时，有序区域元素个数为8，而无序区域个数为1，，可得最后一个无序区域的元素即为有序区域的最后一个元素。

得到有序数组

    根据图解的实现过程，我们可以编写出选择排序相对应的C++实现代码。

二、代码截图

选择排序算法

三、时间和空间复杂度

    通过上述代码截图，可以发现决定算法时间复杂度的函数为selectSort。该函数中使用了嵌套的循环，程序的总执行步数最多，为n^2【可翻看小编以前的简书lookyilook】，因此该选择排序的时间复杂度为O(n^2)。

    空间复杂度，最优的情况下（已经有顺序）复杂度为：O(0)【不用借助辅助变量】；最差的情况下（全部元素都要重新排序）复杂度为：O(n )【需要n个辅助变量】；平均的时间复杂度：O(1)。

    有错请指正！