当前位置 博文首页 > 美迪的麦柯的博客：小白程序员必会基础排序---＞编程新手看过来
本文假定 ：
（1）要排序的数据是整数；
（2）数据储存在数组中；
（3）数据以升序排列。
注：排序程序很容易修改为对其它类型的数据排序，以降序排列或者对ArrayList或LinkedList中的数据排序。
一、选择排序
每次的外层循环的迭代之后，list[i]都被放在正确的位置。最后，所有的元素都被放到了正确的位置上。因此，数列也就排好序了。
可能的Java代码：list为其他类型的话，list[currentMin]需要更换数据类型喏
class SelectSort{
public static void selectSort(int[] list) {
// TODO Auto-generated method stub
for(int i=0;i<list.length-1;i++)//外层循环迭代执行控制以得到list[i]到list[array.length-1]的列表中最小的元素list[currentMIn],然后与list[i]互换。
{
int currentMin=list[i];
int currentMinIndex=i;
for(int j=i+1;j<list.length;j++)
{
if(currentMin>list[j])//如果前面一个数大于后面的数，目前最小数以及目前最小数坐标都换成j
{
currentMin=list[j];
currentMinIndex=j;
}
}
if(currentMinIndex!=i)//就是if(list[i]>list[j])
{
list[currentMinIndex]=list[i]; //直接把list[i]赋值给list[j]
list[i]=currentMin; //然后list[j]又直接赋值给list[i]？？？？什么逻辑啊
//我倒是懂了/hahaha有那么很多点道理。
}
}
}
}
可以用下面的语句或者主函数跟踪方法：
（1）语句：
int [] array= {5,-1,0,9,87,58,99,101};
SelectSort.selectSort(array);
（2）主函数：
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] array= {5,-1,0,9,87,58,99,101};
SelectSort.selectSort(array);
for(int i=0;i<array.length-2;i++)
{
System.out.print(array[i]+" ");
}
System.out.println(array[array.length-1]);
}
}
（3）运行结果：
（4）分析选择排序算法：
给出的分析排序算法，是在列表中找到最小元素，并与其第一个元素互换，然后在剩下的元素中找到最小元素，将其与剩下的列表中的第一个元素交换，这样一直做下去，直到列表中只剩一个元素为止。
对于第一次迭代，比较次数为n-1；第二次迭代次数为n-2；以次类推。设T（n）表示选择排序的复杂度，c表示每次迭代的其他操作如赋值和额外的比较的次数。这样：
T(n)
=（n-1）+c +（n-2）+c +…+ 2+c +1+c
=( (n-1)(n-1+1)/2 ) + c(n-1)
=( (nn)/2 ) - n/2 +cn -n
=O(nn) （注：平方符号在此处无法输出的原因，改为编程语言中的表述方法）
因此，选择排序算法的复杂度为 O(n*n)。
二、插入排序
插入排序是
//插入排序
（1）（2）省略，列举在一、选择排序之中；以下皆省略，以减少不必要的篇幅。
（3）运行结果！：
