今天这篇文章简单介绍下最最最基础的排序
我们数据的存储方式默认为数组，长度为N个元素
选择排序：
算法描述：就是在数组中找到最小的元素，和第一位元素互换内容，倘若第一位的元素最小，则自己和自己互换。然后从第二位开始（因为第一位已经排好序了）遍历数组找到现存最小的元素，让他和第二互换位置。然后从第三位开始重复。。。。。
影响排序的时间的因素有两点，一个是数据移动，为N次。一个是数组比较（其实就是数组遍历的过程）为N-1+N-2+····+2+1=N（N-1）/2约为N^2的量级
根据上面分析可以看出选择排序的时间和输入无关，无论是随机打乱的数组还是已经排好序的数组，进行排序所用的时间都一样。
选择排序的代码实现
public class Selection {
public static void sort(int [] a) {
int n=a.length;
int min;
for(int i=0;i<n;i++) { //i代表正在排序的位置
min=i;
for(int j=i+1;j<n;j++) { //遍历数组只需要从i后面的数组就行，前面已经排好序了
if(a[j]<a[min]) min=j; //找到最小的元素，然后记录它的序号
}
exchange(a, i, min);
}
}
//交换数组元素的次序
public void exchange(int []a,int b,int min) {
int temp=a[b];
a[b]=a[min];
a[min]=temp;
}
}
插入排序：
算法描述：是自己从大到小的序号开始遍历数组元素，比如刚好遍历到i序号，则序号0-(i-1)都是维护大小顺序，现在就是要将原来序号为i的的元素插入到已经维护好的数组，形成排序好的i+1数组，不断增加排序好的数组的元素数目。最后形成数量为n的排序后的数组。
这个算法的时间是和输入有关的最坏情况要分别有~n^/2 比较和交换。最好的情况为n-1次比较0次交换，平均下来是n^2/4的比较和交换，看起来如果n比较大的话好像插入比选择排序更快
public class Insertionsort {
public static void sort(int []a) {
int n=a.length;
for(int i=1;i<n;i++) {
for(int j=i;j>0&&(a[j]<a[j-1]);j--) {
exchange(a,j,j-1);
}
}
}
public static void exchange(int []a,int b,int min) {
int temp=a[b];
a[b]=a[min];
a[min]=temp;
}
}
希尔排序
这个有一点点难懂，它其实是上面插入排序的升级版。不过它维护数组不是从左到右长度逐渐变大（传统插入排序的方式）。它是将数组分成gap组，每组数组的元素为间隔为gap的元素，每一组的元素数可能为n/gap（如果gap不是n的因数的话部分数组的元素数为n/gap+1）然后分别维护他们的顺序。然后再将gap的值按一定规则变小，重新切割数组再维护数组顺序。gap变得越来越小，最后变成1。这时候就维护长度为n的序列，就是完整的遍历冒泡排序，（冒泡和插入，区别不大，但是有区别的，具体查查冒泡排序）这里说冒泡是强调最后一次数组遍历保证排序的正确性，前面的工作只是为了减少这一步的比较和交换次序的操作。
希尔排序的核心思想维护部分部分有序最终利于维护整体有序。
public class Shellsort {
public static void sort(int [] a) {
int n=a.length;
int gap=n/2;
while(gap>=1) {
for(int i=gap;i<n;i++) {
for(int j=i;j>=0&&a[j]<a[j-gap];j-=gap) {
exchange(a,j,j-gap);
}
}
gap/=2;
}
}
public static void exchange(int []a,int b,int c) {
int temp=a[b];
a[b]=a[c];
a[c]=temp;
}
}
注意gap的取值和缩小规律是如何其实都是没关系的，不会影响算法的正确性。但是gap一定要最后是为1！！！
希尔排序对中等大小的数组的运行时间还是可以接受的，但它还只是一种基础的算法，对于大型的数组排序还是需要更高效的算法，这就需要我们继续的学习了。:）
网友评论