数据结构与算法五种排序方法（数据结构与算法）
数据结构与算法五种排序方法（数据结构与算法）比如5，8，5，2，9这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。不稳定排序，每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。重复第二步，直到所有元素均排序完毕。void selectSort(int a[] int n){ //进行n-1趟选择 最后一个元素不需要再选择比较 for(int i = 0; i <n-1; i ){ int minIndex = i; //从无序区选取最小的记录 for(int j = i 1; j<=n; j ){ if(a[minI
一、定义选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。
但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
void selectSort(int a[] int n){
//进行n-1趟选择 最后一个元素不需要再选择比较
for(int i = 0; i <n-1; i ){
int minIndex = i;
//从无序区选取最小的记录
for(int j = i 1; j<=n; j ){
if(a[minIndex] > a[j]) {
minIndex = j;
}
}
if(minIndex != i) {
//和最小元素交换值
swap(a[i] a[minIndex]);
}
}
}
public static void swap(int a int b){
int temp = a;
a = b;
b = temp;
}四、复杂度
空间复杂度为O(1)，是一种原地排序算法；
时间复杂度是O(n2)；
不稳定排序，每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
比如5，8，5，2，9这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。
五、冒泡排序，插入排序，选择排序比较
冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个。
我们把执行一个赋值语句的时间粗略地计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是K的数组进行排序。
用冒泡排序，需要K次交换操作，每次需要3个赋值语句，所以交换操作总耗时就是3*K单位时间。而插入排序中数据移动操作只需要K个单位时间。
这个只是我们非常理论的分析，为了实验，针对上面的冒泡排序和插入排序的Java代码，
写一个性能对比测试程序，随机生成10000个数组，每个数组中包含200个数据，然后在机器上分别用冒泡和插入排序算法来排序，
冒泡排序算法大约700ms才能执行完成，而插入排序只需要100ms左右就能搞定！
所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是O(n2)，
但是如果我们希望把性能优化做到极致，那肯定首选插入排序。插入排序的算法思路也有很大的优化空间，可以使用希尔排序。
