Java实现三大经典排序算法

0x01 前言

最近又开始review一下JavaSE的知识，才发现之前学的三大经典排序算法–冒泡排序、选择排序和插入排序 的实现还是有些许的不足，所以重新实现了一下，顺便也复习一下JavaSE的知识。

0x02 冒泡排序

排序具体步骤：

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素为最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个(如果第N轮，则为倒数N个)；
• 重复以上步骤，直到排序完成。

具体流程图：

代码实现：

//冒泡排序
public void bubbleSort(int... arr){
    boolean exchange_flag; //用于判断是否发生交换
    for(int j=0;j<arr.length-1;j++){ //控制第几轮循环
        exchange_flag = false;
        for(int i=0;i<arr.length-1-j;i++){ //遍历比较
            //如果前一个比后一个大则互换位置
            if(arr[i]>arr[i+1]){
                //交换两个元素
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                exchange_flag = true;
            }
        }
        //如果未发生交换则跳出循环
        if(!exchange_flag){
            break;
        }
    }
    
}

时间复杂度分析：

• 最好情况：如果待排序的数组已经是有序的，那么只需要进行一次遍历，时间复杂度为 O(n)；
• 最坏情况：如果待排序的数组是逆序的，那么需要n-1轮遍历，每一轮遍历需要比较n-i次，时间复杂度为O(n^2)；

0x03 选择排序

排序具体步骤：

• 从数组的第一个位置开始，认为当前元素是最小值。
• 在当前元素之后的未排序部分中，逐个比较，寻找最小值。
  如果找到比当前最小值更小的元素，更新最小值的索引。
• 将找到的最小值与当前元素交换位置。
• 移动到下一个位置，重复步骤以上步骤。

具体流程图：

代码实现：

public void selectSort(int... arr){
    for(int i=0;i<arr.length-1;i++){
        //默认当前为最小的元素
        int minIndex = i; 
        //从i+1，往后找最小的元素
        for(int j=i+1;j<arr.length;j++){
            if(arr[j]<arr[minIndex]){
                //发现更小的则更新最小值索引
                minIndex = j; 
            }
        }
        //交换最小元素和当前元素
        if(minIndex!=i){
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

时间复杂度分析：

• 最好情况：O(n^2)；
• 最坏情况：O(n^2)；

0x04 插入排序

排序具体步骤：

• 初始假设：将第一个元素视为已经排序的部分。
  从第二个元素开始：
• 依次取出未排序部分的元素，与已排序部分从后向前比较。
  找到适当位置后，将该元素插入。
• 重复步骤 2，直到所有元素都插入完成。

具体流程图：

代码实现：

public void insertSort(int... arr){
    //从索引1开始，并将索引1视为已经排序
    for(int i=1;i<arr.length;i++){
        //将当前元素提取出来
        int current = arr[i]; 
        //指定当前元素的前一个元素的下标
        int preIndex = i-1;
        //判断当前元素是否小于前一个元素且是否存在下标越界
        while(preIndex>=0 && arr[preIndex]>current){
            //如果当前元素小于前一个，则将前一个元素后移
            arr[preIndex+1] = arr[preIndex];
            //指针从后往前移动
            preIndex--;
        }
        //如果当前元素比前一个大，则将当前元素插入到前一个元素后面
        arr[preIndex+1] = current;
    }
}

时间复杂度分析：

• 最好情况（数组已经有序）：每轮只需比较一次，时间复杂度为 O(n^2);
• 最坏情况（数组逆序）：每轮需要比较并移动所有已排序元素，时间复杂度为 O(n^2)；
• 平均情况：O(n^2)