C++排序算法总结（附完整cpp程序）

排序算法（C++）写在前面

本文为自己实现的排序算法的简单总结（只有简单的思想 / 思路概括，没有详细的原理分析），主要用于复习，适合于有一定数据结构基础的coder。
持续更新中…(目前只完成了冒泡，选择，插入，希尔，快速，归并，桶，计数；还需要完成的有堆)
最后给出了一个可以运行的.cpp代码，包含所有的排序函数，可以复制后测试。

一、排序总结

算法名称	特点（思想）	时间复杂度	空间复杂度	稳定性
[冒泡](#1. 冒泡排序)	…	O(n^2)	O(1)	稳定
[选择](#2. 选择排序)	每轮选择一个最小的	O(n^2)	O(1)	不稳定
[插入](#3. 插入排序)	将最后一个元素插入到有序序列中	O(n^2)	O(1)	稳定
[希尔](#4. 希尔排序)	多轮插入排序，以gap为间隔，gap初始化为n / 2，每轮gap /= 2	平均O(n^1.3)	O(1)	不稳定
[快速](#5. 快速排序)	选择一个privot，让它左边比它小，右边比它大；递归	O(nlog(n))	O(1)	不稳定
[归并](#6. 归并排序)	参照数组归并的思想，递归	O(nlog(n))	O(n)	稳定
堆		O(nlog(n))		不稳定
[计数](#8. 计数排序)	构建一个max - min大小的count数组（保存每个数字的个数）	O(n + k)	O(k)	稳定
[桶(基数)](#9. 基数排序（桶）)	按照个位，十位，百位…排序	O (nlog®m)		稳定

0. 公共函数

一个swap函数，一个print（打印数组）函数

// 公共函数，交换+打印数组
void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}
void print_arr(vector& arr) {
    for (auto e : arr) {
        cout << e << " ";
    }
    cout << endl;
}

1. 冒泡排序

void BubbleSort() {
    for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n - i - 1; ++j) {
			if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
		}
	}
}

2. 选择排序

每轮选择最小的

// 选择排序 (每次选择最小值)
int FindMinPos(vector& arr, int start_pos) {
    int min_pos = start_pos, min_value = arr[start_pos];
    int n = arr.size();
    for (int i = start_pos + 1; i < n; ++i) {
        if (arr[i] < min_value) {
            min_pos = i;
            min_value = arr[i];
        }
    }
    return min_pos;
}
void SelectSort(vector arr) {
    int n = arr.size();
    for (int i = 0; i < n; ++i) {
        int min_pos = FindMinPos(arr, i);
        if (min_pos != i) {
            swap(arr[min_pos], arr[i]);
        }
    }
    cout << "select sort: ";
    print_arr(arr);
}

3. 插入排序

每轮将最后一个元素插入到有序序列中

// 插入排序(将无序序列插入到有序序列中)
// 每次循环中，最后一个是无序的，前面的都是有序的，只需要移动这个无序元素就行
void InsertSort(vector arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        for (int j = i; j > 0; --j) {
            if (arr[j] < arr[j - 1]) swap(arr[j], arr[j - 1]);
        }
    }
    cout << "insert sort: ";
    print_arr(arr);
}

4. 希尔排序

多次选择排序

// 希尔排序
// 先分组，组内排序，然后分组的gap /= 2
// 其实是多轮插入排序，只不过交换的步长变成gap
void ShellSort(vector arr) {
    int n = arr.size();
    // gap为步长InsertSort()几乎完全一样，只不过用gap替换了原来的1 （0, 即1 - 1，替换为gap - 1）
    for (int gap = n / 2; gap >= 1; gap /= 2) {
        // 这里的代码和
        for (int i = gap; i < n; ++i) {
            for (int j = i; j > gap - 1; j -= gap) {
                if (arr[j] < arr[j - gap]) swap(arr[j], arr[j - gap]);
            }
        }
    }
    cout << "shell sort:  ";
    print_arr(arr);
}

5. 快速排序

每次选择一个数字，让它左边比它小，右边比它大（递归）

// 快速排序
// 每次找到一个基准，分成两份，让左边的都比它小，右边都比它大
int Partition(vector &arr, int low, int high) {
    int pivot_value = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot_value) --high;
        arr[low] = arr[high];
        while(low < high && arr[low] <= pivot_value) ++low;
        arr[high] = arr[low];
    }
    arr[low] = pivot_value;
    return low;
}

void QuickSort(vector& arr, int low, int high) {
    if (low < high) {
        int pivot_pos = Partition(arr, low, high);
        QuickSort(arr, low, pivot_pos - 1);
        QuickSort(arr, pivot_pos + 1, high);
    }
    // cout << "quick sort:  ";
    // print_arr(arr);
}

// 为了不改变原来nums数组，这里我建立一个函数调用QuickSort
void call_QuickSort(vector arr) {
    QuickSort(arr, 0, arr.size() - 1);
    cout << "quick sort:  ";
    print_arr(arr);
}

6. 归并排序

数组归并的思想，递归

注意这里的vec赋值操作vector aux_arr(arr.begin(), arr.end());，并不是引用，而是新建后赋值，详情见C++ vector的赋初值是引用了原来的vector还是新建vector？

// 归并排序
// 2路归并：先22排列有序，然后44，然后88，知道全局有序
void Merge(vector& arr, int low, int mid, int high) {
    // 临时数组(注意这里的赋值操作，并不是引用，而是新建后赋值)
    vector aux_arr(arr.begin(), arr.end());

    int i = low;
    int j = mid + 1;

    // 经典的归并数组（两个需要归并的有序数组分别为aux_arr的low ~ mid和aux_arr的mid+1 ~ high，归并后的数组为arr的low ~ high）
    for (int i = low, k = low, j = mid + 1; i <= mid && j <= high; ++k) {
        if (aux_arr[i] <= aux_arr[j]) {
            arr[k] = aux_arr[i++];
        } else {
            arr[k] = aux_arr[j++];
        }

        // 一个走完，接下来就是直接复制
        while (i <= mid) arr[k] = aux_arr[i++];
        while (j <= high) arr[k] = aux_arr[j++];
    }

}
void MergeSort(vector& arr, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(arr, low, mid);
        MergeSort(arr, mid + 1, high);
        Merge(arr, low, mid, high);
    }
}
void call_MergeSort(vector arr) {
    MergeSort(arr, 0, arr.size() - 1);
}

7. 堆排序 8. 记数排序

创建一个max - min 大小的count数组，存储每个数字出现的个数。

时间复杂度O(n + k)，空间复杂度O(k)，（其中k = max - min）稳定。

——缺点

只能做整数
max - min差距大的时候，空间复杂度太高

// 计数排序，创建一个max - min 大小的count数组，存储每个数字出现的个数
// find_min_and_max_for_count_sort：找到最大最小值
void find_min_and_max_for_count_sort(vector &arr, int &min, int &max) {
    int n = arr.size();

    for (int i = 0; i < n; ++i) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
}
void CountSort(vector arr) {
    int min_num = INT32_MAX, max_num = INT32_MIN;
    find_min_and_max_for_count_sort(arr, min_num, max_num);
    
    vector cnt(max_num - min_num + 1, 0);
    int n = arr.size();

    // 填充cnt数组
    for (int i = 0; i < n; ++i) {
        ++cnt[arr[i] - min_num];
    }

    // 遍历cnt数组，重新赋值给arr
    int arr_index = 0;
    for (int i = 0; i < max_num - min_num + 1; ++i) {
        while (cnt[i] > 0) {
            arr[arr_index++] = i + min_num;
            --cnt[i];
        }
    }

    cout << "count sort: ";
    print_arr(arr);
}

9. 基数排序（桶）

思路很简单，就是创建10个桶，先排个位数（个位数相同的放到一个桶中），然后收集起来，再排十位数，再排百位数…

时间复杂度：；空间复杂度；稳定性：稳定。

——当元素取值范围较大，但元素个数较少时可以利用基数排序

// 基数(桶)排序 radix sort / bucket sort
// bucket sort的辅助函数：求bucket sort的最大轮数（即最高位有多少位）
int bucket_sort_max_round(vector &arr) {
    int max_r = 0;
    int n = arr.size();
    int tmp = arr[0];
    for (int i = 0; i < n; ++i) {
        if (arr[i] > tmp) tmp = arr[i];
    }

    while (tmp) {
        tmp /= 10;
        ++max_r;
    }

    return max_r;
}
void BucketSort(vector arr) {
    int r = bucket_sort_max_round(arr); // 需要的轮数
    int n = arr.size();
    vector> bucket(10, vector(n, 0)); // 10个桶子
    vector bucket_size(10, 0); // 记录每个桶中有多少元素


    for (int i = 0; i < r; ++i) {
        // 每轮开始的时候每个桶的计数清零 （这里不必对桶进行清零，因为保存了桶中当前个数，并且每轮都会覆盖，所以不需要清零）
        for (int k = 0; k < 10; ++k) {
            bucket_size[k] = 0;
        }

        // 放入当前桶中
        for (int j = 0; j < n; ++j) {
            int cur_radix = (arr[j] % (int)pow(10, i + 1)) / (int)pow(10, i);
            bucket[cur_radix][bucket_size[cur_radix]] = arr[j];
            ++bucket_size[cur_radix];
        }

        // 一轮结束 —— 写回到arr中
        int arr_index = 0;
        for (int k = 0; k < 10; ++k) { 
            for (int l = 0; l < bucket_size[k]; ++l) {
                arr[arr_index++] = bucket[k][l];
            }
        }

    }

    cout << "radix (bucket) sort: ";
    print_arr(arr);
}

二、可运行的c++程序（包含以上所有排序的实现） 1. Linux下运行方法

复制以下命令到sort.cpp，保存。然后运行以下命令可以编译运行。

$ g++ -o sort sort.cpp 
$ ./sort

2. 代码如下

// g++ -o sort sort.cpp 

#include 

using namespace std;

void swap(int &a, int &b);
void print_arr(vector& arr);

// 冒泡
void BubbleSort(vector arr);

// 选择
int FindMinPos(vector& arr, int start_pos);
void SelectSort(vector arr);

// 插入
void InsertSort(vector arr);

// 希尔
void ShellSort(vector arr);

// 快速排序
int Partition(vector &arr, int low, int high);
void QuickSort(vector& arr, int low, int high);
void call_QuickSort(vector arr);

// 归并排序
void Merge(vector& arr, int low, int mid, int high);
void MergeSort(vector& arr, int low, int high);
void call_MergeSort(vector arr);

// 桶排序
int bucket_sort_max_round(vector &arr);
void BucketSort(vector arr);

// 计数排序
void find_min_and_max_for_count_sort(vector &arr, int &min, int &max);
void CountSort(vector arr);

int main() {
    vector nums = {9, 6, 11, 3, 5, 4, 2, 1, 12, 0};
    cout << "original array: ";
    print_arr(nums);

    BubbleSort(nums);
    SelectSort(nums);
    InsertSort(nums);
    ShellSort(nums);
    call_QuickSort(nums);
    call_MergeSort(nums);
    BucketSort(nums);
    CountSort(nums);
    exit(0);
}


// 公共函数，交换+打印数组
void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}
void print_arr(vector& arr) {
    for (auto e : arr) {
        cout << e << " ";
    }
    cout << endl;
}


