首页 > 程序开发 > 软件开发 > Java >

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

2014-09-23

单单有数据还不够,对于数据的展现,经常要按照一定的顺序进行排列,越高要求的排序越复杂,这篇只介绍三种大小的简单排序。 1)冒泡排序 模拟:有数组,1,4,2,5,7,3。 (1)首先从1开始冒泡,1比4小,不冒,4大于

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

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的时候,他就是老三的位置了。

接下来就是不停的循环,刚开始看不懂算法设计者的用意。

其实次序与大小出现的次数之间的关系竟然是如此美妙。

相关文章
最新文章
热点推荐