排序算法

1. 冒泡排序（Bubble Sort）

思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。直到比较到最后两个数，一趟排序结束，这样最后一个数一定是数组中最大的一个数，这个数下一次不用参与比较。依次类推，直到排序完成。（ 比较相邻元素，直到序列变为有序为止）

static void sort(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]){
                    swap(a, j, j + 1);
                }
            }
        }
    }

改进：主要是增加了标志位，在数组已经有序后直接跳出循环。

static void sort(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            //增加标志位，标记该趟排序中是否有数被交换，若没有，则说明数组已经是有序的了，可以跳出循环
            boolean isSorted = false;
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]){
                    swap(a, j, j + 1);
                    isSorted = true;
                }
            }
            if (!isSorted){
                break;
            }
        }
    }

再次改进：主要是界定了数组有序区，减少了比较次数。

static void sort(int[] a) {
        //最后一次元素交换的位置
        int lastSwapIndex = 0;
        //界定数列有序区
        int sortBorder = a.length - 1;
        for (int i = a.length - 1; i > 0; i--) {
            //增加标志位，标记该趟排序中是否有数被交换，若没有，则说明数组已经是有序的了，可以跳出循环
            boolean isSorted = false;
            //后面的数组已经有序，无需判断
            for (int j = 0; j < sortBorder; j++) {
                if (a[j] > a[j + 1]){
                    swap(a, j, j + 1);
                    isSorted = true;
                    lastSwapIndex = j;
                }
            }
            sortBorder = lastSwapIndex;
            if (!isSorted){
                break;
            }
        }
    }

2. 快速排序（Quick Sort）

思路：从左往右找到第一个比中轴大的数，从右往左找到第一个比中轴小的数，交换这两个数。采用分治的思想，递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

static void sort(int[] a,int leftRound,int rightRound) {
    if (leftRound >= rightRound) {
        return;
    }
    int mid = partition(a, leftRound, rightRound);
    sort(a, leftRound, mid - 1);
    sort(a, mid + 1, rightRound);
}

static int partition(int[] a, int leftRound, int rightRound) {
    int pivot = a[rightRound];
    int left = leftRound;
    int right = rightRound - 1;
    while (left <= right) {
        while (a[left] <= pivot && left <= right) {
            left++;
        }
        while (a[right] > pivot && left <= right) {
            right--;
        }
        if (left < right) {
            swap(a, left, right);
        }
    }
    swap(a, left, rightRound);
    return left;
}

3. 归并排序（Merge Sort）

思路：分解（Divide）：将n个元素分成两个含n/2个元素的子序列。
解决（Conquer）：用合并排序法对两个子序列递归的排序。
​ 合并（Combine）：合并两个已排序的子序列已得到排序结果。
若是两个已经排好序的数组，我们只需要从头比较各个元素的大小，小的放到新开辟的数组中即可。

static void sort(int[] a, int left, int right) {
    if (left == right)return;
    //分成两半
    int mid = left + (right - left) / 2;
    //左边排序
    sort(a, left, mid);
    //右边排序
    sort(a, mid + 1, right);
    merge(a, left, mid + 1, right);
}

static void merge(int[] a, int leftPtr, int rightPtr, int rightRound) {
    int mid = rightPtr - 1;
    int[] temp = new int[rightRound - leftPtr + 1];
    int i = leftPtr;
    int j = rightPtr;
    int k = 0;
    while (i <= mid && j <= rightRound) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    while (j <= rightRound) {
        temp[k++] = a[j++];
    }
    for (int m = 0; m < temp.length; m++) {
        a[leftPtr + m] = temp[m];
    }
}

4. 堆排序

static void heapSort(int[] array) {
        if (array.length == 0) return;
        int length = array.length;
        //建立堆
        for (int i = length - 1 / 2; i >= 0; i--) {
            heapify(array, length, i);
        }
        //取出堆顶元素，再调整堆
        for (int i = length - 1; i > 0; i--) {
            swap(array, 0, i);
            heapify(array, i, 0);
        }
    }
    
    //调整堆
    static void heapify(int[] array, int length, int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < length && array[left] > array[largest]) {
            largest = left;
        }
        if (right < length && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(array, largest, i);
            heapify(array, length, largest);
        }
    }