直接选择排序算法

A. 直接选择排序算法在最好情况下的时间复杂度为多少

关键字比较次数永远是n(n-1)/2，记录移动次数最多为3(n-1)，最少0次，前者起主导作用，因此实际上时间复杂度还是O(n^2)。

在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数C=(n*n - n)/2,总的移动次数 3(n-1).由此可知，直接选择排序的时间复杂度为 O(n2) 。

(1)直接选择排序算法扩展阅读：

直接选择排序的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值。

与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。当记录占用字节数较多时，通常比直接插入排序的执行速度快些。由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。

B. 第一排01第二排02 03,以此类推,怎么用代码实现数据排列效果

选择排序是常用内部排序的一种，常见的实现算法有直接选择排序算法和堆排序算法，选择排序的基本思想是每次从待排数据中选择第n小的数据放到排序列表的第n个位置，假如共有N个数据待排，那么经过N-1次排序后，待排数据就已经按照从小到大的顺序排列了。
直接选择排序算法的思想比较简单：（假设数据放在一个数组a中，且数组的长度是N）
1：从a[0]-a[N-1]中选出最小的数据，然后与a[0]交换位置
2：从a[1]-a[N-1]中选出最小的数据，然后与a[1]交换位置（第1步结束后a[0]就是N个数的最小值）
3：从a[2]-a[N-1]中选出最小的数据，然后与a[2]交换位置（第2步结束后a[1]就是N-1个数的最小值）
以此类推，N-1次排序后，待排数据就已经按照从小到大的顺序排列了。
直接选择排序的java实现如下：
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static void selectionSort(int[] elements){
for(int i = 0; i < elements.length-1; ++i){
int k = i;
for(int j = i; j < elements.length; ++j){
if(elements[k] > elements[j]){
k = j;
}
}
if(k != i){//交换元素
int temp = elements[i];
elements[i] = elements[k];
elements[k] = temp;
}
}
}

直接选择排序算法的思路很清晰，实现起来也比较简单，但是效率不是很高（O(n*n)）。
堆排序算法和直接选择排序算法最大的不同在于，堆排序算法充分利用大顶堆和完全二叉树的性质，保留每次排序后的结构，同时由于每次比较只是比较根节点和它的子节点，因此大大降低了比较的次数和交换的次数，从而提高效率，堆排序算法的时间复杂度是O(nlogn，以2为底)。
堆排序算法的思想是：（假设数据放在一个数组a中，且数组的长度是N）
1：以数组a为数据，建立一个大顶堆（这样对于二叉树的每个节点，根节点总是比子节点大，其实没必要要求二叉树的每个子树也是大顶堆）
2：交换大顶堆的根节点和数组a中的最后一个节点（最后一个节点不在参与后边的工作）
重复上边的工作，经过N-1次后，数组a已经排好序。
其他的我不太会

C. 简单(直接)选择排序的稳定性

简单选择排序是不稳定排序。

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

(3)直接选择排序算法扩展阅读：

简单选择排序的最优情况：

最好情况下，即待排序记录初始状态就已经是升序排列了，则不需要移动记录。

对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。

排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法。

参考资料来源：网络-简单选择排序

参考资料来源：网络-排序算法稳定性

D. 数据结构-八大排序算法的时间复杂度 稳定性

1：直接插入排序：
最好：待排序已经有序， 从前往后走都不用往里面 插入。 时间复杂度为o(n)
最坏：待排序列是逆序，每一次都要移位插入。 时间复杂度o(n^2)
是稳定排序

2：希尔排序：
最好：缩小增量的插入排序，待排序已经有序。时间复杂度o(n）
一般：平均时间复杂度o(n ^{1.3)，最差也是时间复杂度o(n} 1.3)
不稳定排序

3：冒泡排序：
最好：待排序已经有序。时间复杂度o(n）
最坏：待排序是逆序。时间复杂度o(n^2）
稳定排序

4：快速排序：
最好：待排序无序。时间复杂度o(nlogn)
最坏: 待排序已经有序，基准定义在开始。 时间复杂度为o(n^2)
不稳定排序

5：直接选择排序：
无论好坏:o(n^2)
稳定排序

6：堆排序：
无论好坏：时间复杂度o(nlogn)
不稳定排序

7：归并排序：

稳定排序

8：基数排序：
无论好坏:o(d(n+r)) ，r为基数，d为位数.
稳定排序