快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Partition(vector<int>& v, int low, int high)
{
    int pivotkey = v[low];
    while(low < high)
    {
        while(low < high && v[high] >= pivotkey) --high;
        swapint(v[low], v[high]);
        while(low < high && v[low] <= pivotkey) ++low;
        swapint(v[low], v[high]);
    }
    return low;
}
void Qsort(vector<int>& v, int low, int high)
{
    if(low >= high) return;
    int pivotloc = Partition(v, low, high);
    Qsort(v, low, pivotloc - 1);
    Qsort(v, pivotloc + 1, high);
}
//调用方式：Qsort(vec, 0, vec.size());

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void adjust(vector<int>& vec, int len, int p)
{
    int left = 2 * p + 1;
    int right = 2 * p + 2;
    int maxId = p;
    if(left < len && vec[left] > vec[maxId]) maxId = left;
    if(right < len && vec[right] > vec[maxId]) maxId = right; // maxId是3个数中最大数的下标
    if(maxId != p) // 如果maxId的值有更新
    {
        std::swap(vec[maxId], vec[p]);
        adjust(vec, len, maxId); //递归调整其他不满足堆性质的部分
    }
}
void heapSort(vector<int>& vec)
{
    for(int i = vec.size() / 2 - 1; i >= 0; i--) // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
    {
        adjust(vec, vec.size(), i);
    }
    for(int i = vec.size() - 1; i >= 1; i--)
    {
        swap(vec[0], vec[i]); // 将当前最大的放置到数组末尾
        adjust(vec, i, 0); // 将未完成排序的部分继续进行堆排序
    }
}
//调用方式：heapSort(vec);

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void Merge(int arr[], int reg[], int start, int end) {
    if (start >= end)return;
    int len = end - start;
    int mid = len / 2 + start;
    /* 分成两部分 */
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    /* 分派合并 */
    Merge(arr, reg, start1, end1);
    Merge(arr, reg, start2, end2);
    /* 合并操作 */
    int k = start;
    while (start1 <= end1 && start2 <= end2) reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1) reg[k++] = arr[start1++];
    while (start2 <= end2) reg[k++] = arr[start2++];
    /* 复制结果 */
    for (k = start; k <= end; k++) arr[k] = reg[k];
}
void MergeSort(int arr[], const int len) {
    //创建一个同样长度的序列,用于临时存放
    int reg[len];
    Merge(arr, reg, 0, len - 1);
}
/*调用方式：
int lst[] = {4,54,6,45,12,312,0,-321};
MergeSort(lst, 8);
*/