冒泡 快排 堆排

冒泡排序

原理：一遍循环与旁边的比较找到最大（最小）放到后面，多趟排序之后就成为一个有序的队列。

冒泡排序示意图.png

 //冒泡排序
    public int[] bubbleSort(int[] array){
        int size = array.length;
        int temp ;
        //排序趟数
        for(int i = 0 ; i < size-1 ; i++){
            //找到最大值，不断比较，交换位置
            for(int j = 0 ; j < size-1-i ; j++)
                if(array[j] > array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
        }
        return array;
    }

冒泡循环中有嵌套两个for，所以时间复杂度是O(n^2)

快速排序

原理：在一堆数中取一个base值，一般第一个数为base值，第一个位置为LeftIndex，最后一个位置为RightIndex。然后从RightIndex向前比较，如果比base值小，就交换位置并从LeftIndex向后比较；如果比base值大就RightIndex--。当从LeftIndex开始向后比较base值，如果比base值大，就交换并又从RightIndex向前比较；否则LeftIndex++。当LeftIndex == RightIndex时，两边递归重复上面的操作。

快速排序示意图.png

代码实现

 /**
     * 1.取一个基准
     * 2.从end-》start方向，比基准小的，交换end位置的数字和基准
     * 3.从start-》end方向，比基准大的，交换start位置的数字和基准
     * 4.当start==end后，分治递归两边
     * */
    public void quickSort(int[] array , int i , int j){
        if(i >= j)
            return;
        int start = i;
        int end = j;
        int base = array[start];
        boolean backOrForward = true;
        while (start < end){
            if(backOrForward){
                if(array[end] < base){
                    array[start] = array[end];
                    array[end] = base;
                    backOrForward = false;
                    start++;
                }else{
                    end--;
                }
            }else{
                if(array[start] > base){
                    array[end] = array[start];
                    array[start] = base;
                    backOrForward = true;
                    end--;
                }else{
                    start++;
                }
            }
        }
        Log.i(TAG, "quickSort: end = " + end + ",start = " + start);
        int part = start;
        quickSort(array,i,part-1);
        quickSort(array,part+1,j);
    }

快速排序平均时间复杂度O(n*log2n)

堆排序

原理：把数组想象成一个二叉树，从最后一个有叶儿节点的位置（length /2 - 1）开始，比较左孩子（2index+1）右孩子（2index+2），将大的放到节点，这样一遍循环下来就构成了一个最大堆，最后将第一个位置和最后一个位置交换，最大数就到最后一位。每次都形成最大堆，就成为有序的一个数组

构建二叉树.png 比较左右孩子.png 比较左右孩子.png

代码实现

/**
     * start = 0 起始位置
     * end为需要排序最后一个位置，及数组长度
    **/
    public void heapSort(int[] array,int start,int end){
        int length = array.length;
        int index , temp;
        for(int i = 0 ; i < length ; i++ ){
            index = (end+1) / 2 - 1;
            for(int j = index ; j >=0 ; j-- ){
                int left = 2 * j + 1;//左孩子
                int right = 2 * j + 2;//右孩子
                if(left <= end && array[left] > array[j]){
                    temp = array[j];
                    array[j] = array[left];
                    array[left] = temp;
                }
                if(right <= end && array[right] > array[j]){
                    temp = array[j];
                    array[j] = array[right];
                    array[right] = temp;
                }
            }
            //完成最大堆，最大放到最后
            temp = array[end];
            array[end] =  array[start];
            array[start] = temp;
            //需要排序的最堆数量减少一个
            end--;
        }
    }

堆排序的时间复杂度O(n*log2n)