小算法大智慧之排序（一）

准备好一组数据

private  int[] data={12,5,78,33,9,33,11};

一、排序算法

一、冒泡排序算法

如何实现

思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

步骤：

1.第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。

2.比较第2和第3个数，将小数 放在前面，大数放在后面。

...........

重复上步骤，将小数放在前面，大数放在后面，直到比较到最后的两个数，全部排序完成。

3.在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较。

4.在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较。

...........

重复上步骤，每一趟比较次数依次减少。

文字千百，不如图一张

i=0时，也就是第一趟开始比较，j从0开始，一直到j=数组长度-1

第一趟比较完成后，得到数组如下，第二趟比较时，最后一个数78将不参与比较。

接下来开始第二趟比较，也就是i=1，j从0开始，一直到j=数组长度-1-i

第二趟比较完成后，得到数组如下，下一趟，最后两个数33、78将不参与比较。

如此循环，我们将在第五趟，得到排序完成的数组，如下

再来个代码看看吧。

private  void maopao_sort(){
    int data_length=data.length;
    int temp;
    for(int i=0;i<data_length-1;i++){//i表示第几趟
        boolean IsSort=true;
        for(int y=0;y<data_length-i-1;y++){ //j表示遍历比较的次数，每遍历一趟，比较次数都会少一次
            if(data[y]>data[y+1]){   //如果前面的数大于后者，则交换。
                temp=data[y];
                data[y]=data[y+1];
                data[y+1]=temp;
                IsSort=false;
            }
        }
        System.out.println("遍历第"+i+"次");
        if(IsSort){
            System.out.println("排序完成"+i+"次");
            break;
        }
    }
    for(int i=0;i<data_length;i++){
        System.out.println(data[i]);
    }
}

算法中有个变量IsSort，用来优化效率，如果已经排序好，那就不需要遍历比较了。

我们可以总结下，N个数字要排序完成，总共进行N-1趟排序，第i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数。

时间复杂度分析

对包含n个数据的数组进行冒泡排序，最坏情况下，需要进行n*(n-1)/2次交换。最好情况下，无需进行交换。取中间值n*(n-1)/4，表示初始有序的的平均情况。也就是平均情况下需要n*(n-1)/4次交换操作，比较操作肯定要比交换操作多，而这个复杂度的上限是O(n²)。

所以可粗略地认为冒泡排序平均情况下时间复杂度是O(n²)。

二、选择排序算法

如何实现

思路：在长度为N的无序数组中，第n次遍历N-n个数，找到最小的数值与第n个元素交换

步骤：

1.第一次遍历N个数，找出最小的数与第一个数交换。

2.第二次从第二数个开始，遍历N-1个数，找出最小的数与第二个数交换。

如此循环......

3.直到进行第N-1次遍历，比较最后2个数，判断是否要交换。排序完成。

也来个图吧

第一次遍历，找到最小值5，与第一个数12交换，得到排序数组如下。

第二次遍历，从第二个数也就是12开始遍历，找到最小值9，与数字12交换，得到排序数组如下

如此循环，得到最后排序后的数组如下

我们在配个代码来学习下。

private void select_sort(){
    int data_length=data.length;
    int temp;
    int min_index;
    for(int i=0;i<data_length-1;i++){
        min_index=i;
        for(int y=i+1;y<data_length;y++){
            if(data[min_index]>data[y]){
                min_index=y;
            }
        }
        if(min_index!=i){
            temp=data[i];
            data[i]=data[min_index];
            data[min_index]=temp;
        }
    }
    for(int i=0;i<data.length;i++){
        System.out.println(data[i]);
    }
}

时间复杂度分析

第一次排序，需要比较N-1次； 第二次排序，需要比较N-2次； ...... 第N-1次排序，需要比较1次；

比较次数=(N-1)+(N-2)+...+1=((1+ N-1)*(N-1))/2=N²/2 + N/2 所以时间复杂度为：O(N²)

三、区别

一、相同点

1.都有两层循环，外层循环控制比较的轮数，和数组元素的个数有关。内层循环控制需要参与比较的元素个数，和外层循环的轮数有关,最终比较的次数是一样的。

2.两种算法进行交换的结构是相同的。

二、不同点

1.冒泡算法每轮每个数据比较需要交换数据，选择算法每轮只要交换一次数据。所里理论上，选择排序效率高一点。