Skip to content

Latest commit

 

History

History
269 lines (212 loc) · 8.19 KB

排序算法总结.md

File metadata and controls

269 lines (212 loc) · 8.19 KB
Raw

算法分类

常用的排序算法：快速排序、归并排序，堆排序、计数排序（较常用）

排序方法分类

  • 基于比较的方法：通过比较元素间的相对大小进行排序

    • 快速排序
    • 归并排序
    • 冒泡排序
    • 选择排序
    • 插入排序
    • 希尔排序
    • 堆排序

  • 基于非比较（桶）的排序方法

    • 计数排序
    • 桶排序
    • 基数排序

时空复杂度和稳定性

时空复杂度

image-20220328193624273.png

稳定性

  • 稳定排序：冒泡、归并、插入 + 基于非比较的排序（计数、桶、基数），其中桶排序的稳定性和选用的排序方法有关。
  • 不稳定排序：除了稳定的就是不稳定的，快排、选择、希尔、堆排。

算法实现

八大排序算法代码模板，桶排序实现方式不唯一，基数排序基本不用，就不实现啦~

注意：这里堆排序下标从 1 开始处理比较方便。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

// 快速排序：找一个基准值 x，将比 x 大的数放到 x 的后面，比 x 小的数放到 x 的前面，递归左边部分和右边部分
void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;
    
    int mid = l + r >> 1;
    int x = nums[mid], i = l - 1, j = r + 1;
    while (i < j) {
        do i ++ ; while (nums[i] < x);
        do j -- ; while (nums[j] > x);
        if (i < j) swap(nums[i], nums[j]);
    }
    
    quickSort(nums, l, j), quickSort(nums, j + 1, r);
}

// 归并排序：先向下拆分，直到每个区间只剩一个元素，然后两两区间进行两路归并排序，再往上合并，最后将排序后的数组放到原数组中。
void mergeSort(vector<int>& nums, int l, int r, vector<int>& tmp) {
    if (l >= r) return;
    
    int mid = l + r >> 1;
    mergeSort(nums, l, mid, tmp), mergeSort(nums, mid + 1, r, tmp);
    
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] < nums[j]) tmp[k ++ ] = nums[i ++ ];
        else tmp[k ++ ] = nums[j ++ ];
    }
    
    while (i <= mid) tmp[k ++ ] = nums[i ++ ];
    while (j <= r) tmp[k ++ ] = nums[j ++ ];
    
    for (int i = l, k = 0; i <= r; i ++ ) nums[i] = tmp[k ++ ];
}

// 冒泡排序：比较相邻两个元素的大小，将最大的元素放到数组的末尾，每次排序可以确定一个值的位置，最多经过 n - 1 趟排序即可排序完成
void bubbleSort(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 selectSort(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]);
    }
}

// 插入排序：维护两个区间，一个是已排序区间， 初始状态只有第一个数，另一个是未排序区间，每次从未排序区间中取一个数 x，从已排序区间中找到小于 x 的位置 j，然后将其放到 j + 1 位置上，直到所有数都插入完成。
void insertSort(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i ++ ) {
        int x = nums[i], j = i - 1;
        while (j >= 0 && nums[j] >= x) {
            nums[j + 1] = nums[j];
            j -- ;            
        }
        nums[j + 1] = x;
    }
}

// 插入排序 2：和方法 1 思想是一样的，区别就是：不采用向后移动元素的方式插入，而是用交换的方式找到这个数应该放的位置。
void insertSort2(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i ++ ) {
        for (int j = i - 1; j >= 0 && nums[j] >= nums[j + 1]; j -- ) 
            swap(nums[j], nums[j + 1]);
    }
}

// 希尔排序：对比 [插入排序 2] 记忆；首先将数组进行分组，组内再用插入排序进行排序，最后合并起来就是排序后的结果。
void shellSort(vector<int>& nums) {
    int n = nums.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i ++ ) {
            for (int j = i - gap; j >= 0 && nums[j] >= nums[j + gap]; j -= gap) {
                swap(nums[j], nums[j + gap]);
            }
        }
    }
}