// 冒泡排序
void BubbleSort(vector arr) {
    int n = arr.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
        }
    }
    cout << "bubble sort: ";
    print_arr(arr);
}

// 选择排序 (每次选择最小值)
int FindMinPos(vector& arr, int start_pos) {
    int min_pos = start_pos, min_value = arr[start_pos];
    int n = arr.size();
    for (int i = start_pos + 1; i < n; ++i) {
        if (arr[i] < min_value) {
            min_pos = i;
            min_value = arr[i];
        }
    }
    return min_pos;
}
void SelectSort(vector arr) {
    int n = arr.size();
    for (int i = 0; i < n; ++i) {
        int min_pos = FindMinPos(arr, i);
        if (min_pos != i) {
            swap(arr[min_pos], arr[i]);
        }
    }
    cout << "select sort: ";
    print_arr(arr);
}


// 插入排序(将无序序列插入到有序序列中)
// 每次循环中，最后一个是无序的，前面的都是有序的，只需要移动这个无序元素就行
void InsertSort(vector arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        for (int j = i; j > 0; --j) {
            if (arr[j] < arr[j - 1]) swap(arr[j], arr[j - 1]);
        }
    }
    cout << "insert sort: ";
    print_arr(arr);
}

// 希尔排序
// 先分组，组内排序，然后分组的gap /= 2
// 其实是多轮插入排序，只不过交换的步长变成gap
void ShellSort(vector arr) {
    int n = arr.size();
    // gap为步长InsertSort()几乎完全一样，只不过用gap替换了原来的1 （0, 即1 - 1，替换为gap - 1）
    for (int gap = n / 2; gap >= 1; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            for (int j = i; j > gap - 1; j -= gap) {
                if (arr[j] < arr[j - gap]) swap(arr[j], arr[j - gap]);
            }
        }
    }
    cout << "shell sort:  ";
    print_arr(arr);
}


