Java数据结构和算法(三)——简单排序

单单有数据还不够，对于数据的展现，经常要按照一定的顺序进行排列，越高要求的排序越复杂，这篇只介绍三种大小的简单排序。

1)冒泡排序

模拟：有数组，1,4,2,5,7,3。

(1)首先从1开始冒泡，1比4小，不冒，4大于2，冒上去，与2交换位置，4比5小，不冒，7比3大，冒，结果：1,2,4,5,3,7

(2)接下来从2开始，因为第一个元素冒过了，重复(1)，结果：1,2,4,3,5,7

(3)从第三位4开始，结果1,2,3,4,5,7

(4)虽然看起来已经排好序，但是还是要继续冒，接下来就是从第4位开始，直到第五位元素冒完。

代码：

public class BubbleSort{  
    public static void main(String[] args) {
        int a[] = {1,2,3,4,5,6,3,1,2,3 };
        for (int i = 0; i < a.length-1; i++) {
            for (int j = i; j < a.length; j++) {
                if(a[i]>a[j]){
                    int temp = a[j];
                    a[j] = a[i];
                    a[i]=temp;
                }
            }
        }
    }
}

复杂度：

第一次9次比较，第二次8次，最后1次，比较总数9+8+......+1，9！。

如果N个数据，那比较就是N！=N*(N-1)/2，交换次数大概为比较的一半，N*(N-1)/4，最坏的时候和比较次数一样。

去掉常数，时间复杂度O(N^2)。

2)选择排序

选择排序改进了冒泡排序，交换的次数，看清楚是交换的次数O(N^2)减少到了O(N)。为什么？

模拟：有数组，1,4,2,5,7,3。

(1)从第一个元素开始，假设1为数组的最小值，min=1(min存放的是最小元素的位置)，用1开始和后面元素比较，如果还有比1小的值x，将x元素所在的位置赋值给min，比较之后发现1最小。这个时候，最小的值已经放在最左边了，进入(2)

(2)从第二个值4开始，假设min=2，与2对比，2更小，min=3，2再与5对比，还是2小，与7对比，2小，与3比，2小，最后min=3，同时将2和4替换位置。数组为：1,2,4,5,7,3。

(3)从第三个值4开始(上一步交换了)，这次min=3，与4换位。数组为：1,2,3,4,5,7。

(4)从第四个值4开始，这次min是4了，以此类推。最后：1,2,3,4,5,7。

代码：

第一次敲的：

public class SelectSort{  
    public static void main(String[] args) {
        int a[] = {1,2,3,4,5,6,3,1,2,3 };
        for (int i = 0; i < a.length-1; i++) {
            int min = i;
            int j =0;
            for ( j= i+1; j < a.length-1; j++) {
                if(a[i]>a[j]&&a[i]!=a[j]){
                    min = j;
                }
            }
            int temp = a[i];
            a[i] = a[min];
            a[j] = temp;
        }
        System.out.println(Arrays.toString(a));
    }
}

第二次正确：

