三大排序算法

归并排序[稳定的排序算法]

递归实现

void Merge (vector<int > & seq, int low, int mid, int high)
{
    vector<int > tmp;
    int i = low, j = mid + 1;
    while (i <= mid && j <= high)
    {
        if (seq[i] <= seq[j])
            tmp.push_back (seq[i++]);
        else
            tmp.push_back (seq[j++]);
    }

    while (i <= mid)
        tmp.push_back (seq[i++]);

    while (j <= high)
        tmp.push_back (seq[j++]);

    for (i = 0; i < tmp.size(); i++)
        seq[low + i] = tmp[i];
}

void  mergeSort (vector<int > & seq, int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) >> 1;
        mergeSort (seq, low, mid);
        mergeSort (seq, mid + 1, high);
        Merge (seq, low, mid, high);
    }
}

非递归实现

void Merge (vector<int > & seq, int start1, int start2, int seg)
{
    vector<int > tmp;
    int i = start1, j = start2;
    int n = seq.size();

    while (i < start1 + seg && j < start2 + seg && i < n && j < n)
    {
        if (seq[i] <= seq[j])
            tmp.push_back (seq[i++]);
        else
            tmp.push_back (seq[j++]);
    }

    while (i < start1 + seg && i < n)
        tmp.push_back (seq[i++]);

    while (j < start2 + seg && j < n)
        tmp.push_back (seq[j++]);

    int k = tmp.size();
    for (i = start1; i < start1 + k; i++)
        seq[i] = tmp[i - start1];
}

void  mergeSort (vector<int > & seq)
{
    int n = seq.size();
    for (int seg = 1; seg < n; seg *= 2)
    {
        for (int i = 0; (i + 1)*seg < n; i += 2)
        {
            Merge (seq, i * seg, (i + 1) * seg, seg);
        }
    }
}

快速排序[不稳定的排序算法]

int Partition (vector<int > & seq, int low, int high)//填坑法
{
    vector<int > tmp;
    int i = low, j = high;
    int key = seq[low];//哨兵选取最左边元素
    while (i < j)
    {
        while (seq[j] >= key && i < j)//从右往左寻找
            j--;
        if (i < j)
            seq[i++] = seq[j];//第一次：第一个小于key的值赋给了low位置，即原来哨兵位置
        while (seq[i] < key && i < j)//从左往右寻找
            i++;
        if (i < j)
            seq[j--] = seq[i];
    }
    seq[i] = key;//保存最后的哨兵位置，i==j的地方左边小于key,右边大于等于key
    return i;
}

void  quickSort (vector<int > & seq, int low, int high)
{
    if (low < high)
    {
        int pos = Partition (seq, low, high);
        quickSort (seq, low, pos - 1);
        quickSort (seq, pos + 1, high);
    }
}

堆排序[不稳定的排序算法]

void Adjust (vector<int > & seq, int n, int cur) //最大堆调整
{
    int lc = cur * 2 + 1;//左儿子
    int rc = lc + 1;//右儿子
    if (lc < n && seq[cur] < seq[lc])
    {
        swap (seq[cur], seq[lc]);
        Adjust (seq, n, lc);
    }

    if (rc < n && seq[cur] < seq[rc])
    {
        swap (seq[cur], seq[rc]);
        Adjust (seq, n, rc);
    }
}

void AdjustMaxHeap (vector<int > & seq, int n)
{
    int i = (n - 2) / 2;//从第一个非叶子结点开始
    while (i >= 0)
    {
        Adjust (seq, n, i);
        i--;
    }
}

//s升序排序：先建立一个最大堆，然后将堆顶元素和最后一个元素交换，继续调整，调整完即排好序
void  heapSort (vector<int > & seq)
{
    int n = seq.size();
    AdjustMaxHeap (seq, n);
    for (int i = n - 1; i >= 0; i--)
    {
        swap (seq[0], seq[i]);
        Adjust (seq, i, 0);
    }
}