归并排序

public static void mergeSort(int[] a) {
        mergeSort(a, 0, a.length - 1);
}

public static void mergeSort(int[] a, int start, int end) {
    // 递归出口：数组长度为1时
    if (start >= end) {
        return;
    }
    // 取中点
    int mid = start + (end - start) / 2;
    // 递归排序左半部分
    mergeSort(a, start, mid);
    // 递归排序右半部分
    mergeSort(a, mid + 1, end);
    // 运行到这里时 [start, mid] [mid + 1, end]已经各自有序 将两个有序数组合并为一个
    merge(a, start, mid, end);
}

public static void merge(int[] a, int start, int mid, int end) {
    int i = start, j = mid + 1, k = 0;
    // 需要创建临时数组存储数组 因为同一时间内只会创建一个数组(只有位于线程的栈的顶部的方法才会被运行) 所以空间复杂度为O（n）
    int[] temp = new int[end - start + 1];
    while (i <= mid && j <= end) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    while (j <= end) {
        temp[k++] = a[j++];
    }
    k = 0; i = start;
    while (i <= end) {
        a[i++] = temp[k++];
    }
}

快速排序

public static void quickSort(int[] a) {
    quickSort(a, 0, a.length - 1);
}

public static void quickSort(int[] a, int start, int end) {
    // 递归出口：数组长度为1
    if (start >= end) {
        return;
    }
    // 分区方法：将数组分为三个部分 前半部分的所有数均小于a[pivot] 后半部分的数均大于a[pivot]
    int pivot = partition(a, start, end);
    // 递归排序前半部分
    quickSort(a, start, pivot - 1);
    // 递归排序后半部分
    quickSort(a, pivot + 1, end);
}

public static int partition(int[] a, int start, int end) {
    // 取最后一个数为pivot
    int pivot = a[end];
    // 使得[start, i-1]中的所有数为小于pivot的
    int i = start;
    for (int j = start; j < end; j++) {
        if (a[j] < pivot) {
            swap(a, i, j);
            i++;
        }
    }
    // 将最后一个数放到分割的位置上
    swap(a, i, end);
    // 返回其索引
    return i;
}

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


// 快速选择 找到无序数组中第k大的数
public static int findKthLargest(int[] a, int k) {
        return quickSelect(a, 0, a.length - 1, a.length - k);
    }

    public static int quickSelect(int[] a, int start, int end, int k) {
        if (start >= end) {
            return start;
        }
        int pivot = partition(a, start, end);
        if (pivot == k) {
            return a[pivot];
        } else if (pivot > k) {
            return quickSelect(a, start, pivot - 1, k);
        } else {
            return quickSelect(a, pivot + 1, end, k);
        }
    }

    public static int partition(int[] a, int start, int end) {
        int pivot = a[end];
        int i = start;
        for (int j = start; j < end; j++) {
            if (a[j] < pivot) {
                swap(a, i, j);
                i++;
            }
        }
        swap(a, i, end);
        return i;
    }

计数排序

/**
 * 要求数组中的元素为非负数 且范围不能太大
 */
public static void countingSort(int[] a) {
   // 确定范围
   int max = a[0];
   int len = a.length;
    for (int i = 1; i < len; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    // 计算每个元素的个数
    int[] count = new int[max + 1];
    for (int num : a) {
        count[num]++;
    }
    // 累加个数 count[i]中的值为 <=i的数个数
    for (int i = 1; i <= max; i++) {
        count[i] = count[i - 1] + count[i];
    }
    int[] temp = new int[len];
    // 从后向前遍历 将元素插入到相应位置
    for (int i = len - 1; i >= 0; i--) {
        temp[--count[a[i]]] = a[i];
    }
    System.arraycopy(temp, 0, a, 0, len);
}

/**
 * 假设我们现在需要对 D，a，F，B，c，A，z 这个字符串进行排序，
 * 要求将其中所有小写字母都排在大写字母的前面，
 * 但小写字母内部和大写字母内部不要求有序。
 * 比如经过排序之后为 a，c，z，D，F，B，A，这个如何来实现呢？
 * 如果字符串中存储的不仅有大小写字母，还有数字。
 * 要将小写字母的放到前面，大写字母放在最后，数字放在中间，
 * 不用排序算法，又该怎么解决呢？
 */
public static void sortChar(char[] c) {
    // 双指针
    int i = 0, j = c.length - 1;
    while (i < j) {
        while (Character.isLowerCase(c[i])) {
            i++;
        }
        while (!Character.isLowerCase(c[j])) {
            j--;
        }
        if (i >= j) {
            break;
        }
        swap(c, i, j);
        i++;
        j--;
    }
    j = c.length - 1;
    while (i < j) {
        while (Character.isDigit(c[i])) {
            i++;
        }
        while (Character.isUpperCase(c[j])) {
            j--;
        }
        if (i >= j) {
            break;
        }
        swap(c, i, j);
        i++;
        j--;
    }
}

public static void swap(char[] c, int i, int j) {
    char temp = c[i];
    c[i] = c[j];
    c[j] = temp;
}