数据结构与算法java期末

### Java 数据结构与算法期末复习资料

#### 关于算法的概念及其基本属性
算法是指求解某一问题所使用的一系列清晰的指令[^1]。大部分算法的执行时间会随着输入量的增加而增大，因此理解如何评估和优化这些算法至关重要。

#### 时间复杂度分析
对于任何给定的算法，其时间效率可以通过公式 \(T(n) \approx C_{op}C(n)\) 来近似表示，其中\(C_{op}\)代表单次操作的成本，而\(C(n)\)则指代当输入规模为n时所需的操作数量。为了简化这种表达，在讨论最坏情况下的性能时通常采用大O记号(O)，而在描述最好情况下或平均表现时可能会用到Ω(omega)以及Θ(theta)。

#### 渐进符号的应用场景
三种主要用来衡量函数增长速度的渐进符号——O、Ω 和 Ө ——分别对应上界、下界及紧确界的定义。了解它们有助于更精确地比较不同算法之间的相对效能差异。

#### 编程实践要点
在编写Java应用程序的过程中需要注意一些特定事项：
- 文件命名需严格遵循规定，即`.java`源文件的名字应当与其内部声明的公共类完全吻合；
- 类内的构造器是一种特殊的成员方法，它的名字也得跟所属类别相同，并负责初始化新创建的对象实例；
- 面向对象编程强调三大核心特征：封装性（隐藏实现细节）、继承机制（支持代码重用）还有多态行为（允许子类替代父类），这些都是构建高效软件系统的基石。

#### 快速排序详解
作为一种高效的内省式排序策略，快速排序的关键在于选取合适的枢轴元素来分割待处理序列成较小的部分；理想状态下每次都能均匀分配左右两侧的数据项数目，则整个过程可达到接近线性的运行速率\[2\]。具体来说就是找到一个基准值pivot,使得所有小于等于此数值者置于左侧区间，大于者的放在右侧区域，之后再递归重复上述动作直至完成全部排列工作为止。

public static void quickSort(int[] array, int low, int high){
    if (low < high){ 
        int pi = partition(array, low, high);
        
        // Recursively sort elements before and after partition index.
        quickSort(array, low, pi - 1);  
        quickSort(array, pi + 1, high); 
    }
}

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

    swap(arr,i+1,h);
    return i+1;     
}