曾彪彪的个人博客 -- 排序算法小结

csp-j比赛中，需要掌握的排序算法有
- 冒泡
- 选择
- 插入
- 计数

前三个比较简单，直接写demo。第四个不太会，查阅相关资料，花大约3小时，最终理解。

冒泡排序
```c++
void bubbletSort(vector<int> &nums)
{
    for (int i = 0; i < nums.size(); i++)
    {
        for (int j = 0; j < nums.size() - i - 1; j++)
        {
            if (nums[j] > nums[j + 1])
            {
                swap(nums[j], nums[j + 1]);
            }
        }
    }
}

void bubbletSortImprovement(vector<int> &nums)
{    
    for (int i = 0; i < nums.size(); i++)
    {
        bool swapped=false; //可以做优化，如果数组元素未交换过，表明数组已有序，提前结束。
        for (int j = 0; j < nums.size() - i - 1; j++)
        {
            if (nums[j] > nums[j + 1])
            {
                swap(nums[j], nums[j + 1]);
                swapped=true;
            }
        }
        if(!swapped){
            break;
        }
    }
}

```

选择排序
```c++
void selectionSort(vector<int> &nums)
{
    for (int i = 0; i < nums.size(); i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < nums.size(); j++)
        {
            if (nums[j] < nums[minIndex])
            {
                minIndex = j;
            }
        }
        if (minIndex != i)
        {
            swap(nums[minIndex], nums[i]);
        }
    }
}

```

插入排序
```c++
oid insertionSort(vector<int> &nums)
{
    for (int i = 1; i < nums.size(); i++)
    {
        // i前面的元素都是有序的，把下标为i的元素插入到合适的位置
        int t = nums[i];
        int j = i;
        while (j > 0 && t < nums[j - 1])
        {
            nums[j] = nums[j - 1];
            j--;
        }
        nums[j] = t;
    }
}

```

在学习下一个排序算法之前，先来总结一下上面三个排序算法的特性；
冒泡，时间复杂度o(n^2)，空间复杂度o(1)，经过优化的冒泡，最好的情况下，时间复杂度为o(n)，平均是o(n^2)，稳定排序
选择，不稳定排序，在交换最大最小值时，可能改变了其原来的顺序。时间复杂度稳定o(n^2)，没有优化的空间，交换次数减少。
插入，稳定排序，时间复杂度平均o(n^2),最好可达o(n^2),交换次数多

计数排序

计数排序比较难，要搞明白计数排序，需要先弄清楚一个概念，前缀和。

所谓前缀和，就是对一个数组中的前面的所有元素求和，比如一个数组
arr={1, 2, 3, 4, 5, 6}；那么它的前缀和数组是
preSum={0, 1, 3, 6, 10, 15, 21}

前缀和数组的应用场景包括：
- 快速计算区间和，比如计算arr数组中子数组[i,j]的和，那么用preSum[j+1]-preSum[i]即可。这个特性可以延展到矩阵和的计算，这位计算最大子数组和，最大子矩阵和时，提供了暴力的基础。
- 解决计数类问题，比如计数排序中，记录每个元素出现的次数，求每个元素的计数前缀和，那么这个前缀和表明该元素在排序数组中出现的位置。这一点不太好理解，我们来举个列子。
对于数字arr={3, 3, 3, 2, 5, 1, 1}，那么它们计数频率数组是
{2, 1, 3, 0, 1}，元素1出现2次，元素2出现1次，3出现3次，4出现0次，5出现1次。那么其前缀和是
{2, 3, 6, 6, 7}，这个前缀和可以表示每个元素最后应该出现的位置。根据这个前缀和数组，我们可以计算出：
1 最后出现在第二个位置，下标应该是1(下标从0开始)，2最后应该出现第三个位置，下标是2，3最后出现在第6个位置，下标是5，依此类推。

这是理解计数排序的难点，弄明白了这个知识点，基本可以理解计数排序了。直接上代码，结合代码再理解一遍

```c++
void countingSort(vector<int> &nums)
{
    int maxValue = *max_element(nums.begin(), nums.end());
    int minValue = *min_element(nums.begin(), nums.end());
    vector<int> counter(maxValue - minValue + 1, 0);
    for (auto e : nums)
    {
        counter[e - minValue]++;
    }
    for (int i = 0; i < counter.size() - 1; i++)
    {
        counter[i + 1] += counter[i];
    }
    vector<int> output(nums.size());
    for (int i = nums.size() - 1; i >= 0; i--)
    {
        int v = nums[i];
        counter[v - minValue]--;
        output[counter[v - minValue]] = v;
    }
    nums = output;
}
```

最后对计数排序做一个总结：
计数排序是统计数组中每个元素出现的次数，并且对这些元素的次数计算其前缀和，数组元素的前缀和代表了这个元素应该排在新数组的最后位置+1。为了保证排序的稳定性，需要倒序遍历，确保原数组中排在后面的元素仍然排在后面。计数排序使用的场景是，数组元素的区间不是很大，因为技术数组的大小是maxValue-minValue+1，如果这个值很大，那么需要巨大的内存空间。
另外计数排序只能对整数进行排序，比如对于两位小数可能需要变形，比如乘100再排序，排完之后最后再除100等。

排序算法小结

评论(0)