Java数据结构与算法之数组排序——冒泡

蔚落 2022-08-09 00:51 205阅读 0赞

1） 如此定义的原因：因为在算法执行的时候，最大的数据项总是冒泡到数组的顶端。  
2） 算法大概执行时间：  
比较的次数大概是N2/2，交换的次数大概是N2/4；故冒泡算法的执行时间为O(N2)  
3） 只要一个循环嵌套到另外一个循环里，则其算法的执行时间，可以认为是O(N2)。  
4） 不变性：  
out右边的所有数据都是有序的。  
5） 思路：  
A） 设置一个outer的外层标签，用以标识其右边的元素已经排好。初始值在数组末尾即elementPos-1处，每经过一次循环，outer减1，直至数组最左端。  
B） 设置一个in的内层标签，用以遍历还未排序的元素，其初始值为数组起始位置，即0，终止值为outer减1的位置。这样做，可以避免已排序的元素，再次被排序。  
C） 交换的条件是，当相邻两个元素，前者比后者大的时候，数据进行交换。  
源码示例如下:  
//RandomArray .java

package com.wayne.example.SortArray;
    
    public class RandomArray { 
    
        private int[] randomArray;
        private int elementPos;
    
        /** * 数组初始化，初始化数组的长度 * * @param maxSize * 数组的长度 */
        public RandomArray(int maxSize) {
            randomArray = new int[maxSize];
            elementPos = 0;
        }
    
        /** * 获取数组长度，用于获取数组的长度 * * @return 返回数组的长度 */
        public int size() {
            return elementPos;
        }
    
        /** * 插入元素，用于向数组中插入元素 <br> * 利用遍历插入元素，即每次就查到原数组的最后一个位置上 * * @param value * 待插入的元素值 */
        public void insertElements(int value) {
            randomArray[elementPos] = value;
            elementPos++;
        }
    
        /** * 显示数组，用于显示数组中的元素 */
        public void displayElements() {
            System.out.print("[");
    
            for (int i = 0; i < elementPos - 1; i++)
                System.out.print(randomArray[i] + ", ");
    
            System.out.println(randomArray[elementPos - 1] + "]");
        }
    
        /** * 查找元素，用于查找数组中指定的元素 <br> * 利用遍历去找寻数组 * * @param value * 需要查找的数值 * @return 返回数据在数组中的索引值。如果没有找到，则返回 -1. */
        public int findElements(int value) {
    
            for (int i = 0; i < elementPos; i++)
                if (value == randomArray[i])
                    return i;
    
            return -1;
        }
    
        /** * 获取元素，用于获取该索引值对应的数组的元素 * * @param index * 数组索引值 * @return 如果索引值符合条件，则返回该索引值对应的数据；如果不符合条件，则返回-1 */
        public int getPosElements(int index) {
            if (index > elementPos) {
                System.out.println("你输入的索引值太大，悲了个具！");
                return -1;
            }
            return randomArray[index];
        }
    
        /** * 删除数据，用于删除数组中指定的元素<br> * * @param value * 需要删除的元素 * @return 返回是否删除成功。如果删除成功，则返回true;如果删除不成功，就返回false */
        public boolean deleteElements(int value) {
    
            int posTemp = findElements(value);
    
            if (posTemp == -1)
                return false;
            else {
                for (int i = posTemp; i < elementPos - 1; i++)
                    randomArray[i] = randomArray[i + 1];
                elementPos--;
    
                return true;
    
            }
        }
    
        /** * 排序数组，用于对数组中的元素进行排序<br> * 采用冒泡排序 */
        public void bubbleSort()
        {
            for(int outer = elementPos-1;outer>1;outer--)
                for(int in = 0;in<outer;in++)
                    if(randomArray[in]>randomArray[in+1])
                        swap(in,in+1);
        }
    
        /** * 交换数据，用于交换两个数据 * @param i 源数据1 * @param j 源数据2 */
        private void swap(int i, int j) {
            int temp = randomArray[i];
            randomArray[i] = randomArray[j];
            randomArray[j] = temp;
        }
    }

//测试类

package com.wayne.example.SortArray;
    
    import java.util.Scanner;
    
    public class BubbleSortArrayApp {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            System.out.println("请输入数组长度：");
            Scanner sc_maxSize = new Scanner(System.in);
            int maxSize = sc_maxSize.nextInt();
    
            System.out.println("现在我们得到一个长度为"+maxSize+"的数组！");
            RandomArray randomArray = new RandomArray(maxSize);
    
            System.out.println("现在我们将用0到99的数填充该数组");
    
            for(int i = 0;i<maxSize;i++)
            {
                int temp = (int)(Math.random()*100);
                randomArray.insertElements(temp);
            }
    
            System.out.println("填充完的数组如下：");
            randomArray.displayElements();
    
            System.out.println("经过冒泡排序后的数组如下：");
            randomArray.bubbleSort();
            randomArray.displayElements();
    
        }
    }