题解 | 排序_牛客博客

解题思路

三种排序算法分析

一、冒泡排序 (Bubble Sort)

1. 基本原理

- 比较相邻的两个元素，如果前者大于后者则交换
- 每一轮将最大的元素"冒泡"到末尾
- 重复n-1轮，直到所有元素有序

2. 时间复杂度

最好情况： $\mathcal{O}(n)$ ，数组已经有序
最坏情况： $\mathcal{O}(n²)$ ，数组逆序
平均情况： $\mathcal{O}(n²)$
空间复杂度： $\mathcal{O}(1)$
稳定性：稳定

3. 代码框架

for(int i = 0; i < n-1; i++) {
    for(int j = 0; j < n-1-i; j++) {
        if(arr[j] > arr[j+1]) {
            swap(arr[j], arr[j+1]);
        }
    }
}

二、快速排序 (Quick Sort)

1. 基本原理

- 选择基准元素(pivot)
- 将数组分为两部分：小于pivot和大于pivot
- 递归对两部分进行排序
- 最终合并得到有序数组

2. 时间复杂度

最好情况： $\mathcal{O}(nlogn)$ ，每次都平分数组
最坏情况： $\mathcal{O}(n²)$ ，已经有序或逆序
平均情况： $\mathcal{O}(nlogn)$
空间复杂度： $\mathcal{O}(logn)$ ，递归栈空间
稳定性：不稳定

3. 代码框架

void quickSort(int left, int right) {
    if(left >= right) return;
    int pivot = partition(left, right);
    quickSort(left, pivot-1);
    quickSort(pivot+1, right);
}

三、归并排序 (Merge Sort)

1. 基本原理

- 将数组分成两半
- 递归排序两个子数组
- 合并两个有序数组
- 最终得到完整有序数组

2. 时间复杂度

最好情况： $\mathcal{O}(nlogn)$
最坏情况： $\mathcal{O}(nlogn)$
平均情况： $\mathcal{O}(nlogn)$
空间复杂度： $\mathcal{O}(n)$ ，需要临时数组
稳定性：稳定

3. 代码框架

void mergeSort(int left, int right) {
    if(left >= right) return;
    int mid = left + (right-left)/2;
    mergeSort(left, mid);
    mergeSort(mid+1, right);
    merge(left, mid, right);
}

四、比较分析

1. 时间效率

小数据量：冒泡 ≈ 快速 ≈ 归并
大数据量：快速 ≈ 归并 >> 冒泡
平均性能：快速 > 归并 > 冒泡

2. 空间效率

冒泡： $\mathcal{O}(1)$ ，原地排序
快速： $\mathcal{O}(logn)$ ，递归栈空间
归并： $\mathcal{O}(n)$ ，需要临时数组

3. 稳定性

冒泡：稳定
快速：不稳定
归并：稳定

4. 适用场景

冒泡排序
- 数据量小
- 要求稳定
- 代码简单
快速排序
- 数据量大
- 不要求稳定
- 平均性能最好
归并排序
- 数据量大
- 要求稳定
- 外部排序

5. 优化方向

冒泡排序
- 提前退出标志
- 记录最后交换位置
快速排序
- 三数取中选择pivot
- 处理重复元素
- 小数组使用插入排序
归并排序
- 小数组使用插入排序
- 优化临时数组分配
- 避免重复拷贝

代码

O(n²) 解法 - 冒泡排序

cpp
java
python

class Solution {
public:
    vector<int> MySort(vector<int>& arr) {
        int n = arr.size();
        for(int i = 0; i < n-1; i++) {
            for(int j = 0; j < n-1-i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr[j], arr[j+1]);
                }
            }
        }
        return arr;
    }
};

