排序算法之冒泡排序

概述

冒泡排序是比较常见的排序方法，它因排序过程中元素向水中的气泡慢慢浮上水面一样移动到数列的顶端，从而被成为冒泡排序。

原理

冒泡排序重复地遍历未排序的元素，依次比较相邻的两个元素，若这两个元素的顺序不是理想的顺序，则交换这两个元素的位置，直至最后一个未排列的元素。

步骤

  1. 从待排列队列的第一个元素开始，比较相邻元素的大小，若前者比后者大（升序排列时，降序排列时交换条件为前者比后者小），则交换两者的位置；
  2. 对待排序队列的每一对相邻元素依次进行相同的操作，直到最后一组，此时队列最后一个元素为最大的元素（升序排列时，降序排列时为最小的元素），同时，待排列队列里的元素数量减1；
  3. 对剩余待排序队列重复上述两步操作，直至待排序队列里的元素都排序完成。

Java实现

    public class BubbleSort {

        public int[] sort(int[] arr) {
            if (null == arr || arr.length <= 1) {
                return arr;
            }
        
            for(int i = 0; i < arr.length; i++) {
                for(int j = 0; i < arr.length - i - 1; j++) {
                    if(arr[i] > arr[i+1]) {
                        int temp = arr[i];
                        arr[i] = arr[i+1];
                        arr[i+1] = arr[i];
                    }   
                }
            }

            return arr;
        }
    }

留下评论