经典排序算法

冒泡排序

• 原理
  基于比较的排序算法,每次都从下标为0的位置开始,依次比较相邻的两个元素(下标为i和下标为i+1的),如果下标为i的元素大于下标为i+1的元素,则交换两个元素,以此类推,每次循环比较,都会把一个元素交换到该放的位置.
• 最好时间复杂度:O(N)
• 最坏时间复杂度:O(N^2)
• 空间复杂度:O(1)
• 是稳定排序算法

 public static void bubbleSort(int[] a) {
        boolean swap = false;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    swap = true;
                    int t = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = t;
                }
            }
            if (!swap) break;
        }
    }

插入排序法

• 原理
  将待排序的数组分为前后两部分:前半部分为已排序数组,后半部分是未排序数组,每次在处理未排序数组的第一个元素时都从已排序数组中找到该元素应该插入的位置,查找的方法就是依次向后移动比该元素大的元素.

• 时间复杂度:O(n^2)
• 空间复杂度:插入排序算法是本地排序,空间复杂度为O(1)
• 插入排序是稳定排序

 public static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int j = i - 1;
            int target = a[i];
            for (; j >= 0; j--) {
                if (a[j] > target) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = target;
        }
    }

选择排序法

• 原理
  和插入排序法同样将数组分为待排序和已排序两部分,在每次排序时,都选择待排序数组中最小的元素与此元素交换位置.

• 选择排序法时间复杂度:O(N^2)
• 选择排序法的空间复杂度:O(1)
• 选择排序不是稳定排序算法.

 public static void selectionSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int minValueIndex = i;
            int minV = a[i];
            for (int j = i; j < a.length; j++) {

                if (a[j] < minV) {
                    minValueIndex = j;
                    minV = a[j];
                }
            }
            int t = a[i];
            a[i] = a[minValueIndex];
            a[minValueIndex] = t;
        }
    }

归并排序算法

• 原理
  归并排序的原理是把一个数组拆成两个子数组,并且这两个子数组分别有序的情况下,只需要将这两个有序的子数组归并为一个有序的数组即可.归并排序使用递归的方式实现.
• 递推公式：

mergeSort(a,0,r) = merge(mergeSort(a,0,q), mergeSort(a,q+1,r))
终止条件：
p >= r 不用再继续分解

• 归并排序的时间复杂度 O(N*log(N))
• 归并排序的空间复杂度O(N)

public static void mergeSort(int[] a, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int mid = (startIndex + endIndex) / 2;

        mergeSort(a, startIndex, mid);
        mergeSort(a, mid + 1, endIndex);
        merge(a, startIndex, mid, endIndex);
   }
    private static void merge(int[] a, int startIndex, int mid, int endIndex) {
        int i = startIndex, j = mid + 1;
        if (i >= j) {
            return;
        }
        int[] tmp = new int[endIndex - startIndex + 1];
        int k = 0;
        while (i <= mid && j <= endIndex) {

            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
            }
        }

        if (i <= mid || j <= endIndex) {
            int start = i <= mid ? i : j;
            int end = i <= mid ? mid : endIndex;
            for (; start <= end; start++) {
                tmp[k++] = a[start];
            }

        }
        for (int m = 0; m < tmp.length; m++) {
            a[m + startIndex] = tmp[m];
        }
    }

快排

• 原理
  快排的思想是如果要排序数组a中从下标p到下标r的数据， 从p到q之间选择任意一个点作为分界点（pivot），我们遍历p到r之间的数据，把小于pivot的点放在左边，把大于pivot的点放在右边，将pivot放在中间。经过这个步骤之后，我们就把数据分成三部分，小于pivot的、等于pivot的和大于pivot的。我们认为pivot的下标为q。
  根据递归分治的思想，用递归处理下标p到q-1、和q到r之间的数据，直到区间大小缩小为1，说明整个数组就是有序的了。
• 时间复杂度：O(N*log(N))
• 空间复杂度：快排是原地排序，空间复杂度为O(1)

public static void quickSort(int[] a, int p, int r) {

        if (p >= r) {
            return;
        }
        int q = partition(a, p, r);
        quickSort(a, p, q - 1);
        quickSort(a, q + 1, r);
    }

    private static int partition(int[] a, int p, int r) {

        int pivot = a[r];
        int i = p;
        int j = p;
        for (; j < r; j++) {
            if (a[j] > pivot) {
                int tmp = a[j];
                a[j] = a[i];
                a[i] = tmp;
                i++;
            }
        }
        int tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;
        return i;
    }

堆排序

堆有以下两个特性：

• 堆，首先是棵完全二叉树，所以对适合使用数组存储
• 堆中的节点都大于等于该节点下所有子节点
• 当堆的顶点大于堆中所有子树的节点时，这个堆是大顶堆
• 当堆得顶点小于堆中所有子树的节点时，这个堆是小顶堆

使用堆排序有两个过程，建堆+排序

• 建堆的过程是两种：
  • 从数组下标0开始为初始堆，依次向堆中添加元素，不断堆化，最后所有的元素都加到堆里
  • 如代码buildHeap

• 堆排序，建堆之后的结构是个大顶堆，数组中的第一个元素就是堆顶的元素，也就是最大的，把它和下标为n的元素对换，那么就把最大的元素放到下标为n的位置了，把原来下标为n的元素放到堆顶。这就是相当于删除了堆顶元素，然后再把剩余的n-1个元素进行堆化，建堆之后，再把堆顶的元素放到下标为n-1的位置，以此类推重复这个过程，直到堆中只有一个元素时，那么堆排序就完成了。

public class Heap {
    private int[] a; // 数组，从下标 1 开始存储数据
    private int n;  // 堆可以存储的最大数据个数
    private int count; // 堆中已经存储的数据个数
 public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

 private void buildHeap(int[] a, int n) {
        for (int i = n / 2; i >= 1; --i) {
            heapify(a, n, i);
        }
    }
 private void heapify(int[] a, int n, int i) { // 自上往下堆化
        while (true) {
            int maxPos = i;
            if (i * 2 <= n && a[i] < a[i * 2]) maxPos = i * 2;
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1;
            if (maxPos == i) break;
            swap(a, i, maxPos);
            i = maxPos;
        }
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    // n 表示数据的个数，数组 a 中的数据从下标 1 到 n 的位置。
    public void sort(int[] a, int n) {
        buildHeap(a, n);
        int k = n;
        while (k > 1) {
            swap(a, 1, k);
            --k;
            heapify(a, k, 1);
        }
    }