排序

void InsertSort(int a[], int len) {
    for (int i=1; i<len; i++) {
        int v=a[i];
        for (int j=i-1; v<a[j];j--)
            a[j+1]=a[j]; // 后移
        a[j+1]=v;
    }
}

// ? 按照 ShellSort 定义写出
void shellSort1(int a[], int n) {
    int i, j, k, gap;
    for (gap = n / 2; gap > 0; gap /= 2)
        for (i = 0; i < gap; i++)                   // 分组
            for (int j = i + gap; j < n; j += gap)  // 组内插入排序
                if (a[j] < a[j - gap]) {            // 直接插入排序
                    int v = a[j];
                    for (int k = j - gap; k >= 0 && a[k] > v; k -= gap)
                        a[k + gap] = a[k];  // 后移
                    a[k + gap] = v;
                }
}

// ? 优化
// - 上述 i 的作用是为了确认 j 的位置，并与组内元素比较
// - 明显每次 gap 与 j-gap 就是组内比较，不需要再分组
void shellSort(int a[], int n) {
    int j, k, gap;
    for (gap = n / 2; gap > 0; gap /= 2)
        for (j = gap; j < n; j++)
            if (a[j] < a[j - gap]) {
                int v = a[j];
                for (int k = j - gap; k >= 0 && a[k] > v; k -= gap)
                    a[k + gap] = a[k];  // 后移
                a[k + gap] = v;
            }
}