public class SelectSort{  
    public static void main(String[] args) {
        int a[] = {1,2,3,4,5,6,3,1,2,3 };
        for (int i = 0; i < a.length-1; i++) {
            int min = i;
            for ( int j= i+1; j < a.length; j++) {
                if(a[j]交换值那里和比较那里我写错了，本身比较的时候我们已经把min设定成i开始，那么是将min与j比，如果j更小，则min=j。然后，交换值的时候，和j也是没关系的，既然锁定了最小值的位置，只要和i交换即可。
 
算法有个可以优化地方，就是两者相等的时候是不用互换位置的。减少了一次赋值。
 
复杂度：
其实比较次数也是和冒泡一样——阶乘——N!=N*(N-1)/2。（N个元素）
但是交换的次数是少于N的，所以选择排序比冒泡快，当然元素达到一定数量级的时候，速度就体现出来了。
 
3)插入排序
在简单的排序这三种中最快，时间复杂度仍然为O(N)
 
这个写完代码再解释模拟过程：
代码：
 
public class InsertSort {
    public static void main(String[] args) {
        int[] a = {1,3,2,1,4,2,5,7,3};
        int mark,compare;
        for(mark = 1;mark < a.length;mark++ ){
            int temp = a[mark];
            compare = mark;
            while(a[compare-1]>temp&&compare-1>0){
                a[compare] = a[compare-1];
                compare--;
            }
            a[compare] =temp;
        }
        System.out.println(Arrays.toString(a));
    }
}


模拟：有数组，1,3,2,1,4,2,5,7,3。这个复杂一些，其实也不复杂。
 
(1)首先mark指向插入的位置，从数组第二个位置开始，temp值等于mark位置的元素值，往左比较，3大于1，while循环，a[mark]=temp，即3没有变化，下个for循环。
(2)mark=2，指向2，temp=2，往左，3大于temp，所以2的值替换3，compare
的值减一，即将1和temp比较，1小，跳出while循环，a[mark]=temp，即3的值变成2。
(3)数组现在为，1,2,3,1,4,2,5,7,3，mark=3，指向1，temp=1，往左，3大于1，a[compare]，即a[3]=a[2]=3，再往左，compare减一，compare=2，2大于1，所以a[compare],a[2]=a[1]=2，此时为1,2,2,3,4,2,5,7,3。在往左，compare减一，a[0]=1，不移动，最后a[1]=temp=1，变成1,1,2,3,4,2,5,7,3。
(4)mark+1，继续循环，每次就是以mark为标志，向左比较大小，不停移动。直至最后。
 
复杂度：
比较次数看起来也是阶乘——N!=N*(N-1)/2，但其实每次插入点之后，插入点前面的数据就是有序的，所以，真正比较的只有一半左右——N!=N*(N-1)/4，
复制和比较的次数大致相等。虽然复杂度也是O(N^2)。
但是如果数组是1,2,3,4,5,6,7,8,7的话，也就是前面基本有序，那只有当mark等于9的时候才会比较，而且，就只和8交换而已。那这样的话时间复杂度只有O(N)。
所以说插入比冒泡快一倍，比选择排序快一些。
 
4)题外——计数排序。
 
上面引用了另外一个博客链接，简单的三种排序复杂度都到了O(N^2)，即使后面高级一些的排序也是要O(NlogN)。前段时间看题目发现竟然有O(N)复杂度的排序：现有n个小于100000的整数，写一个算法将这些数从小到大排序，要求时间复杂度O(n)，空间复杂度O(1)。
原来就是用的计数排序。发现原来是算法导论里有的，果断翻书。
 
public class SelectSort{  
    public static void main(String[] args) {
        int a[] = {1,2,3,4,4,4,3,1,2,3 };
        int c[] = new int[5];//c是用来存放每个数字出现次数的数组
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < a.length; j++) {
                if(i == a[j])
                    c[i]++;
            }
        }
        System.out.println(Arrays.toString(c));
        //[0, 2, 2, 3, 2]
        for (int i = 1; i < c.length; i++) {
            c[i] = c[i] +c[i-1];
        }
        System.out.println(Arrays.toString(c));
        //[0, 2, 4, 7, 9]
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[c[a[i]]-1] = a[i];
            c[a[i]]--;
        }
        System.out.println(Arrays.toString(b));
    }
}
算法设计得太巧妙了。
 
c数组为存储a数组中数字出现的个数，即c[0]表示a中0出现的个数，也正因为这样，所以c数组的长度要为a数组中最大元素+1。
 
然后：
 
for (int i = 1; i < c.length; i++) {
     c[i] = c[i] +c[i-1];
}
其实就是次数的累加，比如c[1]=c[1]+c[0]，那么c[1]存的就是a数组出现0和1的个数，以此类推，c[2]存的就是小于等于2的个数。
 
 
 
for (int i = 0; i < a.length; i++) {
      b[c[a[i]]-1] = a[i];
      c[a[i]]--;
}
这里才是算法最美妙的地方。
 
i=0，a[0]=1，c[1]就是1以及0出现次数的地方，1以及0出现两次，既然没有0，那么1就是占据了第一位和第二位的位置（请仔细读这句话，这句话读懂了，整个算法就理解了）。然后我们就把其中的一个1放在1的第二位b[1]的位置，同时c[1]-1，因为我们已经排好了一个1了。
 
接下来，i=1，a[1]=2，c[2]是小于等于2的数字出现的个数，c[2]=4，那么要把它排在第四位，即b[3]的位置，同时c[2]-1=3，因为一个4已经排好序了，那么下次读到4的时候，他就是老三的位置了。
 
接下来就是不停的循环，刚开始看不懂算法设计者的用意。
其实次序与大小出现的次数之间的关系竟然是如此美妙。