public class Solution {
    public int[] MySort (int[] arr) {
        int n = arr.length;
        for(int i = 0; i < n-1; i++) {
            for(int j = 0; j < n-1-i; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }
}

class Solution:
    def MySort(self , arr: List[int]) -> List[int]:
        n = len(arr)
        for i in range(n-1):
            for j in range(n-1-i):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
        return arr

O(nlogn) 解法 - 快速排序

cpp
java
python

class Solution {
public:
    void quickSort(vector<int>& arr, int left, int right) {
        if(left >= right) return;
        
        int pivot = arr[left];
        int i = left, j = right;
        
        while(i < j) {
            while(i < j && arr[j] >= pivot) j--;
            while(i < j && arr[i] <= pivot) i++;
            if(i < j) swap(arr[i], arr[j]);
        }
        arr[left] = arr[i];
        arr[i] = pivot;
        
        quickSort(arr, left, i-1);
        quickSort(arr, i+1, right);
    }
    
    vector<int> MySort(vector<int>& arr) {
        quickSort(arr, 0, arr.size()-1);
        return arr;
    }
};

public class Solution {
    public void quickSort(int[] arr, int left, int right) {
        if(left >= right) return;
        
        int pivot = arr[left];
        int i = left, j = right;
        
        while(i < j) {
            while(i < j && arr[j] >= pivot) j--;
            while(i < j && arr[i] <= pivot) i++;
            if(i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[left] = arr[i];
        arr[i] = pivot;
        
        quickSort(arr, left, i-1);
        quickSort(arr, i+1, right);
    }
    
    public int[] MySort(int[] arr) {
        quickSort(arr, 0, arr.length-1);
        return arr;
    }
}

class Solution:
    def quickSort(self, arr: List[int], left: int, right: int):
        if left >= right:
            return
            
        pivot = arr[left]
        i, j = left, right
        
        while i < j:
            while i < j and arr[j] >= pivot:
                j -= 1
            while i < j and arr[i] <= pivot:
                i += 1
            if i < j:
                arr[i], arr[j] = arr[j], arr[i]
        
        arr[left] = arr[i]
        arr[i] = pivot
        
        self.quickSort(arr, left, i-1)
        self.quickSort(arr, i+1, right)
    
    def MySort(self, arr: List[int]) -> List[int]:
        self.quickSort(arr, 0, len(arr)-1)
        return arr

归并排序 O(nlogn)

cpp
java
python

class Solution {
private:
    void merge(vector<int>& arr, int left, int mid, int right, vector<int>& temp) {
        int i = left, j = mid + 1;
        int k = left;
        
        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++];
        
        for(i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }
    
    void mergeSort(vector<int>& arr, int left, int right, vector<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);
        }
    }
    
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        vector<int> temp(arr.size());
        mergeSort(arr, 0, arr.size() - 1, temp);
        return arr;
    }
};

import java.util.*;

public class Solution {
    /**
     * 合并两个有序区间
     */
    private void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;    // 左半部分起始位置
        int j = mid + 1; // 右半部分起始位置
        int k = left;    // 临时数组起始位置
        
        // 合并两个有序区间
        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++];
        }
        
        // 将临时数组中的元素复制回原数组
        for(i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }
    
    /**
     * 递归进行归并排序
     */
    private 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);
        }
    }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        if(arr == null || arr.length <= 1) {
            return arr;
        }
        // 创建临时数组
        int[] temp = new int[arr.length];
        // 调用归并排序
        mergeSort(arr, 0, arr.length - 1, temp);
        return arr;
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
    def merge(self, arr: List[int], left: int, mid: int, right: int, temp: List[int]):
        """
        合并两个有序区间
        """
        i = left       # 左半部分起始位置
        j = mid + 1    # 右半部分起始位置
        k = left       # 临时数组起始位置
        
        # 合并两个有序区间
        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp[k] = arr[i]
                i += 1
            else:
                temp[k] = arr[j]
                j += 1
            k += 1
        
        # 处理剩余元素
        while i <= mid:
            temp[k] = arr[i]
            k += 1
            i += 1
        while j <= right:
            temp[k] = arr[j]
            k += 1
            j += 1
        
        # 将临时数组中的元素复制回原数组
        for i in range(left, right + 1):
            arr[i] = temp[i]
    
    def mergeSort(self, arr: List[int], left: int, right: int, temp: List[int]):
        """
        递归进行归并排序
        """
        if left < right:
            mid = left + (right - left) // 2
            # 递归排序左半部分
            self.mergeSort(arr, left, mid, temp)
            # 递归排序右半部分
            self.mergeSort(arr, mid + 1, right, temp)
            # 合并两个有序部分
            self.merge(arr, left, mid, right, temp)
    
    def MySort(self, arr: List[int]) -> List[int]:
        """
        主函数：归并排序入口
        """
        if not arr or len(arr) <= 1:
            return arr
        # 创建临时数组
        temp = [0] * len(arr)
        # 调用归并排序
        self.mergeSort(arr, 0, len(arr) - 1, temp)
        return arr