// 快速排序
// 每次找到一个基准，分成两份，让左边的都比它小，右边都比它大
int Partition(vector &arr, int low, int high) {
    int pivot_value = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot_value) --high;
        arr[low] = arr[high];
        while(low < high && arr[low] <= pivot_value) ++low;
        arr[high] = arr[low];
    }
    arr[low] = pivot_value;
    return low;
}

void QuickSort(vector& arr, int low, int high) {
    if (low < high) {
        int pivot_pos = Partition(arr, low, high);
        QuickSort(arr, low, pivot_pos - 1);
        QuickSort(arr, pivot_pos + 1, high);
    }
    // cout << "quick sort:  ";
    // print_arr(arr);
}

// 为了不改变原来nums数组，这里我建立一个函数调用QuickSort
void call_QuickSort(vector arr) {
    QuickSort(arr, 0, arr.size() - 1);
    cout << "quick sort:  ";
    print_arr(arr);
}


// 归并排序
// 2路归并：先22排列有序，然后44，然后88，知道全局有序
void Merge(vector& arr, int low, int mid, int high) {
    // 临时数组(注意这里的赋值操作，并不是引用，而是新建后赋值)
    // 详情见[C++ vector的赋初值是引用了原来的vector还是新建vector？](https://blog.csdn.net/ahundredmile/article/details/125380441?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165719768416781818789265%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=165719768416781818789265&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-125380441-null-null.185^v2^control&utm_term=vec&spm=1018.2226.3001.4450)
    vector aux_arr(arr.begin(), arr.end());

    int i = low;
    int j = mid + 1;

    // 经典的归并数组（两个需要归并的有序数组分别为aux_arr的low ~ mid和aux_arr的mid+1 ~ high，归并后的数组为arr的low ~ high）
    for (int i = low, k = low, j = mid + 1; i <= mid && j <= high; ++k) {
        if (aux_arr[i] <= aux_arr[j]) {
            arr[k] = aux_arr[i++];
        } else {
            arr[k] = aux_arr[j++];
        }

        // 一个走完，接下来就是直接复制
        while (i <= mid) arr[k] = aux_arr[i++];
        while (j <= high) arr[k] = aux_arr[j++];
    }

}
void MergeSort(vector& arr, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(arr, low, mid);
        MergeSort(arr, mid + 1, high);
        Merge(arr, low, mid, high);
    }
}
void call_MergeSort(vector arr) {
    MergeSort(arr, 0, arr.size() - 1);
}

