初级算法总结

快速排序：
快速排序是一种基于分治法的排序。其基本思想在于固定一个分界线，将整个序列按照小于分界线和大于分界线划分，然后再分别对划分好的子段进行排序。

快速排序的时间复杂度在理想情况下是O(n \log n)O(nlogn)，但如果选取分界线每次都是子段中的最大值或最小值的话，时间复杂度可能会退化到O(n^2)O(n
2
)。在内存使用上，因为整个移动过程都在原数组中进行的，所以属于原地排序。

sort函数是C++标准模板库（STL）中一种对快速排序的优化实现，可以通过传入头指针、尾指针和比较函数来对数组中的对象进行排序。

快速排序示例：

将数组{2, 3, 1, 5, 4}从小到大排列。

不使用sort函数

将「整体框架」和「移动元素」进行合并，我们得到快速排序完整代码：

// 该代码参考 https://www.geeksforgeeks.org/quick-sort/
#include 
#define N 100010 
using namespace std; 
int n; 
int a[N]; 
 
void quick_sort(int l, int r) { 
    // 设置最右边的数为分界线
    int pivot = a[r];
    
    // 元素移动
    int k = l - 1;
    for (int j = l; j < r; ++j)
        if (a[j] < pivot) swap(a[j], a[++k]); 
    swap(a[r], a[++k]); 
    
    if (l < k - 1) quick_sort(l, k - 1); // 如果序列的分界线左边的子段长度>1，排序
    if (k + 1 < r) quick_sort(k + 1, r); // 如果序列的分界线右边的子段长度>1，排序
    // 上面的过程结束后，到这里左子段和右子段已经分别排好序。又因为确定分界线以后的移动 *** 作
    // 保证了左子段中的元素都小于等于分界线，右子段中的元素都大于分界线。所以整个序列也是有序的。
} 
 
int main() { 
    // 输入
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); 
     
    // 快速排序
    quick_sort(1, n); 
    
    // 输出
    for (int i = 1; i <= n; ++i) printf("%d ", a[i]);  
    return 0; 
}