排序算法总结

一、冒泡排序

/**
 * 冒泡排序
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 */
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = arr.length - 1; i > 0; --i) {  // 0 ~ arr.length-1
            for (int j = 0; j < i; ++j) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

二、选择排序

/**
 * 选择排序
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 */
import java.util.*;
public class SelectSort {
    public static void selectSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; ++i) { //遍历，逐轮放一个剩余数里最小的
            int minIndex = i; //遍历一遍后最小元素的下标
            for (int j = i + 1; j < arr.length; ++j) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

三、插入排序

/**
 * 插入排序
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 */
public class InsertSort {
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 0 ~ 0 有序
        // 0 ~ i 有序
        for (int i = 1; i < arr.length; ++i) { // 从1开始，0~0已经有序
            int end = i; // end之前的(0 ~ end-1)已经有序
            while (end - 1 >= 0 && arr[end - 1] > arr[end]) {
                swap(arr, end - 1, end);
                end--;
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

四、归并排序

/**
 * 归并排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(n)
 * 稳定性：稳定
 */
public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        if (left < right) {
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    public static void merge(int[] arr, int left, int mid, int right) { //左边有序和右边有序 归并
        int[] help = new int[right - left + 1]; // 辅助空间
        int i = 0;
        int p1 = left, p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= right) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; ++i) {
            arr[left + i] = help[i];
        }
    }
}

五、快速排序

/**
 * 快速排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn)
 * 稳定性：不稳定
 */
public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }
    // arr[L~R]上排好序
    public static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
            swap(arr, R, L + (int)(Math.random() * (R - L + 1))); // 随机选择切分元素pivot的下标，与最右边的进行交换
            int[] p = partition(arr, L, R);
            quickSort(arr, L, p[0] - 1);
            quickSort(arr, p[1] + 1, R);
        }
    }
    // 返回划分值等于区域的左边界和右边界,即[ p[0], p[1] ]之间的数等于pivot
    public static int[] partition(int[] arr, int L, int R) {
        int less = L - 1; // <区右边界
        int more = R; // >区左边界
        int pivot = arr[R];  // 划分值
        while (L < more) {  // L表示当前数位置
            if (arr[L] < pivot) {
                swap(arr, ++less, L++);
            }
            else if (arr[L] > pivot) {
                swap(arr, --more, L);
            }
            else {
                L++;
            }
        }
        swap(arr, more, R);
        return new int[]{less + 1, more};
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

六、堆排序

/**
 * 堆排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 */
public class HeapSort {
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; ++i) {  // O(N)
            heapInsert(arr, i); // O(logN)  整理成堆
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);  // 堆顶元素（当前最大）交换到数组末尾
        while (heapSize > 0) { // O(N)
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    public static void heapify(int[] arr, int index, int heapSize) {  // 某个数在index位置，能否往下移动
        int left = index * 2 + 1; // 左孩子下标
        while (left < heapSize) { // 下方还有孩子
            // 两个孩子中谁的值大，就把下标给largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 父节点和较大孩子之间，谁的值大，把下标给largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}