下面的类文件都在同一个包中。
/**
* 排序算法类的通用模板
*/
class SortExample {
/**
*比较两个Comparable对象的大小
* @param v: 第一个Comparable对象
* @param w: 第二个Comparable对象
* @return: v是否小于w
*/
static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}
/**
* 交换Comparable数组中的两个指定元素
* @param a: Comparable数组
* @param i: 第一个元素的索引
* @param j: 第二个元素的索引
*/
static void exch(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
/**
* 在单行中打印数组
* @param a: Comparable数组
*/
static void show(Comparable[] a){
for (Comparable c: a){
System.out.print(c + " ");
}
System.out.println();
}
/**
* 测试数组元素是否有序
* @param a: Comparable数组
* @return: 是否有序
*/
static boolean isSorted(Comparable[] a){
for (int i = 1; i < a.length; i++){
if (less(a[i], a[i - 1])){
return false;
}
}
return true;
}
}
冒泡排序
/**
* 冒泡排序
*/
public class BubbleSort {
/**
* 将数组a按照升序排列
* @param a: Comparable数组
*/
public static void sort(Comparable[] a){
int N = a.length;
//如果只有一个元素就不用排序了
if (N == 1){
return;
}
//控制冒泡排序的循环次数，每循环一次将剩余数组中最大的数飘到后面
for (int i = 0; i < N; i ++){
boolean flag = false; // 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了
for (int j = 0; j < N - i - 1; j ++){ //此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面
if (SortExample.less(a[j + 1], a[j])){ //这两个相邻的数是逆序的，交换
SortExample.exch(a, j, j + 1);
flag = true;
}
}
if (!flag){ //没有数据交换，数组已经有序，退出排序
break;
}
}
}
public static void main(String[] args) {
Integer[] a = {3, 5, 1, 9, 2, 11, 6, 8, 10, 7, 0, 4};
System.out.println("排序前:");
SortExample.show(a);
sort(a);
assert SortExample.isSorted(a);
System.out.println("排序后:");
SortExample.show(a);
}
}
image.png
时间复杂度：O(N^2)
空间复杂度：O(1)
是否稳定：是
是否为原地排序：是
插入排序
/**
* 插入排序(无需大量交换的改进版)
*/
class InsertionSort {
/**
* 将数组a按照升序排列
* @param a: Comparable数组
*/
private static void sort(Comparable[] a){
int N = a.length;
for (int i = 1; i < N; i ++){
Comparable temp = a[i];
int j;
//比要插入的元素大的元素后移一位
for (j = i; j > 0 && SortExample.less(temp, a[j - 1]); j --){
a[j] = a[j - 1];
}
a[j] = temp;
}
}
public static void main(String[] args) {
Integer[] a = {3, 5, 1, 9, 2, 11, 6, 8, 10, 7, 0, 4};
System.out.println("排序前:");
SortExample.show(a);
sort(a);
assert SortExample.isSorted(a);
System.out.println("排序后:");
SortExample.show(a);
}
}
image.png
时间复杂度：介于O(N)和O(N^2)之间， 取决于输入元素的排列情况
空间复杂度：O(1)
是否稳定：是
是否为原地排序：是
希尔排序
/**
* 希尔排序
*/
public class ShellSort {
/**
* 将数组a按照升序排列
* @param a: Comparable数组
*/
private static void sort(Comparable[] a){
int N = a.length;
int tab = N / 3; //子数组的个数/间隔
while (tab >= 1){
//分组
for (int i = 0;i < tab; i ++){
//进行插入排序
for (int j = i + tab; j < N; j += tab){
Comparable temp = a[j];
int k;
for (k = j; k >= tab && SortExample.less(temp, a[k - tab]); k -= tab){
a[k] = a[k - tab];
}
a[k] = temp;
}
}
tab /= 3;
}
}
public static void main(String[] args) {
Integer[] a = {3, 5, 1, 9, 2, 11, 6, 8, 10, 7, 0, 4};
System.out.println("排序前:");
SortExample.show(a);
sort(a);
assert SortExample.isSorted(a);
System.out.println("排序后:");
SortExample.show(a);
}
}
image.png
时间复杂度：O(NlogN)
空间复杂度：O(1)
是否稳定：否
是否为原地排序：是
归并排序
/**
* 归并排序(自顶向下)
*/
public class MergeSort {
private static Comparable[] aux; //归并所需的辅助数组
/**
* 将数组a按照升序排列
* @param a: Comparable数组
*/
public static void sort(Comparable[] a){
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
/**
* 将数组a按照升序归并
* @param a: 要归并的Comparable数组
* @param aux: 辅助数组
* @param low: 数组索引的下界
* @param mid: 数组索引的中位
* @param hig: 数组索引的上界
*/
private static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int hig){
int i = low; //前半部分数组的指针
int j = mid + 1; //后半部分数组的指针
//将a复制到aux
if (hig + 1 - low >= 0){
System.arraycopy(a, low, aux, low, hig + 1 - low);
}
//归并
for (int k = low; k <= hig; k ++){
if (i > mid){
a[k] = aux[j++];
}
else if (j > hig){
a[k] = aux[i++];
}
else if (SortExample.less(aux[i], aux[j])){
a[k] = aux[i++];
}
else {
a[k] = aux[j++];
}
}
}
/**
* 将数组a[low..hig]排序（递归）
* @param a: 要排序的Comparable数组
* @param low: 数组索引的下界
* @param hig: 数组索引的上界
*/
private static void sort(Comparable[] a, int low, int hig){
if (hig <= low){
return;
}
int mid = low + (hig - low) / 2;
sort(a, low, mid); //将左半边排序
sort(a, mid + 1, hig); //将右半边排序
merge(a, aux, low, mid, hig); //归并结果
}
public static void main(String[] args) {
Integer[] a = {3, 5, 1, 9, 2, 11, 6, 8, 10, 7, 0, 4};
System.out.println("排序前:");
SortExample.show(a);
sort(a);
assert SortExample.isSorted(a);
System.out.println("排序后:");
SortExample.show(a);
}
}
image.png
时间复杂度：O(NlogN)
空间复杂度：O(N)
是否稳定：是
是否为原地排序：否
快速排序
import edu.princeton.cs.algs4.StdRandom;
/**
* 快速排序（三向切分）
*/
public class QuickSort {
/**
* 将数组a按照升序排列
* @param a: Comparable数组
*/
public static void sort(Comparable[] a){
StdRandom.shuffle(a); //python中为random.shuffle(a)
sort(a, 0, a.length - 1);
}
/**
* 对数组a进行递归切分
* @param a: 要排序的Comparable数组
* @param low: 数组索引的下界
* @param hig: 数组索引的上界
*/
private static void sort(Comparable[] a, int low, int hig){
if (hig <= low){
return;
}
int left = low; //用于指示将小于切分元素的元素交换到左边的指针
int i = low + 1; //从左到右扫描的索引
int right = hig; //用于指示将大于切分元素的元素交换到右边的指针
Comparable v = a[low]; //切分元素
while (i <= right){
int cmp = a[i].compareTo(v);
if (cmp < 0){
SortExample.exch(a, left ++, i ++); //比切分元素小的元素放到切分元素的左边
}
else if (cmp > 0){
SortExample.exch(a, i, right --); //比切分元素大的元素放到切分元素的右边
}
else {
i ++; //和切分元素相等时跳过
}
}
sort(a, low, left - 1); //对数组左半边进行快速排序
sort(a, right + 1, hig); //对数组右半边进行快速排序
}
public static void main(String[] args) {
Integer[] a = {3, 5, 1, 9, 2, 11, 6, 8, 10, 7, 0, 4};
System.out.println("排序前:");
SortExample.show(a);
sort(a);
assert SortExample.isSorted(a);
System.out.println("排序后:");
SortExample.show(a);
}
}
image.png
时间复杂度：介于O(N)和O(NlogN)之间，运行效率由概率保证，同时也取决于输入元素的分布情况
空间复杂度：O(lgN)
是否稳定：否
是否为原地排序：是
堆排序
/**
* 堆排序
*/
public class HeapSort {
/**
* 由上至下的堆有序化（下沉）
* @param a: 用于建堆的数组
* @param currentRoot: 父节点的索引
* @param N: 数组的大小
*/
private static void sink(Comparable[] a, int currentRoot, int N){
while (2 * currentRoot + 1 < N){
int i = 2 * currentRoot + 1; //左子节点的索引
//找到较大的子节点
if (i + 1 < N && SortExample.less(a[i], a[i + 1])){
i ++;
}
//判断子节点是否比根节点大
if (!SortExample.less(a[currentRoot], a[i])){
break;
}
SortExample.exch(a, currentRoot, i); //交换
currentRoot = i; //根指针移到子节点
}
}
/**
* 将数组a按照升序排列
* @param a: Comparable数组
*/
public static void sort(Comparable[] a){
int N = a.length;
//建堆
for (int i = (N - 2) / 2; i >= 0; i --){
sink(a, i, N);
}
System.out.println("构建完成的大顶堆:");
SortExample.show(a);
//将大顶堆头结点（最大数）与最后一个元素交换位置，然后除去最后这个最大的元素，
//再sink操作维护该（除去最后一个元素的数组）堆为大顶堆。循环直到升序排序完成
for (int n = N - 1; n > 0; n --){
SortExample.exch(a, 0, n);
sink(a, 0, n);
}
}
public static void main(String[] args) {
Integer[] a = {3, 5, 1, 9, 2, 11, 6, 8, 10, 7, 0, 4};
System.out.println("排序前:");
SortExample.show(a);
sort(a);
assert SortExample.isSorted(a);
System.out.println("排序后:");
SortExample.show(a);
}
}
image.png
时间复杂度：(NlogN)
空间复杂度：O(1)
是否稳定：否
是否为原地排序：是