// 堆 - 向下调整：找出当前节点 u 和左右儿子值的的最大者 t，如果当前节点 u 不是最大值，那么将 u 和 t 的值交换，此时节点 u 是堆顶且是最大值，递归向下调整节点 t
void down(vector<int>& nums, int n, int u) {
    int t = u, left = u * 2, right = u * 2 + 1;
    if (left <= n && nums[left] > nums[t]) t = left;
    if (right <= n && nums[right] > nums[t]) t = right;
    if (u != t) {
        swap(nums[u], nums[t]);
        down(nums, n, t);
    }
}

// 堆排序 - 下标从 1 开始
void heapSort(vector<int>& nums, int size) {
    int n = size;
    // 建堆
    for (int i = n / 2; i >= 1; i -- ) down(nums, n, i);
    
    // 堆排序：每次将堆顶和待排序区间的最后一个元素交换，然后新的堆顶再向下调整
    for (int i = 1; i <= size; i ++ ) {
        swap(nums[1], nums[n]);
        n -- ;
        down(nums, n, 1);
    }
}

// 堆排序 - 下标从 0 开始
/*void down(vector<int>& nums, int n, int u) {
    int t = u, left = u * 2, right = u * 2 + 1;
    if (left <= n && nums[left] > nums[t]) t = left;
    if (right <= n && nums[right] > nums[t]) t = right;
    if (u != t) {
        swap(nums[u], nums[t]);
        down(nums, n, t);
    }
}

void heapSort(vector<int>& nums, int size) {
    int n = size;
    
    // 建堆
    for (int i = n / 2; i >= 1; i -- ) down(nums, n, i);
    
    // 堆排序
    for (int i = 1; i <= size; i ++ ) {
        swap(nums[1], nums[n]);
        n -- ;
        down(nums, n, 1);
    }
}*/

// 计数排序：开数组数值范围的桶，每个元素一个桶，每个桶记录每个元素出现的次数，最后遍历桶输出
void countingSort(vector<int>& nums) {
    int n = nums.size();
    // 开一个桶，假设最大值是 100
    vector<int> cnt(101, 0);
    
    // cnt 记录每个元素出现的次数
    for (int i = 0; i < n; i ++ ) cnt[nums[i]] ++ ;
    
    for (int i = 0, k = 0; i <= 100; i ++ ) {
        // 将桶里的数放到原数组中
        while (cnt[i]) {
            nums[k ++ ] = i;
            cnt[i] -- ;
        }
    }
}

int main()
{
    /* 测试数据
        2
        5
        5 2 3 1 4
        10
        6 8 1 3 2 5 9 7 4 0
    */
    int T;
    cin >> T;
    while (T -- ) {
        int n;
        cin >> n;
        
        vector<int> nums(n);
        for (int i = 0; i < n; i ++ ) cin >> nums[i];
        
        // quickSort(nums, 0, nums.size() - 1);
        // vector<int> tmp(n);
        // mergeSort(nums, 0, nums.size() - 1, tmp);
        // bubbleSort(nums);
        // selectSort(nums);
        // insertSort(nums);
        // insertSort2(nums);
        // shellSort(nums);
        
        // vector<int> nums(n + 1);
        // for (int i = 1; i <= n; i ++ ) cin >> nums[i];
        // heapSort(nums, n); // 堆排序下标从 1 开始比较好写，其他排序从 0 开始
        // for (int i = 1; i <= n; i ++ ) cout << nums[i] << " ";
        
        // countingSort(nums);
        
        for (int i = 0; i < n; i ++ ) cout << nums[i] << " ";
        cout << endl;
    }
    
    return 0;
}

外部排序

10G数据，1G内存，如何排序？

PS：面试常考题

学习资料

练习地址

精选资料

其他资料