排序算法

非比较排序
- 计数排序：稳定的线性时间排序算法，牺牲空间换取时间的非比较类排序算法，O(N+k)
- 桶排序：计数排序的升级版，
- 基数排序：一位一位的排序
比较类
- 交换
  - 冒泡：两层for循环，第一层控制趟数，第二层控制比较，每一趟都可以将本次最大元素送到末尾
  - 快排：选取一个元素作为基准，将数据分为大于基准和小于基准的两组，然后继续往下排序
- 插入
  - 简单插入：将数据分为有序区和无序区，逐一扫描无序区里面的元素，将其与有序区元素进行比较，将有序区较大的数逐一往后挪
  - 希尔排序：通过增量控制的方法，达到几次排序就可以让数组基本有序，不稳定，例如 13 11¹ 11² 15 ，希尔排序后变为13 11² 11¹ 15
- 选择
  - 简单选择：第一次，选出最小的元素放到第一个位置，第二次，选择次小的元素放到第二个位置。不稳定，例如 5 8 5 2 9
  - 堆排序：堆是利用完全二叉树的性质维护的一维数组
    
    大顶堆：父结点的值大于左右子结点的值
    
    小顶堆：父结点的值小于左右子结点的值
- 归并
  - 二路归并：分治思想，首先不断二分，然后开始合并，由小的有序数组合并为大的有序数组，稳定，时间复杂度始终是O(NlogN)
  - 多路归并

是否稳定：看相同的元素在排序前后的相对顺序是否发生改变

代码实现

#include<bits/stdc++.h>
using namespace std;


