排序算法总结

　　1.冒泡排序

　　相邻两个交换

　　时间复杂度O（n²）

　　稳定

　　2.插入排序

　   O(n²)

　　稳定

　　3.选择排序

　　O(n²)

　　不稳定

　　4.快排

　　1）从待排序的n个记录中任意选取一个记录（通常选取第一个记录）为分区标准;

　　2）把所有小于该排序列的记录移动到左边，把所有大于该排序码的记录移动到右边，中间放所选记录，称之为第一趟排序；

　　3）然后对前后两个子序列分别重复上述过程，直到所有记录都排好序。

　　稳定性：不稳定

　　平均时间复杂度：O(nlogn)

　　

　　5.归并

　　1)先通过二分将其分到最小，再合并有序数组

　　O（nlogn） 稳定

void Merge(int *a, int *l, int*r, int m, int n)
{
    int i = 0, j = 0,k=0;
    while (i < m&&j < n)
    {
        if (l[i] < r[j]) a[k++] = l[i++];
        else
        {
            a[k++] = r[j++];
        }
    }
    while (i < m) a[k++] = l[i++];
    while (j < n)a[k++] = r[j++];
}


void MergeSort(int *a, int n)
{
    int mid, i, *l, *r;
    if (n < 2) return;
    mid = n / 2;
    l = new int[mid];
    r = new int[n - mid];
    for (i = 0; i < mid; i++) l[i] = a[i];
    for (i = mid; i < n; i++) r[i - mid] = a[i];
    MergeSort(l, mid);
    MergeSort(r, n - mid);
    Merge(a, l, r, mid, n - mid);
    delete[] r;
    delete[] l;
}

 　　
　　6.堆排序

　　时间复杂度O（nlogn）

　　不稳定

　　

void buildminHeap(vector<int>&a,int i)//建堆
{
    int temp = a[i];//挖坑
    for (; i != 0;)
    {
        if (temp < a[(i - 1) / 2])
        {
            a[i] = a[(i - 1) / 2];//填坑
            i = (i - 1) / 2;
        }
        else
            break;
    }
    a[i] = temp;
}

void minHeap(vector<int> a, vector<int> &res)
{
    for (int i = 0; i < a.size(); i++)
    {
        res[i] = a[i];
        buildminHeap(res, i);
    }
}

vector<int> removeminHeap(vector<int> a)
{
    int n = a.size();
    vector<int> res;
    res.resize(a.size(), 0);
    for (int i = 0; i <n ; i++)
    {
        res[i] = a[0];
        a[0] = a[a.size() - 1];
        a.erase(a.end() - 1);
        int j = 0,k=2*j+1;
        while (1)
        {
            k = 2 * j + 1;
            if ((k+1) > a.size() && k < a.size())//没有右子树
            {
                int temp = a[j];
                a[j] = a[k];
                a[k] = temp;
            }
            else if (k < a.size() && (k+1)< a.size())//左右子树存在
            {
                int t = a[k] < a[k+1] ? (k) : (k+1);    //取小的
                int temp = a[t];
                a[t] = a[j];
                a[j] = temp;
                j = t;
            }
            else
                break;
        }
    }
    return res;
}

　　7.桶排序

　　O（n+C） 稳定