初识Java（Java数组-数组排序算法)

川长思鸟来 2022-05-27 04:51 219阅读 0赞

### 一、数组排序算法 ###

1.1 冒泡排序

在程序设计中，经常需要将一组数列进行排序，这样更加方便统计与查询。

冒泡排序是最常用的数组排序算法之一，它排序数组元素的过程总是将小数往前放、大数往后放，类似水中气泡往上升的动作，所以称作冒泡排序。

（ 1 ）基本思想

冒泡排序的基本思想是对比相邻的元素值，如果满足条件就交换元素值，把较小的元素移动数组前面，把大的元素移动数组后面（也就是两个元素交换位置），这样较小的元素就想气泡一样从底部上升到顶部。

（ 2 ）算法示例

冒泡算法由双层循环实现，其中外层循环用于控制排序轮数，一般为要排序的数组长度减 1 次，因为最后一次循环只剩下一个数组元素，不需要对比，同时数组已经完成排序。而内层循环主要用于对比数组中每个临近元素的大小，以确定是否交换位置，对比和交换次数随排序轮数而减少。

（ 3 ）算法实现

eg ：实现冒泡排序，正排序。

public class BubbleSort{
        public static void main(String[] args){
            int[] array = { 63, 4, 24, 1, 3, 15 };         //创建一个数组，这个数组元素是乱序
            BubbleSort sorter = new BubbleSort();          //创建冒泡排序类的对象
            sorter.sort(array);                            //调用排序方法将数组排序
        }
        /**
         * 冒泡排序
         *@param array 要排序的数组
         */
        public void sort(int[] array){
            for(int i = 0 ; i < array.length ; i++){
                //比较相邻两个元素，较大的数往后冒泡
                for(j = 0 ; j < array.length-i ; j++){
                    if(array[j] > array[j+1]){
                        int temp = array[j];                //把第一个元素值保存到临时变量中
                        array[j] = array[j+1];              //把第二个元素值保存到第一个元素单元中
                        array[j+1] = temp;                  //把临时变量(也就是第一个元素原值)保存到第二个元素中
                    }
            }
        }
        showArray(array);                                   //输出冒泡排序后的数组元素
        }
        /**
         * 显示数组中的所有元素
         *@param array 要显示的数组
         */
        public void showArray(int[] array){
            for(int i : arrray){                            //遍历数组
                System.out.print(">"+i);                    //输出每个数组元素值
            }
            System.out.println();
        }
    }

运行结果为 ：> 1 > 3 > 4 > 15 > 24 > 63

冒泡排序的主要思想是：把相邻两个元素进行比较，如满足一定条件则进行交换（如判断大小或日期前后等），每次循环都将最大（或最小）的元素排在最后，下一次循环是对数组中其他的元素进行类似操作。

1.2 直接选择排序

直接选择排序方法是属于选择排序的一种，它的排序速度要比冒泡排序快一些，也是常用的排序算法。

（ 1 ）基本思想

直接选择排序的基本思想是将排序位置与其他数组元素分别对比，如果满足条件就交换元素值，注意这里区别冒泡排序，不是交换相邻元素，而是把满足条件的元素与指定的排序位置交换（如从最后一个元素开始排序），这样排序好的位置逐渐扩大，最后整个数组都成为已排序好的格式。

与冒泡排序相比，直接选择排序的交换次数要少很多，所以速度更快些。

（ 2 ）算法示例

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序地放在已排好序的数列的最后，直到全部待排序的数据元素排完。

初识数组资源 [ 63 4 24 1 3 15 ]
    第一趟排序后 [ 15 4 24 1 3 ] 63
    第二趟排序后 [ 15 4 3 1 ] 24 63
    第三趟排序后 [ 1 4 3 ] 15 24 63
    第四趟排序后 [ 1 3 ] 4 15 24 63
    第五趟排序后 [ 1 ] 3 4 15 24 63

（ 3 ）算法实现

实现直接选择排序，正排序。

/**
    * 直接选择排序算法实例
    */
    public class SelectSort{
        public static void main(String[] args){
            int[] array = { 63, 4, 24, 1, 3, 15 };             //创建一个数组
            SelectSort sorter = new SelectSort();              //创建直接选择排序类的对象
            sorter.sort(array);                                //调用排序对象的方法将数组排序
        }     
        /**
        * 直接选择排序法
        * @param array 要排序的数组
        */
        public void sort(int[] array){
            int index ;
            for(int i = 1 ; i < array.length ; i++){
                index = 0;
                for(int j = 1 ;j <= array.length-i ; j++){
                    if(array[j] > array[index]){
                        index = j ;
                    }
                }
            //在交换位置 array.length-i 和 index(最大值)上的两个数
            int temp = array[array.length-i];                  //把第一个元素值保存到临时变量中
            array[array.length-i] = array[index];              //把第二个元素值保存到第一个元素单元中
            array[index] = temp;                               //把临时变量也就是第一个元素原值保存到第二个元素中
            }
            showArray(array);                                  //输出直接选择排序后的数组值
        }
        /**
        * 显示数组中的所有元素
        * @param array 要显示的数组
        */
        public void showArray(int[] array){
            for(int i : array){                                //遍历数组
                System.out.print(">"+i);                       //输出每个数组元素值
            }
            System.out.println();
        }
    }

运行结果为 ： > 1 > 3 > 4 > 15 > 24 > 63

1.3 反转排序

反转排序就是以相反的顺序把原有数组的内容重新排序。反转排序算法在程序开发中也经常用到。

（ 1 ）基本思想

就是把数组最后一个元素与第一个元素替换，倒数第二个与第二个元素替换，以此类推，直到所有数组元素反转替换。

（ 2 ）算法示例

反转排序是对数组两边的元素进行替换，所以只需要循环数组长度的半数次，如数组长度为 7 ，那么 for 循环只需要循环 3 次 。

eg ：

初始数组资源 [ 10 20 30 40 50 60 ]
    第一趟排序后 60 [ 20 30 40 50 ] 10
    第二趟排序后 60 50 [ 30 40 ] 20 10
    第三趟排序后 60 50 40 30 20 10

（ 3 ）算法实现

实现反转排序。

/**
    * 反转排序算法实例
    */
    public class ReverseSort{
        public static void main(String[] args){
            int[] array = {10 ,20 ,30 ,40, 50,60};             //创建一个数组
            ReverseSort sorter = new ReverseSort();            //创建反转排序类的对象
            sorter.sort(array);                                //调用排序对象的方法将数组反转
        }
        /**
        *直接选择排序法
        *@param array 要排序的数组
        */
        public void sort(int[] array){
            System.out.println("数组原有内容:");
            showArray(array);                                  //输出排序前的数组值
            int temp ;
            int len = array.length;
            for(int i = 0 ; i < len/2 ; i ++){
                temp = array[i];
                arrray[i] = array[len-1-i];
                array[len-1-i] = temp;
            }
            System.out.println("数组反转后的内容:");
            showArray(array);                                  //输出排序后的数组值
       }
        /**
         *显示数组中的所有元素
        *@param array 要显示的数组
        */
        public void showArray(int[] array){
            for(int i : array){                                //遍历数组
                System.out.printl("\t"+i);                     //输出每个数组元素值
            }  
        System.out.println();
        }
    }

运行结果为 ：

数组原有内容 ： 10 20 30 40 50 60

数组反转后的内容 ： 60 50 40 30 20 10