（C++实现）经典排序算法

1. 交换排序

根据数组中两个元素值的大小来交换两个元素在数组中的位置。

1.1 冒泡排序

1.1.1 基本思想： 假设待排序的长度是n，从后往前（或者是从前往后）依次比较相邻的两个元素的大小，
如果是逆序，则交换，直到比较完成。下面是从小到大的排序过程：
(1) 取未排序序列的最后一个元素（待排序的元素）；
(2) 在未排序的元素序列中从后向前扫描，如果待排序的元素比新元素小，就交换它们两个；
(3) 重复步骤(2)，直到待排序的元素插入与排序的位置；
(4) 重复步骤(1)~(3)，知道排序完成。
1.1.2 代码实现：

void bubbleSort(vector<int> &arr, int len){
    for(int i=0; i < len-1; i++){   // n-1趟排序
        int flag = 0;     // 交换的标记
        for(int j=len-1; j>i; j--){
            if(arr[j] < arr[j-1]){
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                flag = 1;
            }
        }
        if(flag == 0)   //第一次排序为发生交换，则原序列有序
            return;
    }
}

1.2.3 性能分析：
(1) 空间复杂度：。
(2) 时间复杂度：最好情况下（待排序的序列为有序序列，比较次，交换次），为。最坏情况下（待排序序列为逆序序列，比较次，交换次）：。
(3) 稳定性：当相等的两个元素进行比较时，不会发生交换，两个元素在排序前和排序后的相对位置不会发生交换。因此，针对以上所写冒泡排序算法，是稳定的。

1.2 快速排序

1.2.1 基本思想： 基于分治法。在待排序表L[1,...,n]中任取一个元素pivot为基准，通过一趟排序将序列划分为两部分：L[1,...,k-1]和L[k+1,...,n]，使得L[1,...,k-1]的所有元素值都小于pivot，L[k+1,...,n]的所有元素值都大于pivot，而pivot在序列最终的L[k]位置上。随后，分别递归的对两个子序列重复以上过程，直到序列内只有一个元素或者为空。由此可知，每一趟的快速排序都有一个元素在序列的最终位置上。
1.2.2 代码实现：

int partition(vector<int> &arr, int low, int high){
    int pivot = arr[low];
    while(low < high){
        while(low<high && arr[high] >= pivot)
            --high;
        if(low<high)
            arr[low++] = arr[high];
        
        while(low<high && arr[low]<=pivot)
            ++low;
        if(low < high)
            arr[high--] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

void quickSort(vector<int> &arr, int low, int high){
    if(low < high){
        int pivotPos = partition(arr, low, high);
        quickSort(arr, low, pivotPos - 1);
        quickSort(arr, pivotPos + 1, high);
    }
}

1.2.3 性能分析：
(1) 空间复杂度：快速排序需要递归栈保存每次递归调用时所需要的信息，为。（可借助二叉树的思想）
(2) 时间复杂度：快速排序的时间复杂度与划分是否对称有关。最好的情况下，每次划分后的序列是对称的，时间复杂度为；最坏的情况下，初始序列是有序或是逆序，时间复杂度为。
(3) 稳定性：举例，初始序列为{2，2，3}，快速排序后为{2，2，3}。值相同的两个元素在序列中的相对位置发生了变化。

2. 插入排序

插入排序：每次将一个待插入的元素插入到已经排序好的子序列中，直到全部的序列插入完成。

2.1 直接插入排序

2.1.1 基本思想：
假设L是一个由n个元素的待排序序列，现将L(i)插入到有序列L[1,2,...,i-1]中，则排序过程如下：
(1) 查找L(i)在L[1,2,...,i-1]中待插入的位置k；
(2) 将L[k,...,i-1]中的所有元素往后移动一个位置；
(3) 将L(i)复制到L(k)中；
(4) 重复步骤(1)-(3)，直到所有的元素排序完成。
2.1.2 代码实现：

void insertSort(vector<int> &arr, int len){
    for(int i = 1; i < len; i++){
        int current = arr[i];
        int j = i - 1;
        while(j >= 0 && current < arr[j]){
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = current;
    }
}

2.1.3 性能分析：
(1) 空间复杂度： 借助了常数个存储单元，空间复杂度为；
(2) 时间复杂度： 直接插入排序的时间复杂度与待排序序列的初始状态有关。最好情况下，待排序序列有序，每个元素需要比较1次，时间复杂度为；最坏的情况下，待排序序列逆序，总的比较次数为，总的移动次数为.因此，时间复杂度为。
(3) 稳定性：待插入的元素再有序序列中查找待插入的位置时，遇到相同元素即停止，不会发生交换。因此，直接插入排序是稳定的。

2.2 折半插入排序

2.2.1 基本思想：
假设L是一个由n个元素的待排序序列，现将L(i)插入到有序列L[1,2,...,i-1]中，则排序过程如下：
(1) 折半查找L(i)在L[1,2,...,i-1]中待插入的位置k；
(2) 将L[k,...,i-1]中的所有元素往后移动一个位置；
(3) 将L(i)复制到L(k)中；
(4) 重复步骤(1)-(3)，直到所有的元素排序完成。
2.2.2 代码实现：

void binaryInsertSort(vector<int> &arr, int len){
    int left, right, mid, temp;
    for(int i = 1; i < len; i++){
        temp = arr[i];   //待插入元素
        left = 0;
        right = i - 1;
        while(left <= right){
            mid = (left + right) / 2;
            if(temp < arr[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        for(int j = i - 1; j > right; j--)
            arr[j + 1] = arr[j];
        arr[right + 1] = temp;
    }
}

2.2.3 性能分析：
(1) 空间复杂度：。
(2) 时间复杂度：。第趟折半查找待插入元素的在已排序序列中位置的时间复杂度为，则总的比较次数为；总的移动次数为。所以折半插入排序的时间复杂度为。
(3) 稳定性：折半插入排序是稳定的。

主函数代码：

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int len;
    cin >> len;
    vector<int> arr(len);    
    cout << "待排序序列为：";
    for(int i = 0; i < len; i ++){
        cin >> arr[i];
    }
    // bubbleSort(arr, len);
    // quickSort(arr, 0, len - 1);
    // insertSort(arr, len);
    // binaryInsertSort(arr, len);    
    cout << "排序结果为：";
    for(int i = 0; i < len; i ++){
        cout << arr[i] << ' ';
    }
    cout << endl;
    return 0;
}