void BubbleSort(int a[], int len){
    for (int i=0; i<len; i++){
        for (int j=i+1; j<len; j++){
            if (a[i]>a[j]){
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
}

// ? 快排划分
int Partition(int a[], int l, int r) {
    int p = a[l];
    while (l < r) {                      // l != r
        while (l < r && a[r] >= p) --r;  // r 向左扫描
        a[l] = a[r];
        while (l < r && a[l] <= p) ++l;  // l 向右扫描
        a[r] = a[l];
    }
    a[l] = p;
    return l;
}

// ? 快速排序
void QuickSort(int a[], int l, int r) {
    if (l < r) {
        int p = Partition(a, l, r);
        QuickSort(a, l, p - 1);
        QuickSort(a, p + 1, r);
    }
}

// ? 三数取中优化，此版本快的飞起
// https://www.cnblogs.com/chengxiao/p/6262208.html
// - 左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值
void QuickSort(int a[], int l, int r) {
    int mid = a[(l + r) / 2];
    int i = l, j = r;
    do {
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    } while (i <= j);
    if (l < j) QuickSort(a, l, j);
    if (i < r) QuickSort(a, i, r);
}

// 字符串的快排
void qsort(vector<string>& nums, int l, int r) {
    int i = l, j = r;
    string m = nums[l + ((r - l) >> 1)];
    do {
        while (nums[i] + m < m + nums[i]) i++;
        while (nums[j] + m > m + nums[j]) j--;
        if (i <= j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    } while (i <= j);
    if (l < j) qsort(nums, l, j);
    if (i < r) qsort(nums, i, r);
}

void SelectSort(int a[], int len){
    for (int i=0; i<len-1; i++){
        int k=i;
        for (int j=i+1; j<len; j++){
            if (a[j]<a[k]) k=j;
        }
        if (i!=k) swap(a[i],a[k]);
    }
}

// - 图解 https://www.cnblogs.com/chengxiao/p/6129630.html

// ? 调整以 k 为根的子树，即 shift 操作
// - 大孩子上升，空位置下降
void HeadAdjust(int a[], int k, int len) {
    int t = a[k];
    for (int i = k * 2 + 1; i < len; i = i * 2 + 1) {
        //  如果左子结点小于右子结点，i指向右子结点
        if (i + 1 < len && a[i] < a[i + 1]) i++;
        //  如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
        if (a[i] > t) {
            a[k] = a[i];
            k = i;
        } else
            break;
    }
    a[k] = t;  // t 放在最终位置
}

// ? 堆排序
void HeapSort(int a[], int len) {
    int i;
    // - 建立大根堆
    for (i = len / 2 - 1; i >= 0; i--) HeadAdjust(a, i, len);
    // - 交换堆顶堆低元素 + 调整堆结构
    for (i = len - 1; i >= 0; i--) {
        swap(a[i], a[0]);
        HeadAdjust(a, 0, i);
    }
}

void Merge(int a[], int begin, int mid, int end) {
    int left = begin, right = mid + 1, k = 0;
    int *temp = new int[end - begin + 1];
    //顺序选取两个有序区的较小元素，存储到t数组中
    while (left <= mid && right <= end) {
        //较小的先存入temp中
        if (a[left] <= a[right])
            temp[k++] = a[left++];
        else
            temp[k++] = a[right++];
    }
    //若比较完之后，有序区仍有剩余，则直接复制到t数组中
    while (left <= mid) temp[k++] = a[left++];
    while (right <= end) temp[k++] = a[right++];
    //将排好序的存回arr中
    for (int i = begin, k = 0; i <= end; i++, k++) a[i] = temp[k];
    //删除指针，释放空间
    delete[] temp;
}

// ? 递归
void MergeSort(int a[], int begin, int end) {
    if (begin < end) {
        int mid = (begin + end) / 2;
        MergeSort(a, begin, mid);    // 左侧递归
        MergeSort(a, mid + 1, end);  // 右侧递归
        Merge(a, begin, mid, end);   // 归并
    }
}

// ? 非递归
void MergeSort2(int a[], int n) {
    int size = 1, begin, mid, end;
    while (size <= n - 1) {
        begin = 0;
        while (begin + size <= n - 1) {
            mid = begin + size - 1;
            end = mid + size;
            if (end > n - 1)  //第二个序列个数不足size
                end = n - 1;
            Merge(a, begin, mid, end);
            begin = end + 1;  //下一次归并时第一关序列的下界
        }
        size *= 2;  //扩大范围
    }
}

// ? 辅助函数，求数据的最大位数  
int maxbit(int data[], int n) {  
    int maxData = data[0];  ///< 最大数  
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。  
    for (int i = 1; i < n; ++i) {  
        if (maxData < data[i]) maxData = data[i];  
    }  
    int d = 1;  
    int p = 10;  
    while (maxData >= p) {  
        // p *= 10; // Maybe overflow  
        maxData /= 10;  
        ++d;  
    }  
    return d;  
 /*    
     int d = 1; //保存最大的位数  
     int p = 10;  
     for(int i = 0; i < n; ++i){  
         while(data[i] >= p){  
             p *= 10;  
             ++d;  
         }  
     }  
     return d;
*/  
}  
  
// ? 基数排序  
void Radixsort(int data[], int n) {  
    int d = maxbit(data, n);  
    int *tmp = new int[n];  
    int *count = new int[10];  //计数器  
    int i, j, k;  
    int radix = 1;  
    for (i = 1; i <= d; i++)  //进行d次排序  
    {  
        for (j = 0; j < 10; j++) count[j] = 0;  //每次分配前清空计数器  
        for (j = 0; j < n; j++) {  
            k = (data[j] / radix) % 10;  //统计每个桶中的记录数  
            count[k]++;  
        }  
        for (j = 1; j < 10; j++)  
            count[j] = count[j - 1] + count[j];  //将tmp中的位置依次分配给每个桶  
        for (j = n - 1; j >= 0; j--)  //将所有桶中记录依次收集到tmp中  
        {  
            k = (data[j] / radix) % 10;  
            tmp[count[k] - 1] = data[j];  
            count[k]--;  
        }  
        for (j = 0; j < n; j++)  //将临时数组的内容复制到data中  
            data[j] = tmp[j];  
        radix = radix * 10;  
    }  
    delete[] tmp;  
    delete[] count;  
}