java数组三种排序方式

java数组三种排序方式

• • • 一、冒泡排序
    • 二、插入排序：
    • 三、选择排序
    • 三种算法排序的稳定性分析

一、冒泡排序

动图演示：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

排序思路：
第一步：将倒数第一个和倒数第二个数进行比较，如果小，则互换；
第二步：将倒数第二个和倒数第三个数进行比较，如果小，则互换；
… …
第N步：筛选出最小的一个数，然后从剩下的数中按照上面的方法反复操作，得到需要的序列。

代码实现

import java.util.Arrays;

public class TestDemo { 
    public static void main(String[] args) { 
        int [] array = { 7,14,3,22,1,6,15,60,5};
        for (int i = 0; i < array.length-1; i++) {  //控制循环次数，比长度少一次。
            for (int j = 0; j < array.length-i-1; j++) {  //后面排好的值不需要进行比较，所以减去i。
                if(array[j]>array[j+1]) { 
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

测试结果

二、插入排序：

动图演示：

在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

例：六个数12 15 9 20 6 31 24 用直接插入排序，如下图：

思路：

第一步：从给出的六个数中，随便拿出一个数，比如12，形成一个有序的数据序列（一个数当然是有序的数据序列了，不看12之外的数，就当其他的数不存在）；
第二步：从剩下的五个数中挑出一个数来，比如15，和刚才的12作比较，12<15，因此，放在12后面，形成数据序列12 15；
第三步：从剩下的四个数中挑出一个数来，比如9，和刚才的有序数据序列12 15作比较，9 < 12 < 15，因此，放在最前面，形成数据序列9 12 15；
… …
第N步，经过这样一个一个的插入并对比，就形成了上图所示的排序结果。在一个元素插入时，首先要和数据序列中最大的元素作比较，如果遇到相同的，则放在相同元素的后面。

代码实现

public class TestDemo { 
    public static void main(String[] args) { 
        int [] array = { 7,14,3,22,1,6,15,60,5};
        int temp=0;
        for(int i=1;i<array.length;i++){ 
            int j=i-1;
            temp=array[i];
        for(;j>=0&&temp<array[j];j--){ 
            array[j+1]=array[j];//将大于temp的值整体后移一个单位 
        }
            array[j+1]=temp;
        }
        System.out.println(Arrays.toString(array));
    }
}

测试结果

三、选择排序

动图演示：

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

思路：

第一步：从四个数找到最小的，和初始状态排在第一位的移动互换；
第二步：从剩下三个数中找到最小的，和初始状态排在第二位的移动互换；
… …
第N步：重复上述查找最小和互换的步骤，直到最后一个为止。

代码实现

public class TestDemo { 
    public static void main(String[] args) { 
        int [] array = { 7,14,3,22,1,6,15,60,5};
        for (int i = 0; i < array.length-1; i++) {  //i为要比较的元素。
            for (int j = i+1; j < array.length; j++) {  //i后的每一次元素。
                if(array[i]>array[j]) //两者比较，将较小值放在前面位置。
                { 
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

测试结果

三种算法排序的稳定性分析

1. 直接插入排序：一般插入排序，比较是从有序序列的最后一个元素开始，如果比它大则直接插入在其后面，否则一直往前比。如果找到一个和插入元素相等的，那么就插入到这个相等元素的后面。插入排序是稳定的。
2. 选择排序：在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。光说可能有点模糊，来看个小实例：858410，第一遍扫描，第1个元素8会和4交换，那么原序列中2个8的相对前后顺序和原序列不一致了，所以选择排序不稳定。
3. 冒泡排序：由前面的内容可知，冒泡排序是相邻的两个元素比较，交换也发生在这两个元素之间，如果两个元素相等，不用交换。所以冒泡排序稳定。

部分内容转载自: https://blog.csdn.net/zwqjoy1.