关于数据结构中排序算法的总结2

1、快速排序 ( 时间复杂度O(nlogn) )

　　它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

　　/**
     * 快速排序(升序)
     * */
    public static void quickSort(int[] arr, int lowIndex, int highIndex) {
        if (lowIndex < highIndex) {
            int axisIndex = partAndReturnPos(arr, lowIndex, highIndex);
            quickSort(arr, lowIndex, axisIndex - 1);
            quickSort(arr, axisIndex + 1, highIndex);
        }
    }

    /**
     * 快排分组 并 返回轴的下标
     * 
     */
    public static int partAndReturnPos(int[] arr, int lowIndex, int highIndex) {
        // 选取一个轴元素
        int axis = arr[lowIndex];
        while (lowIndex < highIndex) {
            while (lowIndex < highIndex && arr[highIndex] >= axis) {
                highIndex--;
            }
            // 找到比轴小的元素 将该元素放到轴的左边
            arr[lowIndex] = arr[highIndex];
            while (lowIndex < highIndex && arr[lowIndex] <= axis) {
                lowIndex++;
            }
            // 找到比轴大的元素 将该元素放到轴的右边
            arr[highIndex] = arr[lowIndex];
        }
        // 找到轴的位置
        arr[lowIndex] = axis;
        return lowIndex;
    }

2、归并排序 ( 时间复杂度O(nlogn) )

　　归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

　　/**
     * 归并排序(升序)
     * */
    public static void mergeSort(int[] arr, int lowIndex, int highIndex) {
        if (lowIndex < highIndex) {
            int midIndex = (lowIndex + highIndex) / 2;
            mergeSort(arr, lowIndex, midIndex);
            mergeSort(arr, midIndex + 1, highIndex);
            binaryMerge(arr, lowIndex, midIndex, highIndex);
        }
    }

    /**
     * 二路归并操作
     * */
    public static void binaryMerge(int[] arr, int lowIndex, int midIndex, int highIndex) {
        // 左边数组的长度
        int lengthOfLeft = midIndex - lowIndex + 1;
        // 右边数组的长度
        int lengthOfRight = highIndex - midIndex;
        // 定义两个临时数组 保存左右两边的数据
        int[] arrLeft = new int[lengthOfLeft + 1];
        int[] arrRight = new int[lengthOfRight + 1];
        for (int i = 0; i < lengthOfLeft; ++i) {
            arrLeft[i] = arr[lowIndex + i];
        }
        for (int i = 0; i < lengthOfRight; ++i) {
            arrRight[i] = arr[midIndex + 1 + i];
        }
        arrLeft[arrLeft.length - 1] = arrRight[arrRight.length - 1] = Integer.MAX_VALUE;
        // 开始归并操作
        int i = 0, j = 0;
        for (int k = lowIndex; k <= highIndex; ++k) {
            if (arrLeft[i] < arrRight[j]) {
                arr[k] = arrLeft[i++];
            } else {
                arr[k] = arrRight[j++];
            }
        }
    }

3、堆排序 ( 时间复杂度O(nlogn) )

　　堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

　　/**
     * 堆排序(升序)
     * */
    public static void heapSort(int[] arr) {
        // 从最后一个非叶子节点(length/2-1)调整序列的前半部分元素 以构建一个堆
        for (int i = arr.length / 2 - 1; i >= 0; --i) {
            adjustHeap(arr, arr.length, i);
        }
        // 开始排序
        for (int i = arr.length - 1; i > 0; --i) {
            // 把第一个元素和当前的最后一个元素交换
            int t = arr[0];
            arr[0] = arr[i];
            arr[i] = t;
            // 将剩下的元素再次调整成大根堆
            adjustHeap(arr, i, 0);
        }
    }

    /**
     * 调整堆元素
     * 
     * @param arr
     * @param length
     *            堆的长度
     * @param i
     *            待调整的元素下标
     */
    public static void adjustHeap(int[] arr, int length, int i) {
        // 左孩子下标
        int leftChildIndex = 2 * i + 1;
        // 右孩子下标
        int rightChildIndex = leftChildIndex + 1;
        // 较大孩子的下标
        int biggerChildIndex;
        while (leftChildIndex < length) {
            biggerChildIndex = leftChildIndex;
            if (rightChildIndex < length && arr[rightChildIndex] > arr[leftChildIndex]) {
                biggerChildIndex = rightChildIndex;
            }

            // 如果较大的孩子大于父结点那么交换
            if (arr[i] < arr[biggerChildIndex]) {
                int t = arr[i];
                arr[i] = arr[biggerChildIndex];
                arr[biggerChildIndex] = t;
            } else {
                // 节点没有交换则跳出循环
                break;
            }
            // 节点做了交换 则继续调整
            i = biggerChildIndex;
            // 计算左右孩子
            leftChildIndex = 2 * i + 1;
            rightChildIndex = leftChildIndex + 1;
        }
    }

4、希尔排序 ( 时间复杂度O(n^1.3) )

　　希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

　　/**
     * 希尔排序
     * */
    public static void shellSort(int[] arr) {
        // 待插入的元素
        int insertingVal;
        // 增量
        int gap = arr.length;

        do {
            gap = gap / 3 + 1;
            for (int i = gap; i < arr.length; i++) {
                // 保存待插入的元素
                insertingVal = arr[i];

                int j = i - gap;
                while (j >= 0 && arr[j] > insertingVal) {
                    arr[j + gap] = arr[j];
                    j = j - gap;
                }
                arr[j + gap] = insertingVal;
            }
        } while (gap > 1);
    }

关于数据结构中排序算法的总结2

推荐阅读