算法

平均时间复杂度

空间复杂度

最坏情况

排序方式

稳定性

归并排序

O(n log n)

O(n)

O(n log n)

外

稳定

选择排序

O(n^2)

O(1)

O(n log n)

内

不稳定

堆排序

O(n log n)

O(1)

O(n log n)

内

不稳定

插入排序

O(n^2)

O(1)

O(n^2)

内

稳定

希尔排序

O(n log^2 n)

O(1)


内

不稳定

快速排序

O(n log n)

O(log n)

O(n^2)

内

不稳定

冒泡排序

O(n^2)

O(1)

O(n^2)

内

稳定

基数排序k是关键字取值范围

O(n)

O(k)


外

稳定

冒泡排序：重的泡泡下沉。 
    bool flag = true; 
    for (int i = 1; i < zq.size(); ++i) //第一层循环，最多要冒泡数组个数-1次才能排完序
    { 
        flag = false; 
        for (int j = 0; j < (zq.size() - i); ++j) //第二层循环，循环次数为数组总个数 - 第几个元素。        { 
            if (zq[j + 1] < zq[j]) 
            { 
                flag = true;
                temp = zq[j + 1]; 
                zq[j + 1] = zq[j]; 
                zq[j] = temp; 
            } 
        } 
    }
快速排序：选一个界点(这里是第一个数)，小的放左边，大的放右边，递归。 
void quick_sort(vector<int>&zq, int left, int right)
{ 
    if (left > right) 
        return; 
    int i = left + 1; 
    int j = right; 
    int temp = zq[left]; //界点
    while (i <= j) 
    { 
        while (zq[i] < temp)
            i++; 
        while (zq[j] > temp) 
            j--; 
        if (i < j) 
            swap(zq[i++], zq[j--]); 
        else 
            i++; 
    } 
    swap(zq[j], zq[left]); //j就是界点应该的位置
    quick_sort(zq,left,j-1); //界点左侧分治
    quick_sort(zq,j+1,right);//界点右侧分治
}
归并排序：核心两个有序表合并一个。把每个元素看成一个有序表 
void merge(vector<int>&zq, int low, int mid, int high)
 {      //low为第一有序区第一元素，mid为第一有序区最后元素
    int i = low, j = mid + 1,count=low;
    while (i <= mid && j <= high)
    {
        if (zq[i] <= zq[j])
            result[count++] = zq[i++];
        else
            result[count++] = zq[j++];
    }
    while (i <= mid)//比较完后，第一区仍有剩余
        result[count++] = zq[i++];
    while (j <= high)//比较完后，第二区仍有剩余
        result[count++] = zq[j++];
    for (int i = low; i <= high; i++)
        zq[i] = result[i];
 }
 void mergesort(vector<int>&zq,int low,int high)
 {
    if (low < high)
    {
        int mid = (low + high) / 2;
        mergesort(zq, low, mid);
        mergesort(zq, mid + 1, high);
        merge(zq, low, mid, high);
    }
 }