数据结构：八大常见排序算法详解

排序广泛应用于各类场景，如成绩排名、销量统计等。本文将详细介绍八种常见排序算法。

1. 直接插入排序

直接插入排序的基本思想是：将待排序的关键码值按照大小插入到一个已经有序的序列中，直到将所有的关键码值插入完为止，得到一个新的有序序列。

// 时间复杂度 O(N^2)
void InsertSort(int* arr, int n) {
    for (int i = 0; i < n; ++i) {
        int tmp = arr[i];
        int end = i - 1;
        while (end >= 0) {
            if (arr[end] > tmp) {
                arr[end + 1] = arr[end];
                --end;
            } else {
                break;
            }
        }
        arr[end + 1] = tmp;
    }
}

若 end >= 0，说明应该继续比较当前 end 所处位置的关键码值与待排序关键码值的大小关系。若 end 位置的关键码值大，就将 end 位置的关键码值往后移一步，继续 --end，重复上述步骤，直到 end 位置的关键码值小于等于待排序的关键码值，跳出循环。此时 end+1 的位置就是待排序关键码值应该插入的位置。

2. 希尔排序

希尔排序是对于直接插入排序的一种优化，又叫做缩小增量法。希尔排序的基本思想是：先选定一个整数（通常是 gap=gap/3+1），把待排序文件所有记录分成各组，所有距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后 gap=gap/3+1 得到下一个整数，再将数组分成各组，进行插入排序。当 gap=1 时，就相当于直接插入排序。

