最近在看数据结构，学到了几种新的排序算法，记录下来，供以后复习
排序算法
冒泡排序
/**
* @brief 冒泡排序的基本思想就是不断比较相邻的两个数，
* 让较大的元素不断地往后移。经过一轮比较，就选出最大的数；
* 经过第2轮比较，就选出次大的数，以此类推。
* 一定要经过 N-1 轮比较
* @param array 数组
* @param n 数组元素个数
* @return
*/
void bubble_sort(int array[], int n){
for (int i = 0; i < n - 1; i++)
{
bool sorted = true; // 优化了一下
for (int j = 0; j < n - i - 1; j++)
{
if (array[j] > array[j + 1])
{
sorted = false;
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
if (sorted == true)
break; // 没有发生数据交换的话说明排序完成了
}
}
选择排序
/**
* @brief 选择排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
* 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
* 以此类推，直到所有元素均排序完毕。
* @param a 数组名
* @param n 数组元素个数
* @return
*/
void selection_sort(int a[], int n){
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[min])
min = j;
}
if (min != i){
// 这种交换方式更好，原地交换
a[i] = a[i] + a[min];
a[min] = a[i] - a[min];
a[i] = a[i] - a[min];
}
}
}
插入排序
/**
* @brief 插入算法的核心思想是取未排序区间中的元素，
* 在已排序区间中找到合适的插入位置将其插入，
* 并保证已排序区间数据一直有序。
* 重复这个过程，直到未排序区间中元素为空，算法结束
* @param a 数组名
* @param n 数组元素大小
* @return
*/
void insertion_sort(int a[], int n){
for (int i = 1; i < n; i++)
{
int val = a[i]; // 要保护现场，不然值会被更改
int j = i - 1;
for (; j >= 0; j--)
{
if (a[j] > val)
{
a[j + 1] = a[j];
}
else { // 没有 break 的话就得不到正确答案
break;
}
}
/*
* 注意是 j + 1，这个我想了很久，其实很简单，
* 因为跟 a[j] 比较，那当然是插入在 a[j + 1] 了
*/
a[j + 1] = val;
}
}
归并排序
/**
* @brief 自己写的，写了很久，总算写出来的时候的成就感真好！
* @param a 数组名
* @param begin 排序起点
* @param middle 排序中点
* @param end 排序末尾
*/
void merge(int a[], int begin, int middle, int end)
{
// n1,n2可以自己画图得出个数
int n1 = middle - begin + 1;
int n2 = end - middle;
int *left = new int[n1];
int *right = new int[n2];
for (int i = 0; i < n1; i++){
left[i] = a[begin + i];
}
for (int j = 0; j < n2; j++){
right[j] = a[middle + j + 1];
}
for (int i = 0, j = 0, k = begin; k <= end; k++){
if (i == n1){
a[k] = right[j++];
continue;
}
if (j == n2){
a[k] = left[i++];
continue;
}
if (left[i] <= right[j]){
a[k] = left[i++];
}
else {
a[k] = right[j++];
}
}
delete[]left;
delete[]right;
}
void merge_sort(int a[], int begin, int end)
{
if (begin >= end)
return;
int middle = (begin + end) / 2;
merge_sort(a, begin, middle);
merge_sort(a, middle + 1, end);
merge(a, begin, middle, end);
}
快速排序
/**
* @brief quick_sort 思想就是挑一个参考点（这里是数组最后一个元素）
* 使得参考点前的元素都小于他，之后的元素都大于他
* 然后就这样不断地递归调用，直至不满足条件
* 这里的交换操作可以用1.申请临时变量 2.就地交换 3.用swap算法
* 但是在这里的while循环李不能用就地交换，我也还不知道原因。。
* @param a
* @param begin
* @param end
*/
void quick_sort(int a[], int begin, int end){
if (begin >= end)
return;
int middle = a[end];
int i = begin, j = end - 1;
while(i < j){ // 退出循环的条件为 i == j
while (j > i && a[i] < middle) {
i++;
}
while (j > i && a[j] >= middle){
j--;
}
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
// swap(a[i], a[j]);
// 这里不能用就地交换，否则结果不对
// a[i] = a[i] + a[j];
// a[j] = a[i] - a[j];
// a[i] = a[i] - a[j];
}
if (a[i] >= a[end]){
// swap(a[i], a[end]);
a[i] = a[i] + a[end];
a[end] = a[i] - a[end];
a[i] = a[i] - a[end];
}
else {
i++;
}
quick_sort(a, begin, i - 1);
quick_sort(a, i + 1, end);
}
性能比较
我用随机生成的数组对各种排序算法的耗时进行测量，结果如下，可见大规模的数据还是快排的速度更加快啊
| n = 1000 | n = 10000 | n = 100000 | |
|---|---|---|---|
| bubble_sort | 4 ms | 466 ms | 36631 ms |
| insertion_sort | 1 ms | 89 ms | 8241 ms |
| selection_sort | 2 ms | 171 ms | 16779 ms |
| merge_sort | 1 ms | 7 ms | 50 ms |
| quick_sort | 0 ms | 1 ms | 29 ms |
附上测试代码，其中 C++ 生成随机数是要用 time 去播种的，觉得有点意思
#include "ctime"
#include "cstdlib"
#include <QDebug>
#include <QTime>
int main()
{
srand(int(time(0)));
int n = 100000, arr[n];
for (int i = 0; i < n; i++){
arr[i] = rand() % 1000;
}
QTime time;
time.start();
merge_sort(arr, 0, n - 1);
qDebug() << time.elapsed();
}
一般排序算法比较的都是时间复杂度，而且时间复杂度的计算可以用 逆序度 来表示，具体的去看王争老师的课程复习一下，在此不赘述了。
关于排序，还有原地排序和稳定排序的说法，所谓稳定排序就是排好序之后，两个相同的元素的顺序和排序之前一样，原地排序就不需要申请额外的内存空间，空间复杂度非常低。下面是各种排序算法的性能比较。
| 时间复杂度 | 稳定排序 | 原地排序 | |
|---|---|---|---|
| bubble_sort | O(n^2) | √ | √ |
| insertion_sort | O(n^2) | √ | √ |
| selection_sort | O(n^2) | × | √ |
| bucket_sort | O(n) | √ | × |
| counting_sort | O(n+k)，k是数据范围 | √ | × |
| radix_sort | O(dn)，d为维度 | √ | × |
| merge_sort | O(nlogn) | √ | × |
| quick_sort | O(nlogn) | × | √ |