class MySort{
   
public:
    static void PrintSort(vector<int>& nums) {
   
        for (auto i : nums) cout << i << " ";
        cout << endl;
    }
    /*比较类排序算法*/
    //交换
    //1 冒泡排序
    //时间复杂度O(N^2)
    static void BubbleSort(vector<int>& nums) {
   
        // len个元素进行len-1趟排序，每次上浮一个元素（最小或者最大）
        for (int i = 0; i < nums.size() - 1; ++i) {
   //控制趟数
            for (int j = 0; j < nums.size() - 1 - i; ++j) {
   
                if (nums[j] > nums[j+1]) {
   
                    swap(nums[j], nums[j+1]);
                }
            }
        }
    }
    //2.快速排序
    // 时间复杂度：最坏是O(N^2) 平均是O(NlogN) 最好也是O(NlogN)
    static void QuickSort(vector<int>& nums) {
   
        QuickSortRecur(nums, 0 , nums.size()-1);
    }
    static void QuickSortRecur(vector<int>& nums, int left, int right) {
   
        if (left >= right) return ;
        int i = rand() % (right - left +1) + left;//随机选择基准点
        swap(nums[left], nums[i]);
        int low = left , high = right ;
        while (low < high) {
   
            while (low < high  &&  nums[high] >= nums[left])
                high--;
            while (low < high  &&  nums[low] <= nums[left])
                low++;
            swap(nums[low], nums[high]);
        }
        swap(nums[low], nums[left]);
        QuickSortRecur(nums, left, low-1);
        QuickSortRecur(nums, low+1, right);
    }
    //插入
    //3. 简单插入排序 
    //时间复杂度： 最坏完全逆序O(N^2) 最好完全顺序O(N) 
    //将数组分为有序区和无序区，每次从无序区选出一张牌插入到有序区
    static void InsertSort (vector<int>& nums) {
   
        int j = 0;
        for (int i = 1; i < nums.size(); ++i) {
   
            j = i - 1;//有序区最后一个元素
            while (j >= 0 && nums[j] > nums[i]) {
   
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = nums[i];
        }
    }
    //4.希尔排序 
    //时间复杂度： 最坏O(N^2) 最好O(N)
    //对插入排序的一种改进
    //通过增量控制排序数据的分组
    static void ShellSort(vector<int>& nums) {
   
        int len = nums.size();
        for (int gap = len / 2; gap > 0; gap /= 2) {
   
            for (int i = gap; i < len; ++i) {
   
                int j = i - gap;//有序区最后一个元素
                while (j >= 0 && nums[j] > nums[i]) {
   
                    nums[j + gap] = nums[j];
                    j -= gap;
                }
                nums[j + gap] = nums[i];
            }
        }
    }
    //选择排序
    //5.简单选择排序
    //时间复杂度O(N^2)
    static void  SelectSort(vector<int>& nums){
   
        //第一次遍历，选出最小的元素放到第一个位置，下一次，选出次小的元素放到第二个位置，...
        int smallest = 0 ;
        for (int i = 0; i < nums.size() - 1; ++i) {
   
            smallest = i;
            for (int j = i + 1; j < nums.size(); ++j) {
   
                if (nums[j] < nums[smallest]) 
                    smallest = j;
            }
            swap(nums[i], nums[smallest]);
        }
    }
    //6.堆排序
    //堆是一个近似完全二叉树的结构，假设数组是二叉树的顺序存储方式 
    //时间复杂度 O(NlogN)
    static void HeapSort (vector<int>& nums) {
   
        int len = nums.size();
        //建立大顶堆
        for (int i = len / 2 - 1;i >= 0; --i) {
   
            MaxHeaplify(nums, i, len - 1); 
        }
        //调整
        for (int i = len - 1; i > 0; --i) {
   
            swap(nums[0], nums[i]);//将根结点元素（最大值）放到排序区
            MaxHeaplify(nums, 0, i - 1);//对未排序区重新进行最大堆调整
        }
    }
    static void MaxHeaplify (vector<int>& nums, int start, int end) {
   
        //最大堆调整，使根结点的元素值最大，注意，单独的这个函数不足以使最大堆有序，只是保证根结点是最大值
        int dad = start;
        int son = start * 2 + 1;
        while (son <= end) {
   
            if (son + 1 <= end && nums[son + 1] > nums[son]) {
    //选取最大的子结点
                son++;
            }
            if (nums[dad] > nums[son]) {
    //如果父结点大于子结点，退出
                return;
            } else {
   
                swap(nums[dad], nums[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    }
    //归并
    //7. 二路归并排序
    //分治思想，将两个小的有序数组合并为大的有序数组；
    //时间复杂度：O(NlogN) 空间复杂度：O(N)
    static void MergeSort(vector<int>& nums) {
   
        vector<int> tmp(nums.size());
        MergeSortRecur(nums, tmp, 0, nums.size() - 1);
    }
    static void MergeSortRecur(vector<int>& nums, vector<int>& tmp, int left, int right) {
   
        //分
        if (left >= right) return ;
        int mid = left + ((right - left) >> 1);
        MergeSortRecur(nums, tmp, left, mid);
        MergeSortRecur(nums, tmp, mid + 1, right);

        //治
        for (int i = left; i <= right; ++i) tmp[i] = nums[i];
        for (int i = left, j = mid + 1, k = left; k <= right; ++k) {
   
            if (i == mid + 1) {
    //i到达边界
                nums[k] = tmp[j++];
            } else if (j == right +1 || tmp[i] <= tmp[j]) {
    //j到达边界 或 tmp[i] <= tmp[j]
                nums[k] = tmp[i++];
            } else {
    // tmp[i] > tmp[j]
                nums[k] = tmp[j++];
            }
        } 
    }
    /*非比较类排序算法*/
    //8.计数排序
    //时间复杂度O(N+k) k为数据的最大值
    static void CountingSort(vector<int>& nums) {
   
        //牺牲空间换取时间的一种非比较类排序算法，将数据值作为计数数组里的键值，出现次数作为结果存储下来
        if (nums.size() == 0) return;
        int maxValue = nums[0];
        int minValue = nums[0];
        for (auto i : nums) {
   
            maxValue = max(maxValue, i);
            minValue = min(minValue, i);
        }
        vector<int> count(maxValue - minValue + 1, 0);//计数数组
        vector<int> tmp(nums);//暂存原始数据
        for (auto i: tmp) count[i - minValue]++;//统计每一个数据出现的次数
        for (int i = 1; i < count.size(); ++i) count[i] += count[i - 1];//计算出相同元素在排序后的数组里面最后一个元素的下标
        for (int i = tmp.size() - 1; i >=0; --i) {
   
            nums[count[tmp[i] - minValue] - 1] = tmp[i];
            count[tmp[i] - minValue]--;
        }
        //这个地方也可以顺序遍历，只需要将计数数组加1，然后，计数数组里面记录的是相同元素在排序后的数组里面的第一个下标
    }
    //9.桶排序
    static void BucketSort(vector<int>& nums) {
   
        //计数排序的升级
        int maxValue = nums[0];
        int minValue = nums[0];
        for (auto i : nums) {
   
            maxValue = max(maxValue, i);
            minValue = min(minValue, i);
        }
        int bucketSize = 50;
        int bucketCount = (maxValue - minValue) / bucketSize + 1;
        cout<<buckets.size()<<endl;

        for (int i = 0; i < nums.size(); ++i) {
   
            buckets[(nums[i] - minValue) / bucketSize].push_back(nums[i]);
        }
        for (int i = 0, preCount = 0; i < buckets.size(); ++i) {
   
            //对桶里面的数据进行排序
            CountingSort(buckets[i]);
            for (int j = 0; j < buckets[i].size(); ++j)
                nums[preCount + j] = buckets[i][j];
            preCount += buckets[i].size();
        }
    }
    //10.基数排序
    //依次比较数据每一位，最后得出正确的顺序
    static void RadixSort(vector<int>& nums) {
   
        //相当于有10个桶，每次依据一位进行排序
        int len = nums.size();
        int maxbit = maxBit(nums);
        int radix = 1;
        vector<int> tmp(len);
        vector<int> count(10,0);
        for(int i = 1; i <= maxbit; ++i) {
   
            for (int j = 0; j < 10; ++j) count[j] = 0;
            //统计每一个桶里面的元素个数
            for (int j = 0; j < len; ++j) {
   
                count[(nums[j] / radix) % 10]++;
            } 
            //在tmp中为每一个桶划分位置
            for (int j = 1; j < 10; ++j) count[j] = count[j] + count[j - 1];
            int k;
            for (int j = len - 1; j >= 0; --j) {
   
                k = (nums[j] / radix) % 10;
                tmp[count[k] - 1] = nums[j];
                count[k]--;
            }
            for (int j = 0; j < len; ++j) nums[j] = tmp[j];
            radix *= 10;
        }
    }
    static int maxBit(vector<int>& nums) {
   
        int d = 1;
        int p = 10;
        for (int i = 0; i < nums.size(); ++i) {
   
            while(nums[i] >= p) {
   
                p *= 10;
                d++;
            }
        }
        return d;
    }
};

int main(){
   
    vector<int> nums = {
   25,34,18,67,31,76,100000,1000};
    MySort::PrintSort(nums);
    MySort::BucketSort(nums);
    MySort::PrintSort(nums);
    return 0;
}

十大排序算法归纳总结

文章目录

排序算法

代码实现