欢迎来到NiceSpace!祝大家开心每一天!
  • C++
常用排序算法总结

整理了下一些常用的排序算法。

一、冒泡排序


冒泡排序:一排n个元素的序列,通过两两比较交换位置保持大的(或者小的)在右侧,这样经过n-1轮这样的操作完成排序。

源码:

#define SWAP(a,b) {a=a+b;b=a-b;a=a-b;}
 
// 冒泡排序
void BubbleSort(int src[], int n)
{
    for (int i = 0; i <= n - 2; i++)
    {
        for (int j = 0; j <= n - 2 - i; j++)
        {
            if (src[j] > src[j + 1])
            {
                SWAP(src[j], src[j+1])
            }
        }
    }
}


空间复杂度:O(1)

时间复杂度:最好:O(n),最坏O(n^2),平均O(n^2)

冒泡排序是稳定排序

二、选择排序


选择排序:一排n个元素的序列,每次通过两两比较,选出最大的索引与最右侧的元素交换,这样第一轮排出最大的元素在最右侧,第二轮选出第二大的元素在最右侧左移一个元素,这样经过n-1轮完成排序。

源码:

#define SWAP(a,b) {a=a+b;b=a-b;a=a-b;}
 
// 选择排序
void SelectionSort(int src[], int n)
{
    for (int i = 0; i <= n - 2; i++)
    {
        int key = 0;
        for (int j = 0; j <= n - 2 - i; j++)
        {
            if (src[key] < src[j])
                key = j;
        }
        if (src[key]> src[n - 1 - i])
        {
            SWAP(src[key], src[n-1-i])
        }
    }
}


空间复杂度:O(1)

时间复杂度:最好:O(n),最坏O(n^2),平均O(n^2)

选择排序是不稳定排序

三、插入排序


插入排序:一排n个元素的序列,从左向右遍历,遍历的每一个元素与它左侧元素逐一比较,找到刚好小于它的元素插入到后面,比他大的逐一向右侧移动一个元素,直至遍历完毕完成排序。

源码:

// 插入排序
void InsertSort(int src[], int n)
{
    for (int pt = 1; pt < n; pt++)
    {
        int key = src[pt];
        int idx = pt - 1;
        while (idx >= 0 && src[idx] > key)
        {
            src[idx + 1] = src[idx];
            idx--;
        }
        src[idx + 1] = key;
    }
}


空间复杂度:O(1)

时间复杂度:最好:O(n),最坏O(n^2),平均O(n^2)

插入排序是稳定排序

四、快速排序


快速排序:快速排序将n个元素的序列通过递归的方法,每次规定一个关键值,将小于等于关键值的元素放置到关键值左侧,大于关键值的元素放置到关键值右侧,这样直到递归完毕完成排序。

源码:

#define SWAP(a,b) {a=a+b;b=a-b;a=a-b;}
 
//快速排序
void QuickSort(int src[],int begin, int end)
{
    if (begin >= end)
        return;
    int key = src[begin];
    int l = begin;
    int r = end;
    while (l < r)
    {
        while (src[l] <= key && l < r)
            l++;
        while (src[r] > key && r > l)
            r--;
        if (r > l)
            SWAP(src[l], src[r])
    }
 
    if (r > begin)
        SWAP(src[begin], src[r])
 
    QuickSort(src, begin, r-1);
    QuickSort(src, r+1, end);
}


空间复杂度:O(log2n)

时间复杂度:最好:O(nlog2n),最坏:O(n^2),平均:O(nlog2n)

快速排序是不稳定排序

五、归并排序


归并排序:一个n个元素的序列,进行递归,每次递进时平均拆分成两个序列,然后对拆分后的序列进行排序,最后对排好序的两个序列进行合并。这样递归结束完成排序。

源码:

// 归并排序
void Combine(int src[], int begin, int end)
{
    int mid = (begin + end) / 2;
    int p = begin;
    int q = mid + 1;
    int k = 0;
    int* tmp = new int[end - begin + 1];
    while (p <= mid && q <= end)
    {
        if (src[p] <= src[q])
            tmp[k++] = src[p++];
        else
            tmp[k++] = src[q++];
    }
    while (p <= mid)
        tmp[k++] = src[p++];
    while (q <= end)
        tmp[k++] = src[q++];
    //复制到原数组
    for (int i = 0; i < end - begin + 1; i++)
    {
        src[begin + i] = tmp[i];
    }
 
    delete[] tmp;
}
 
void MergeSort(int src[], int begin, int end)
{
    if (begin >= end)
        return;
    
    int mid = (begin + end) / 2;
    MergeSort(src, begin, mid);
    MergeSort(src, mid + 1, end);
 
    Combine(src, begin, end);
}


空间复杂度:O(nlog2n)

时间复杂度:最好,最坏,平均:O(nlog2n)

归并排序是稳定排序

六、堆排序


堆排序:堆排序是将一个n个元素的序列描述成一个二叉树的形式,建立大根堆(每个根节点都不小于它的叶子节点的值),或者小根堆(每个根节点都不大于它的叶子节点的值),然后通过n-1次调堆完成排序。

源码:

#define LEFTCHILD(i) (i * 2 + 1)
#define RIGHTCHILD(i) (i * 2 + 2)
#define SWAP(a,b) {a=a+b;b=a-b;a=a-b;}
 
//调堆
void MaxHeap(int src[], int heapsize, int pos)
{
    int lastest = pos;
    while (1)
    {
        int l = LEFTCHILD(pos);
        int r = RIGHTCHILD(pos);
        if (l < heapsize && src[lastest] < src[l])
            lastest = l;
        if (r < heapsize && src[lastest] < src[r])
            lastest = r;
        if (lastest == pos)
            break;
        SWAP(src[pos], src[lastest]);
 
        pos = lastest;
    }
}
// 堆排序
void HeapSort(int src[], int heapsize)
{
    //建堆
    for (int k = heapsize / 2 - 1; k >= 0; k--)
    {
        MaxHeap(src, heapsize, k);
    }
    //调堆
    for (int k = heapsize - 1; k > 0; k--)
    {
        SWAP(src[0], src[k]);
        heapsize--;
        MaxHeap(src, heapsize, 0);
    }
}


空间复杂度:O(1)

时间复杂度:最好:O(nlog2n),最坏:O(nlog2n),平均:O(nlog2n)

堆排序是不稳定排序

七、希尔排序


希尔排序:希尔排序是插入排序的一种优化,是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,就变成了直接插入排序,算法终止。

源码:

//希尔排序
void ShellSort(int src[], int n)
{
    for (int gap = n / 2; gap > 0; gap = gap / 2)
    {    
        for (int pt = gap; pt < n; pt++)
        {
            int key = src[pt];
            int idx = pt - gap;
            while (idx >= 0 && src[idx] > key)
            {
                src[idx + gap] = src[idx];
                idx = idx - gap;
            }
            src[idx + gap] = key;
        }
    }
}


空间复杂度:O(1)

时间复杂度:最好,平均:O(nlog2n),最坏O(n^2)

希尔排序是不稳定排序

随机文章
3D图形学总结(三)—相机坐标转换(UVN相机) python爬虫之爬取腾讯新闻 3D图形学总结(十二)—纹理滤波 3D图形学总结(六)—背面消除与物体剔除 破解图片防盗链