数据结构与算法--排序算法(冒泡、快速、堆)浅析

1、冒泡排序

冒泡排序的思想是，使用 n个 for循环重复遍历数组。每次 for循环从数组的第一个数开始逐个往后两两比较。如果是升序排序，那么每比较一个次就将最大的一个数移到后面（如果前大后小的话，两数互换）。直到把当次for循环中最大的数换到本次for循环数组的最后位置，然后将这个位置排除在外，进入下次循环。如此往复，直到数组内所有的数都有序。
看下图示意：

维基百科.gif

排序方法实现：

    /**
     * 冒泡
     * 
     * @param sort 
     * @return
     */
    public static Integer[] bubbleSort(Integer[] sort){
        int temp;
        for (int i = 0 ; i < sort.length ; i ++){
            for (int j = 0 ; j < sort.length - i -1 ; j ++ ){
                if (sort[j] > sort[j + 1]){
                    temp = sort[j];
                    sort[j] = sort[j + 1];
                    sort[j + 1] = temp;
                }
            }
        }
        Log.d("integerSort=" , "array=" + Arrays.toString(sort));
        return sort;
    }

时间复杂度：代码中使用了两个 for循环，每个for循环的时间复杂度是线性的O(n)。所以，两个for循环一嵌套，冒泡算法的时间复杂度是O(n²)。因为整个排序过程都在数组内，所以冒泡排序并没有使用额外的辅助空间。

2、快速排序

快速排序的思想是，将一段数组以选取的中值为分界，将数组中比中值大的值移到右边，比中值小的值移到左边。然后再以中值的位置将数组分成两段，每一段又按照上一步执行。如此递归，直到数组大小有序。

快速排序.gif

具体实现：

public static void quick(int[] sort){
        if (sort.length > 0) quickReal(sort , 0 , sort.length - 1);
        Log.d("integerSort=" , "Qui=" + Arrays.toString(sort));
    }
    private static void quickReal(int[] sortR , int low , int high){
        if (low < high){
            int middleIndex = quickMiddleSort(sortR , low , high); // 划分数组片段，并记录片段中值索引
            quickReal(sortR , low , middleIndex - 1); // 数组片段的下半部分进行递归
            quickReal(sortR , middleIndex + 1 , high); //数组片段的上半部分进行递归
        }
    }
    /************  将一段数组以中值为分界
     *                大的值移到中值右边
     *                小的移到左边
     *                该方法只是按中值大小将数组片段分成两半，
     *                并未实现彻底排序，还需进一步递归***************/
    private static int quickMiddleSort(int[] sortA , int low , int high){
        int middleTemp = sortA[low];  // 保存中值
        while (low < high){    //low和high相撞前一直循环
            while ((low < high) && (sortA[high] >= middleTemp)) {
                high --;  // 从高处往下遍历，遇到比中值小的值停止循环
            }
            sortA[low] = sortA[high];  //将比中值小的值放到低处
            while ((low < high) && (sortA[low] <= middleTemp)){
                low ++;   // 从低处向上遍历，碰到比中值大的值停止循环
            }
            sortA[high] = sortA[low]; //将比中值大的值移动到右边
        }
        sortA[low] = middleTemp;  // 还原中值
        return low;
    }

时间复杂度：理想情况下，每次划分所选择的中间数恰好将当前序列几乎等分，时间复杂度为O(nlog2n)。最坏情况下，每次所选的中间数是当前序列中的最大或最小元素，长度为n的数据表的快速排序需要经过n趟划分，时间复杂度为O(n2)。因此，快速排序的平均时间复杂度为O(nlog2n)。

3、堆排序

堆排序我们还是以升序排序为例来讲。在讲堆排序之前还是先讲讲堆得一些特性。堆分为大根堆和小根堆，大根堆的每一个父节点都大于或等于他的两个子节点，也就是一个堆里面，节点值大小是递减的。下面看看这种数据结构：

大根堆.png

上面我们看到，堆中的每一个父节点的值都大于或等于他的左右子节点。根据这一特性，就可以构造出一个堆数组。如上图所示，数组中的每个元素a[ i ]的左、右子节点分别是a[2 * i + 1]、a[2 * i + 2]。所以根据这一特性，我们就可以将这个数组进行堆排序。

堆排序的思想是这样的，第一步我们首先要将一个数组经过元素交换构造成上图的大根堆数组。这个交换的过程叫做下虑，也就是从左到右遍历所有父节点（非叶子节点），一旦发现有父节点的值小于子节点，那父节点和子节点就交换值。这样一轮下虑过后，这个数组就变成了大根堆数组。

第二步，我们将第一步构建成的大根堆数组的第一个数（根节点最大的数）和数组的最后一个数交换。也就是上图中的61和29交换位置。

第三步，我们再将交换后的上面数组角标为 8的61这个值排除在外，再次循环执行第一步下虑和第二步最大值交换操作。如此直到数组升序。

实现：

private static void heapSort(int[] sort){
        if (sort == null || sort.length < 2) return;
        for (int i = sort.length / 2 - 1 ; i >= 0 ; i --){
            percDown(sort , i , sort.length);
        }
        for (int i = sort.length - 1 ; i > 0 ; i --){
            swapValue(sort , 0 , i);
            percDown(sort , 0 , i);
        }

        Log.d("tag" , "heapSort=" + Arrays.toString(sort));
    }

    /**
     * 下虑
     *
     * @param sort
     * @param index
     * @param length
     */
    private static void percDown(int[] sort , int index , int length){
        Looper.loop();
        while (index * 2 + 1 < length){
            if ((index * 2 + 2 < length) && (sort[index * 2 + 1] < sort[index * 2 + 2])){
                if (sort[index] < sort[2 * 2 + 2])
                {
                    swapValue(sort , index , index * 2 + 2);
                    index = index * 2 + 2;
                }else break;
            }else if (sort[index] < sort[index * 2 + 1]){
                swapValue(sort , index , index * 2 + 1);
                index = index * 2 + 1;
            }else break;
        }
    }

    /**
     * 交换
     * 
     * @param sort 
     * @param one
     * @param two
     */
    private static void swapValue(int[] sort , int one , int two){
        int team = sort[one];
        sort[one] = sort[two];
        sort[two] = team;
    }

这次就只简单分析 3种，后续会继续搞搞别的排序算法。