// 堆排序
void HeapSort() {

}

// 计数

// 基数(桶)排序 radix sort / bucket sort
// bucket sort的辅助函数：求bucket sort的最大轮数（即最高位有多少位）
int bucket_sort_max_round(vector &arr) {
    int max_r = 0;
    int n = arr.size();
    int tmp = arr[0];
    for (int i = 0; i < n; ++i) {
        if (arr[i] > tmp) tmp = arr[i];
    }

    while (tmp) {
        tmp /= 10;
        ++max_r;
    }

    return max_r;
}
void BucketSort(vector arr) {
    int r = bucket_sort_max_round(arr); // 需要的轮数
    int n = arr.size();
    vector> bucket(10, vector(n, 0)); // 10个桶子
    vector bucket_size(10, 0); // 记录每个桶中有多少元素


    for (int i = 0; i < r; ++i) {
        // 每轮开始的时候每个桶的计数清零 （这里不必对桶进行清零，因为保存了桶中当前个数，并且每轮都会覆盖，所以不需要清零）
        for (int k = 0; k < 10; ++k) {
            bucket_size[k] = 0;
        }

        // 放入当前桶中
        for (int j = 0; j < n; ++j) {
            int cur_radix = (arr[j] % (int)pow(10, i + 1)) / (int)pow(10, i);
            bucket[cur_radix][bucket_size[cur_radix]] = arr[j];
            ++bucket_size[cur_radix];
        }

        // 一轮结束 —— 写回到arr中
        int arr_index = 0;
        for (int k = 0; k < 10; ++k) { 
            for (int l = 0; l < bucket_size[k]; ++l) {
                arr[arr_index++] = bucket[k][l];
            }
        }

    }

    cout << "radix (bucket) sort: ";
    print_arr(arr);
}


