排序算法是将一组数据按特定顺序（如升序、降序）重新排列的算法，核心评价指标为时间复杂度（数据规模与操作次数的关系）、空间复杂度（算法所需额外存储空间）和稳定性（相等元素排序后相对位置是否不变）。
一、常见排序算法分类
比较类排序：通过比较元素大小确定顺序，主流算法均属此类（如冒泡、快排）。
二、核心排序算法详解
1. 冒泡排序（Bubble Sort）
核心逻辑：重复遍历数组，每次比较相邻元素，将较大元素“冒泡”到末尾，直至无交换操作。
复杂度：时间复杂度 O(n²)（最坏/平均）、O(n)（最好，已排序数组加优化）；空间复杂度 O(1)（原地排序）。
稳定性：稳定（相等元素不交换）。
适用场景：小规模数据、几乎已排序的数据。
2. 快速排序（Quick Sort）
核心逻辑：选一个“基准”元素，将数组分为“小于基准”和“大于基准”两部分，递归排序子数组（分治思想）。
复杂度：时间复杂度 O(nlogn)（平均）、O(n²)（最坏，基准选极值）；空间复杂度 O(logn)（递归栈，平均）/ O(n)（最坏）。
稳定性：不稳定（基准交换可能打乱相等元素顺序）。
适用场景：大规模数据（实际应用中最快的排序之一，需优化基准选择）。
3. 插入排序（Insertion Sort）
核心逻辑：将数组分为“已排序”和“未排序”部分，依次将未排序元素插入已排序部分的正确位置。
复杂度：时间复杂度 O(n²)（最坏/平均）、O(n)（最好，已排序数组）；空间复杂度 O(1)（原地排序）。
稳定性：稳定（插入时不跨越相等元素）。
适用场景：小规模数据、几乎已排序的数据（如链表排序）。
4. 选择排序（Selection Sort）
核心逻辑：每次从“未排序”部分选最小（或最大）元素，与未排序部分的第一个元素交换，直至排序完成。
复杂度：时间复杂度 O(n²)（最坏/平均/最好，固定遍历次数）；空间复杂度 O(1)（原地排序）。
稳定性：不稳定（交换可能打乱相等元素顺序，如 [3, 2, 2]）。
适用场景：小规模数据、内存有限的场景（交换次数少）。
三、算法选择原则
1. 数据规模：小规模数据（n≤100）选冒泡、插入、选择；大规模数据（n≥1000）选快排、归并。
2. 稳定性需求：需稳定排序（如按“成绩”排序后保留“学号”顺序）选归并、插入、冒泡；无需求选快排、选择。
3. 内存限制：内存紧张选原地排序（快排、冒泡、插入、选择）；无限制可选归并（需额外空间）。
4. 数据初始状态：已排序或接近排序数据，选插入、冒泡（优化后）；无序数据选快排

代码练习

1.插入排序

//插入排序
    public void InsertSort(int[] arr)
    {
        int n=arr.length;
        //整体思路：从认为第一个元素有序开始，依次将后面的元素插入到这个有序序列中来，直到整个序列有序为止
        for(int i=1;i<n;i++)//从第二个元素开始遍历
        {
            int key = arr[i];//当前插入的元素
            int j = i - 1;
            while (j >= 0 && arr[j] > key)//将key插入到前面有序数组的合适位置
            {
                arr[j + 1] = arr[j];//把arr[j]后移一位
                j--;//j减1继续比较，直到找到合适的位置
            }
            arr[j + 1] = key;
        }
    }

2.选择排序

 //选择排序
    public void SelectSort ( 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索引处的值不是最小的，交换
                {
                    minIndex=j;
                }
            }
            //交换arr[i]和arr[minIndex]
            int temp=arr[i];
            arr[i]=arr[minIndex];
            arr[minIndex]=temp;
        }
    }

3.冒泡排序

 //冒泡排序
    public void  BubbleSort( int[] arr)
    {
        //整体思路：通过每一次循环的比较找到最大值
        int n=arr.length;
        //外层排序n-1次
        for(int i=0;i<n-1;i++)
        {
            //内层比较n-i-1次
            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;
                }
            }
        }
    }

4.快速排序

//快速排序
    public  static void QuickSort(int[] arr)//对外提供的排序方法，方便用户调用
    {
            QuickSort(arr,0,arr.length-1);
    }
    //用递归排序对数组进行分区，小于基准点的在左边，大于基准点的在右边
    private static int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[right];//选择最右边为基准点
        int i = left-1;//初始一个小于元素边界的变量
        for(int j=left;j<right;j++)
        {
            if(arr[j]<=pivot)//如果当前元素小于基准点
            {
                i++;
                //交换arr[i]和arr[j]，将小于基准点的元素放在前面
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //将基准点放在正确的位置上，既i+1
        int temp = arr[i+1];
        arr[i+1] = arr[right];
        arr[right] = temp;
        return i+1;//返回基准点的最终位置aaaaaalaakka
    }
//-------------------------------------------------------------------
    private  static  void QuickSort(int[] arr,int left,int right)//核心的递归排序方法，left表示当前排序的左边界，right表示用边界
    {
        if(left<right)
        {
            int pivot=Partition(arr,left,right);
            QuickSort(arr,left,pivot-1);//对基准点左边进行递归排序
            QuickSort(arr,pivot+1,right);//对基准点右边进行递归排序
        }
    }