void ShellSort(int* arr, int n) {
    int gap = n;
    // gap > 1 都是预排序，目的是为了让数组更接近有序
    while (gap > 1) {
        // 组数越多，循环次数多；组数越少，每组内比较的次数增多
        // 3 是一个折中的取法
        // +1（只有一组，相当于直接插入排序）是为了保证最后一组数据是有序的
        gap = gap / 3 + 1;
        for (int j = 0; j < n; ++j) {
            int tmp = arr[j];
            int end = j - gap;
            while (end >= 0) {
                if (arr[end] > tmp) {
                    arr[end + gap] = arr[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
}

对待排序文件记录进行分组，对每一组的记录先进行排序，若 arr[end]>tmp，将当前 end 位置的记录往后移，更新 end，继续判断 end 位置的关键码值与 tmp 的大小关系，若 arr[end]<tmp，就跳出循环，此时 end+gap 就是待排序关键码值要插入的位置，再重新分组，重复上述步骤。

希尔排序特性总结：

1. 希尔排序是对直接插入排序的优化。
2. gap>1 都是预排序，目的是为了让数组更加接近有序，gap=1，就相当于直接插入排序。

3. 直接选择排序

1. 在元素集合 arr[i]...arr[n-1] 选择最小（或最大）的元素。
2. 若它不是这组元素中的第一个（或最后一个）元素时，就将它与这组元素中的第一个（或最后一个）元素进行交换。
3. 在剩余的元素集合中 arr[i+1]...arr[n-2]，重复上述步骤，直到集合剩余一个元素。

// 时间复杂度 O(N^2)
// 直接选择排序
void SelectSort(int* arr, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        // 最小值和最大值都要从 begin 位置开始找起，因为 begin 位置的元素有可能就是最大值或最小值
        int mini = begin, maxi = begin;
        // 找最大，小值
        for (int i = begin + 1; i <= end; ++i) {
            if (arr[i] > arr[maxi]) {
                maxi = i;
            }
            if (arr[i] < arr[mini]) {
                mini = i;
            }
        }
        if (maxi == begin) {
            maxi = mini;
        }
        swap(&arr[begin], &arr[mini]);
        swap(&arr[maxi], &arr[end]);
        ++begin;
        --end;
    }
}

从 begin~end 区间内 mini 找最小值，maxi 找最大值，找到后 mini 位置的元素与 begin 位置的元素进行交换，maxi 与 end 元素进行交换。

4. 堆排序

堆排序是一种利用堆这种数据结构的排序算法。升序建大堆，降序建小堆。

void AdjustDown(int* arr, int parent, int n) {
    // 左孩子
    int child = 2 * parent + 1;
    while (child < n) {
        // 右孩子大，++child
        if (child + 1 < n && arr[child + 1] > arr[child]) {
            ++child;
        }
        // 孩子节点大于父节点
        if (arr[child] > arr[parent]) {
            swap(&arr[child], &arr[parent]);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

// 堆排序
void HeapSort(int* arr, int n) {
    for (int i = (n - 1 - 1) / 2; i >= 0; --i) {
        AdjustDown(arr, i, n);
    }
    int end = n - 1;
    while (end > 0) {
        swap(&arr[0], &arr[end]);
        AdjustDown(arr, 0, end);
        --end;
    }
}

从最后一棵子树开始进行向下调整算法，直到根节点调整完毕，此时为一个有效的堆。再将根节点与最后一个节点进行交换，调整堆，删除最后一个节点。重复上述步骤，直至元素有序。

5. 归并排序

归并排序采用的是分治法，是将已有序的子序列进行合并，得到一个完全有序的序列。

void _MergeSort(int* arr, int left, int right, int* tmp) {
    if (left >= right) {
        return;
    }
    int mid = ((right - left) >> 1) + left;
    // 划分左右区间
    // 左区间 [left,mid]
    // 右区间 [mid + 1,right]
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);
    // 进行合并
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = begin1;
    while (begin1 <= end1 && begin2 <= end2) {
        if (arr[begin1] > arr[begin2]) {
            tmp[index++] = arr[begin2++];
        } else {
            tmp[index++] = arr[begin1++];
        }
    }
    // 若某子数组有剩余元素，则将该数组剩余元素依次填充
    while (begin1 <= end1) {
        tmp[index++] = arr[begin1++];
    }
    while (begin2 <= end2) {
        tmp[index++] = arr[begin2++];
    }
    for (int i = left; i <= right; ++i) {
        arr[i] = tmp[i];
    }
}

// 归并排序
void MergeSort(int* arr, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n);
    _MergeSort(arr, 0, n - 1, tmp);
    free(tmp);
}

对一个序列不断地进行划分左右区间，直到不能划分为止，再对子区间依次进行排序，合并即可。

6. 计数排序（非比较排序）

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用，操作步骤：

1. 统计相同元素出现次数。
2. 根据统计的结果将序列回收到原来的序列中。

// 计数排序
void CountSort(int* arr, int n) {
    // 求数组内最大，最小值
    int max = arr[0], min = arr[0];
    for (int i = 0; i < n; ++i) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    // 开空间
    int gap = max - min + 1;
    int* count = (int*)calloc(sizeof(int), gap);
    // 统计每一个元素出现的次数
    for (int i = 0; i < n; ++i) {
        count[arr[i] - min]++;
    }
    // 排序
    int index = 0;
    for (int i = 0; i < gap; ++i) {
        while (count[i]--) {
            arr[index++] = i + min;
        }
    }
    free(count);
}

之所以开空间没有按照元素的个数去开空间，是因为如果元素个数非常庞大的情况下，可能会申请失败，浪费空间。因此对原数组进行遍历，求数组内的最大值和最小值，再开辟空间。统计原数组内每一个元素出现的次数，根据统计的结果对序列进行排序。

7. 快速排序

快速排序的基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程。

7.1 Hoare 版本的快速排序

思路：

1. 创建左右指针，确定基准值。
2. 从右往左找比基准值小的，从左往右找比基准值大的，左右指针数据交换，进行下次循环。

// hoare 版本
int _QuickSort(int* arr, int left, int right) {
    int key = left;
    // 如果不++left，那么当 right 指向的数据都大于 key(基准值) 时，会存在越界问题
    ++left;
    while (left <= right) {
        // 从右往左找比基准值小的
        while (left <= right && arr[right] > arr[key]) {
            // arr[right] == arr[key] 要不要交换
            --right;
        }
        // 从左往右找比基准值大的
        while (left <= right && arr[left] < arr[key]) {
            ++left;
        }
        if (left <= right) {
            swap(&arr[left++], &arr[right--]);
        }
    }
    swap(&arr[right], &arr[key]);
    return right;
}

right 指针从右往左找比基准值小的数据，left 指针从左往右找比基准值大的数据，左右指针数据进行交换，继续重复上述步骤。跳出循环之后，right 指向的位置就是基准值的位置。

7.2 挖坑法

思路： 创建左右指针。首先从右往左找比基准值小的数据，找到后放入左边坑中，当前位置变为新的'坑'；然后从左往右找比基准值大的数据，找到后放入右边坑中，当前位置变为新的'坑'，结束循环后，将基准值放入当前'坑'中，返回当前'坑'下标。

// 挖坑法
int _QuickSort1(int* arr, int left, int right) {
    int key = arr[left];
    int hole = left;
    while (left < right) {
        // 从右往左找比基准值小的
        while (left < right && arr[right] >= key) {
            --right;
        }
        arr[hole] = arr[right];
        hole = right;
        // 从左往右找比基准值大的
        while (left < right && arr[left] <= key) {
            ++left;
        }
        arr[hole] = arr[left];
        hole = left;
    }
    arr[hole] = key;
    return hole;
}

7.3 Lomuto 前后指针法

思路： 创建前后指针，从左往右找比基准值小的数据进行交换，使小的数据都排在基准值左边。

int _QuickSort2(int* arr, int left, int right) {
    int key = left;
    int prev = left, cur = prev + 1;
    while (cur <= right) {
        // 从左往右找比基准值小的数据
        if (arr[cur] < arr[key] && ++prev != cur) {
            swap(&arr[prev], &arr[cur]);
        }
        ++cur;
    }
    swap(&arr[prev], &arr[key]);
    return prev;
}

// 快速排序
void QuickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int key = _QuickSort(arr, left, right);
    // 划分左右序列
    QuickSort(arr, left, key - 1);
    QuickSort(arr, key + 1, right);
}

基准值确定之后，在对原数组进行左右区间划分，重复上述步骤。

7.4 非递归版本的快速排序

// 非递归版本（栈实现）
void QuickSortNonR(int* arr, int left, int right) {
    Stack s;
    // 栈初始化
    StackInit(&s);
    // 栈顶插入数据
    StackPush(&s, right);
    StackPush(&s, left);
    // 判断栈是否为空
    while (!StackEmpty(&s)) {
        // 取栈顶数据
        int begin1 = StackTop(&s);
        StackPop(&s);
        int end1 = StackTop(&s);
        StackPop(&s);
        int key = begin1;
        int prev = begin1;
        int cur = prev + 1;
        while (cur <= end1) {
            if (arr[cur] < arr[key] && ++prev != cur) {
                swap(&arr[cur], &arr[prev]);
            }
            ++cur;
        }
        swap(&arr[prev], &arr[key]);
        if (prev + 1 < end1) {
            StackPush(&s, end1);
            StackPush(&s, prev + 1);
        }
        if (begin1 < prev - 1) {
            StackPush(&s, prev - 1);
            StackPush(&s, begin1);
        }
    }
    StackDestroy(&s);
}

先入右区间的左右端点，再入左区间的左右端点，因为栈遵从先入后出的原则。