排序算法.md

    public static int[] swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        return nums;
    }

1.快速排序

核心的思路是取第一个元素（或者最后一个元素）作为分界点，把整个数组分成左右两侧，左边的元素小于或者等于分界点元素，而右边的元素大于分界点元素，然后把分界点移到中间位置，对左右子数组分别进行递归，最后就能得到一个排序完成的数组。当子数组只有一个或者没有元素的时候就结束这个递归过程。

    public static void quickSort(int[] nums, int left, int right) {
        if (left > right) return;
        int key = nums[left];
        int l = left;
        int r = right;
        while (l < r) {
            while (nums[r] >= key && l < r)
                r--;
            while (nums[l] <= key && l < r)
                l++;
            if (l < r)
                swap(nums, r, l);
        }

        nums[left] = nums[r];
        nums[r] = key;

        quickSort(nums, left, r - 1);
        quickSort(nums, r + 1, right);
    }

2.归并排序

归并排序是建立在归并操作上的一种有效排序算反，采用的是分治思想。这一算法充分利用了完全二叉树深度是log2(n+1)的特性，因此效率比较高。其基本原理如下：

对于给定的一组记录，利用递归与分支技术将数据划分为越来越小的半子表，再对班子表排序，最后利用递归方法将排序好的半子表合并为越来越大的有序表。

经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录与第二个位置记录交换；重复这个过程直到进行比较的记录剩下一个为止。

动画演示

    public static void mergeSort(int[] a, int left, int right) {
        int mid = left + (right - left) / 2;
        if (left < right) {
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }

    public static void merge(int[] a, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int leftPointer = left;
        int rightPointer = mid + 1;
        int i = 0;
        while (leftPointer <= mid && rightPointer <= right) {
            if (a[leftPointer] <= a[rightPointer]) {
                temp[i++] = a[leftPointer++];
            } else {
                temp[i++] = a[rightPointer++];
            }
        }
        while (leftPointer <= mid) {
            temp[i++] = a[leftPointer++];
        }
        while (rightPointer <= right) {
            temp[i++] = a[rightPointer++];
        }
        if (temp.length >= 0) {
            System.arraycopy(temp, 0, a, left, temp.length);
        }
    }

参考连接

3.冒泡排序

冒泡排序从左到右依次比较两个相邻的元素，如果前一个元素比较大，就把前一个元素和后一个元素交换位置，完成一趟循环后保证了最大的元素在最后一位。接下来进行第二趟排序，第二趟排序完成后第二大的元素在倒数第二位。依次遍历直至整个数组排序完成。

冒泡排序的时间复杂度是O(n2),空间复杂度为

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