排序算法总结

稳定排序算法‌

稳定排序保证相等元素的‌相对顺序‌在排序后不变。常见算法包括：

‌冒泡排序‌

○ 通过相邻元素比较和交换，相等元素不会交换位置。时间复杂度为O(n²)，适合教学演示和小规模数据排序。

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // 交换相邻元素
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        
        bubbleSort(arr);
        
        System.out.println("\n排序后数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

插入排序‌

○ 将元素插入已排序序列时，遇到相等元素则停止在后方，保持顺序。通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。时间复杂度为O(n²)，适合小规模数据排序。

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // 将比key大的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("排序前数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        
        insertionSort(arr);
        
        System.out.println("\n排序后数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

‌归并排序‌

○ 合并时优先保留左子数组元素，确保稳定性。采用分治策略将数组分成两半分别排序，然后合并两个有序子数组。时间复杂度为O(n log n)。

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

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

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        
        System.arraycopy(temp, 0, arr, left, k);
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("排序前数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        
        mergeSort(arr);
        
        System.out.println("\n排序后数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

基数排序‌

○ 按位排序时依赖稳定的子排序算法（如计数排序）。通过按位分配和收集进行排序，时间复杂度为O(d*(n+k))，其中d是最大数字的位数，k是基数（这里是10）。特别适合整数排序且位数差异不大的情况。

public class RadixSort {
    // 获取数组中最大数的位数
    private static int getMaxDigits(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
        }
        return (int) Math.log10(max) + 1;
    }

    // 基数排序主方法
    public static void radixSort(int[] arr) {
        int maxDigits = getMaxDigits(arr);
        int n = arr.length;
        int[] output = new int[n];
        
        for (int exp = 1; exp <= maxDigits; exp++) {
            int[] count = new int[10];
            
            // 统计每个桶中元素个数
            for (int num : arr) {
                int digit = (num / (int) Math.pow(10, exp-1)) % 10;
                count[digit]++;
            }
            
            // 计算累计位置
            for (int i = 1; i < 10; i++) {
                count[i] += count[i-1];
            }
            
            // 将元素放入输出数组
            for (int i = n-1; i >= 0; i--) {
                int digit = (arr[i] / (int) Math.pow(10, exp-1)) % 10;
                output[count[digit]-1] = arr[i];
                count[digit]--;
            }
            
            // 将排序结果复制回原数组
            System.arraycopy(output, 0, arr, 0, n);
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("排序前数组:");
        for (int num : arr) System.out.print(num + " ");
        
        radixSort(arr);
        
        System.out.println("\n排序后数组:");
        for (int num : arr) System.out.print(num + " ");
    }
}

TimSort（Java中的对象排序）‌

○ Java的Arrays.sort()对对象数组使用TimSort，结合归并和插入排序，保证稳定性。

非稳定排序算法‌

非稳定排序可能打乱相等元素的相对顺序。常见算法包括：

‌快速排序‌

○ 分区过程中可能交换不相邻的相等元素。通过选取基准元素将数组分成两部分递归排序，平均时间复杂度O(n log n)。

public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

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

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("排序前数组:");
        for (int num : arr) System.out.print(num + " ");
        
        quickSort(arr);
        
        System.out.println("\n排序后数组:");
        for (int num : arr) System.out.print(num + " ");
    }
}

‌堆排序‌

○ 建堆和调整堆时，父子节点的交换可能改变顺序。 构建最大堆并反复提取堆顶元素完成排序，时间复杂度为O(n log n)。

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        
        // 构建最大堆
        for (int i = n/2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 逐个提取元素
        for (int i = n-1; i > 0; i--) {
            // 将当前根节点（最大值）移到数组末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            // 对剩余元素重新堆化
            heapify(arr, i, 0);
        }
    }
    
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;    // 初始化最大值为根节点
        int left = 2*i + 1; // 左子节点
        int right = 2*i + 2;// 右子节点
        
        // 如果左子节点大于根节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // 如果右子节点大于当前最大值
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // 如果最大值不是根节点
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            
            // 递归堆化受影响的子树
            heapify(arr, n, largest);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        
        heapSort(arr);
        
        System.out.println("\n排序后数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

选择排序‌

○ 每次选择最小元素并与当前位置交换，可能导致中间相等元素位移。通过不断选择剩余元素中的最小值并交换位置来完成排序，时间复杂度为O(n²)。

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n-1; i++) {
            // 找到未排序部分的最小元素索引
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // 将找到的最小元素与第一个未排序元素交换
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("排序前数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        
        selectionSort(arr);
        
        System.out.println("\n排序后数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

希尔排序‌

○ 按间隔分组插入排序，跨越式交换破坏稳定性。通过逐步缩小间隔对子序列进行插入排序，时间复杂度取决于间隔序列的选择。

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        
        // 初始间隔设为数组长度的一半，然后逐步缩小
        for (int gap = n/2; gap > 0; gap /= 2) {
            // 对每个间隔进行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {23, 12, 1, 8, 34, 54, 2, 3};
        System.out.println("排序前数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        
        shellSort(arr);
        
        System.out.println("\n排序后数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Java中的排序实现‌

‌对象数组/集合（如Collections.sort()）‌

○ 使用‌TimSort‌（稳定），因为需要保留对象属性的原始顺序。
○ 引入版本‌：Java 7 及以后。
○ ‌特点‌：TimSort 是一种混合排序算法，结合了‌归并排序‌和‌插入排序‌。它针对现实中的部分有序数据（如已部分排序或存在有序子序列的数组）进行了优化，具有较好的实际性能。

基本类型数组（如Arrays.sort(int[])）‌

○ 使用‌双轴快速排序‌（Dual-Pivot Quicksort，非稳定），因基本类型相同值无需区分顺序，优先效率。