【数据结构和算法】十几种排序算法，图文详解

1，快速排序

快速排序原理是首先要找到一个中枢，把小于中枢的值放到他前面，大于中枢的值放到他的右边，然后再以此方法对这两部分数据分别进行快速排序。先看一下代码

    public int[] MySort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    private void quickSort(int[] array, int start, int end) {
        if (start < end) {
            int key = array[start];//用待排数组的第一个作为中枢
            int i = start;
            for (int j = start + 1; j <= end; j++) {
                if (key > array[j]) {
                    swap(array, j, ++i);
                }
            }
            array[start] = array[i];//先挪，然后再把中枢放到指定位置
            array[i] = key;
            quickSort(array, start, i - 1);
            quickSort(array, i + 1, end);
        }
    }

    //交换两个数的值
    public void swap(int[] A, int i, int j) {
        if (i != j) {
            A[i] ^= A[j];
            A[j] ^= A[i];
            A[i] ^= A[j];
        }
    }

这里是先用待排数组的第一个作为中枢，把数组划分两部分，小于他的往前挪，那大于他的自然就在后面了，然后再把中枢值放到大于和小于他之间的位置。 快速排序其实有很多变种，这里就不在一一看了，想了解的可以看下《104，排序-快速排序》

2，归并排序

归并排序是把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列 代码如下

    public int[] MySort(int[] arr) {
        int i = 1;
        while (i < arr.length) {
            //原理很简单，就是先两个两个合并，然后4个，然后8个……
            for (int j = 0; j + i < arr.length; j += 2 * i) {
                merge(arr, j, j + i - 1, Math.min(j + 2 * i - 1, arr.length - 1));
            }
            i = i << 1;
        }
        return arr;
    }

    private void merge(int[] data, int left, int center, int right) {
        int length = right - left + 1;
        int[] tmp = new int[length];
        int tempIndex = 0;
        //_left是前半部分开始的位置，_right是后半部分开始的位置
        int _left = left;
        int _right = center + 1;
        while (_left <= center && _right <= right) {
            if (data[_left] <= data[_right]) {
                tmp[tempIndex++] = data[_left++];
            } else {
                tmp[tempIndex++] = data[_right++];
            }
        }
        while (_right <= right) {
            tmp[tempIndex++] = data[_right++];
        }
        while (_left <= center) {
            tmp[tempIndex++] = data[_left++];
        }
        tempIndex = 0;
        while (tempIndex < length) {
            data[left + tempIndex] = tmp[tempIndex++];
        }
    }

3，堆排序

堆排序，也可以理解为二叉树排序，这里的堆分为两种，一种是大顶堆，一种是小顶堆，我们所有的排序方法都以升序为主，其实倒序原理也都差不多，所以这里我们主要分析的是大顶堆。大顶堆就是根节点不小于他的两个子节点，

代码如下

    public int[] MySort(int[] arr) {
        int length = arr.length;
        buildMaxHeap(arr, length);
        for (int i = 0; i < length; i++) {
            swap(arr, 0, length - 1 - i);
            maxHeapfy(arr, 0, length - i - 1);
        }
        return arr;
    }

    private void maxHeapfy(int[] arr, int i, int heapSize) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int largest = i;
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {//把最大值给父节点
            swap(arr, largest, i);
            maxHeapfy(arr, largest, heapSize);
        }
    }

    private void buildMaxHeap(int[] array, int heapSize) {
        //从最后一个非叶子节点开始循环
        for (int i = (heapSize - 2) >> 1; i >= 0; i--) {
            maxHeapfy(array, i, heapSize);
        }
    }

    public void swap(int[] A, int i, int j) {
        if (i != j) {
            A[i] ^= A[j];
            A[j] ^= A[i];
            A[i] ^= A[j];
        }
    }

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解