十大排序算法（C++）_c++排序算法

十大排序算法（C++）

1、冒泡排序

原理：比较相邻两个元素，如果前一个比后一个大则交换二者位置（以升序为例），每进行一轮比较则可以把最大的元素放到相对最后的位置。每进行一轮比较就会有一个元素变为有序。循环对每轮越来越少的元素进行比较则最终变为有序序列。
如果序列元素初始时为有序，则一轮则可进行排序完毕，最好时间复杂度为O(n)；如果序列元素初始时是逆序，则需要n-1轮比较，且每轮要进行n-i次比较，最坏时间复杂度为O(n²)，平均时间复杂度为O(n²)。

// 冒泡排序
void SortBubbling(int arr[],const int &iLen)
{
    for (int i = 0; i < iLen; i++)	//n轮比较
    {
        for (int j = 0; j < iLen-1-i; j++)//每轮n-i次比较
        {
            if (arr[j] > arr[j + 1])
                std::swap(arr[j], arr[j + 1]);	//交换元素
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2、快速排序

原理：快速排序首先从待排序列中取出一个元素作为基数，然后分别从序列的两端进行比较，分别将比基数大的数放在基数的右边位置，比基数小的元素放在基数的左边位置；然后分别对基数左右两部分的数据以相同的原理进行操作（递归操作）。
快速排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n²)，平均时间复杂度为O(nlogn)

//快速排序
void SortFast(int arr[], const int& iLeft,const int& iRight)
{
    if (iLeft < iRight)
    {
        int iFlag = arr[iLeft];
        int i = iLeft, j = iRight;
        while (i < j)
        {
            while (j > i && arr[j] >= iFlag)	// 从后往前找到比基数小的元素下标
                --j;
            if (i < j)							// 把比基数小的元素放置在基数前半部分
                arr[i++] = arr[j];

            while (i < j && arr[i] < iFlag)		// 从前往后找到比基数大的元素下标
                ++i;
            if (i < j)							// 把比基数大的元素放置在基数的后半部分
                arr[j--] = arr[i];
        }
        arr[i] = iFlag;							// 放置基数的所在位置

        SortFast(arr, iLeft, i - 1);			// 对基数前半部分进行排序
        SortFast(arr, i + 1, iRight);			// 对基数后半部分进行排序
    }
}
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

3、插入排序

原理：插入排序对少量元素进行排序是比较有效的一种排序方式。插入排序会对数据进行后移，如果数据量较大则移动大量数据的代价就高了。排序从第二个元素开始与之前的元素进行比较找到自己的位置。
如果待排序列是有序的则最好时间复杂度为O(n)；如果待排序列是逆序的则最坏时间复杂度为O(n²)

//插入排序
void SortInsert(int arr[], const int& iLen)
{
    for (int i = 1; i < iLen; i++)	// 从第二个元素开始
    {
        for (int j = i; j - 1 >= 0 && arr[j - 1] > arr[j]; --j)	// 当前元素与之前元素进行比较，如果小则交换位置，直到不小于之前元素为止
        {
            std::swap(arr[j - 1], arr[j]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

4、希尔排序

原理：希尔排序是直接插入排序的一个高级版本，又名缩小增量排序。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。希尔排序的增量设置是一个难题，难以寻找最优的增量变化关系。一般采用length/2，length/2/2，…，1。
在序列为有序的情况下，最优的时间复杂度为O(n)；最坏情况下时间复杂度为O(n²)；平均时间复杂度为O(n^1.3)。

//希尔排序
void SortShell(int arr[], const int& iLen)
{
    int iStep = iLen / 2 + 1;	// 设置初始步长

    while (0 != iStep)
    {
        for (int i = 0; i + iStep < iLen; i++)
        {
            if (arr[i] > arr[i + iStep])
                std::swap(arr[i], arr[i + iStep]);
        }

        --iStep ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5、选择排序

原理：首先选择待排序列中最小的元素，将其放置在序列的起始位置，然后再从剩余的数据中选择最小的元素放置在已排序序列的末尾。
选择排序的时间复杂度为O(n²)。

//选择排序
void SortSelect(int arr[], const int& iLen)
{
    for (int i = 0; i < iLen; i++)
    {
        int iMinIdx = i;
        for (int j = i+1; j < iLen; j++)
        {
            if (arr[iMinIdx] > arr[j])
                iMinIdx = j;
        }
        if(i != iMinIdx)
            std::swap(arr[i], arr[iMinIdx]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6、堆排序

原理：堆排序是以堆这种数据结构进行排序，堆分为大顶堆和小顶堆，类似于完全二叉树，子节点总是小于或者大于其父节点。
1、大顶堆：每个结点的值都大于等于其子节点的值，用于升序排序，大顶堆满足关系arr[i] >= arr[ii2+1] && arr[i] >= arr[2i+2]
2、小顶堆：每个结点的值都小于等于其子节点的值，用于降序排序,小顶堆满足关系arr[i] <= arr[ii2+1] && arr[i] <= arr[2i+2]
堆排序的时间复杂度为O(nlogn)。

//调节堆
void AdjustHeap(int arr[], const int& iStart, const int& iEnd)
{
    int iFather = iStart;
    int iLSon = iStart * 2 + 1;
    int iTemp = arr[iStart];
    for (; iLSon <= iEnd; iFather = iLSon, iLSon = 2 * iLSon + 1)
    {
        //选出左右子树中大的结点
        if (iLSon < iEnd && arr[iLSon] < arr[iLSon + 1])
            ++iLSon;

        //如果父节小于子结点，则交换父子结点
        if (iTemp < arr[iLSon])     
        {
            arr[iFather] = arr[iLSon];
            arr[iLSon] = iTemp;
        }
        else
            break;
    }
}

//堆排序
void SortHeap(int arr[], const int& iLen)
{
    for (int i = iLen / 2 - 1; i >= 0; --i)
        AdjustHeap(arr, i, iLen - 1);   //调整堆为大顶堆

    for (int i = iLen - 1; i > 0; --i)
    {
        //提取堆顶最大元素放入序列末尾，然后把剩余元素再次调节成大顶堆
        std::swap(arr[0], arr[i]);
        AdjustHeap(arr, 0, i - 1);
    }
}
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
29
30
31
32
33
34
35
36

7、归并排序

原理：归并排序是一种稳定有效的排序算法。算法采用分治法，首先是子序列有序，然后再把子序列进行合并，成为一个完整的序列。
归并排序的时间复杂度为O(nlogn)。

void MargeEnd(int arr[], const int& iLIdx, const int& iRIdx, const int& iMid)
{
    int iLSize = iMid - iLIdx;
    int iRSize = iRIdx - iMid + 1;
    std::unique_ptr<int[]> pArrL(new int[iLSize]{ 0 });
    std::unique_ptr<int[]> pArrR(new int[iRSize]{ 0 });

    for (int i = iLIdx; i < iMid; i++)
        pArrL[i-iLIdx] = arr[i];//左边部分元素
    for (int i = iMid; i <= iRIdx; i++)
        pArrR[i-iMid] = arr[i];//右边部分元素

    int iIdx1 = 0, iIdx2 = 0, iCnt = iLIdx;
    while (iIdx1 < iLSize&& iIdx2 < iRSize)
    {
        if (pArrL[iIdx1] < pArrR[iIdx2])
            arr[iCnt++] = pArrL[iIdx1++];
        else
            arr[iCnt++] = pArrR[iIdx2++];
    }

    while (iIdx1 < iLSize)	//合并剩余左边部分元素
        arr[iCnt++] = pArrL[iIdx1++];

    while (iIdx2 < iRSize)	//合并剩余右边部分元素
        arr[iCnt++] = pArrR[iIdx2++];
}

void Marge(int arr[], const int& iStart, const int& iEnd)
{
    if (iStart == iEnd)
        return;
    int iMid = (iEnd + iStart) / 2;

    Marge(arr, iStart, iMid);
    Marge(arr, iMid + 1, iEnd);

    MargeEnd(arr, iStart, iEnd, iMid+1);
}

//归并排序
void SortMarge(int arr[], const int& iLen)
{
    Marge(arr, 0, iLen - 1);
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

8、桶排序

原理：桶排序首先是分配有限个桶，然后把待排序数据根据一定的规则归类放入不同的桶中，并且在桶中采用一定的策略再次进行排序，最终把桶中的元素进行遍历便可以得到有序序列。桶排序是以空间获取时间的排序方式。

//简单桶排序
void SortBucket(int arr[], const int& iLen)
{
    std::vector<std::vector<int>> vctBucket(iLen);
    for (int i = 0; i < iLen; i++)
    {
        vctBucket.at(arr[i] % 10).push_back(arr[i]);
    }
    
    int i = 0;
    for (auto item : vctBucket)
    {
        for (auto subItem : item)
            arr[i++] = subItem;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

9、计数排序

原理：计数排序是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）。

//计数排序
void SortCounter(int arr[], const int& iLen)
{
    std::vector<int> vctCount(iLen);
    for (int i = 0; i < iLen; i++)
        vctCount.at(arr[i])++;  //记录每个值出现的次数

    int iIdx = 0;
    for (int i = 0; i < vctCount.size(); i++)
    {
        for (int j = 0; j < vctCount.at(i); j++)
            arr[iIdx++] = i;		// 按序列组织数据
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

10、基数排序

原理：基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

void StartRadix(int arr[], const int& iLen, const int& iExp)
{
    std::unique_ptr<int[]> pTemp(new int[iLen] {0});
    std::unique_ptr<int[]> pCnt(new int[10]{ 0 });

    for (int j = 0; j < iLen; j++)
        pCnt[(arr[j] / iExp) % 10]++; //统计每个桶中元素数量

    for (int j = 1; j < 10; j++)      //计算元素存在于序列中的位置
        pCnt[j] += pCnt[j - 1];

    for (int j = iLen-1; j >=0; j--)    //元素放入临时数组
    {
        pTemp[pCnt[(arr[j] / iExp) % 10] - 1] = arr[j];
        pCnt[(arr[j] / iExp) % 10]--;
    }

    for (int i = 0; i < iLen; i++)  //恢复每轮排序的元素到原始数组中
        arr[i] = pTemp[i];
}

//基数排序
void SortRadix(int arr[], const int& iLen)
{
    auto item = std::max_element(arr, arr + iLen - 1);

    for (int i = 1; *item / i > 0; i *= 10)
        StartRadix(arr, iLen, i);
}

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
29
30