// 计数排序，创建一个max - min 大小的count数组，存储每个数字出现的个数
// find_min_and_max_for_count_sort：找到最大最小值
void find_min_and_max_for_count_sort(vector &arr, int &min, int &max) {
    int n = arr.size();

    for (int i = 0; i < n; ++i) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
}
void CountSort(vector arr) {
    int min_num = INT32_MAX, max_num = INT32_MIN;
    find_min_and_max_for_count_sort(arr, min_num, max_num);
    
    vector cnt(max_num - min_num + 1, 0);
    int n = arr.size();

    // 填充cnt数组
    for (int i = 0; i < n; ++i) {
        ++cnt[arr[i] - min_num];
    }

    // 遍历cnt数组，重新赋值给arr
    int arr_index = 0;
    for (int i = 0; i < max_num - min_num + 1; ++i) {
        while (cnt[i] > 0) {
            arr[arr_index++] = i + min_num;
            --cnt[i];
        }
    }

    cout << "count sort: ";
    print_arr(arr);
}

运行结果

levi@LEVI1:~/code$ g++ -o sort sort.cpp 
levi@LEVI1:~/code$ ./sort 
original array: 9 6 11 3 5 4 2 1 12 0 
bubble sort: 0 1 2 3 4 5 6 9 11 12 
select sort: 0 1 2 3 4 5 6 9 11 12 
insert sort: 0 1 2 3 4 5 6 9 11 12 
shell sort:  0 1 2 3 4 5 6 9 11 12 
quick sort:  0 1 2 3 4 5 6 9 11 12 
radix (bucket) sort: 0 1 2 3 4 5 6 9 11 12 
count sort: 0 1 2 3 4 5 6 9 11 12

3. 代码说明

以上代码可能有遗漏之处，欢迎指出。

C++排序算法总结（附 完整cpp程序）

C/C++/C#相关栏目本月热门文章

C++排序算法总结（附完整cpp程序）