1.冒泡排序
/* 冒泡排序 */
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
2.选择排序
/* 选择排序 */
void selectionSort(int arr[], int n) {
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i; j < n; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
int tmp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = tmp;
}
}
3.插入排序
/* 插入排序 */
void insertionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int current = arr[i + 1]; // 当前元素
int preIndex = i; // 前一元素
while (preIndex >= 0 && current < arr[preIndex]) { // 如果前一元素比当前元素大，则往后移一个位置
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current; // 把当前元素插在首个比当前元素小的下一位
}
}
4.希尔排序
/* 希尔排序 */
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) { // 选择增量为gap，每次gap减半(即分成gap组)
for (int i = gap; i < n; i++) { // 对每个组进行进行(n/gap-1)次排序
// 注意这里不是按组分别排序，而是交叉：先排第0组的第1个，然后第1组的第1个.....然后第0组的第2个，然后第1组的第2个
int current = arr[i]; // 当前元素
int preIndex = i - gap; // 本组前一元素
while (preIndex >= 0 && current < arr[preIndex]) { // 如果本组前一元素比当前元素大，则前一元素移到本组后一个位置
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = current; // 把当前元素插在首个比当前元素小的本组下一位
}
}
}
5.归并排序
void merge(int arr[], int start, int middle, int end) {
vector<int> v; // 创建一个辅助队列，按大小顺序存放左右集合的元素
int i = start, j = middle + 1;
while (i <= middle && j <= end) {
if (arr[i] < arr[j]) {
v.push_back(arr[i++]);
} else {
v.push_back(arr[j++]);
}
}
while (i <= middle) {
v.push_back(arr[i++]);
}
while (j <= end) {
v.push_back(arr[j++]);
}
// 按排好序的元素放回原数组中
for (unsigned int i = 0; i < v.size(); i++) {
arr[start + i] = v[i];
}
}
/* 归并排序 */
void mergeSort(int arr[], int start, int end) {
if (start >= end) { // 如果只有一个元素，则不用继续排，直接返回
return;
}
int middle = (end + start) / 2; // 找到中间位置，左右分别递归排序
mergeSort(arr, start, middle);
mergeSort(arr, middle + 1, end);
merge(arr, start, middle, end); //把左右排序结果合并
}
void mergeSortAdepter(int arr[], int n) {
mergeSort(arr, 0, n - 1);
}
6.快速排序
/* 快速排序 */
void quickSort(int arr[], int left, int right) {
if (left >= right) { // 只剩一个元素则不用再排序
return;
}
int i = left, j = right;
int base = arr[left]; // 设立一个基准，最后目标是基准的左边<=基准，基准的右边>=基准
while (i < j) {
while (i < j && arr[j] >= base) // 从右往左找到一个小于等于基准的A
j--;
while (i < j && arr[i] <= base) // 从左往右找到一个大于等于基准的B
i++;
if (i < j) { // 如果A在B的右边，则交换位置
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 让基准和最后一个<=基准换位，这样保证上述的最后目标
arr[left] = arr[i];
arr[i] = base;
// 递归处理左边和右边的数组
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
void quickSortAdpter(int arr[], int n) {
quickSort(arr, 0, n - 1);
}
7.堆排序
void adjustMaxHead(int arr[], int i, int n) {
//参考堆和完全二叉树的性质，把以i为父节点的堆调整为大顶堆
int maxIndex = i;
if (i * 2 <= n && arr[i * 2] > arr[maxIndex]) { // 如果存在左子树且比当前节点大
maxIndex = i * 2;
}
if (i * 2 + 1 <= n && arr[i * 2 + 1] > arr[maxIndex]) { //如果存在右子树且比当前节点大
maxIndex = i * 2 + 1;
}
if (maxIndex != i) { // 如果当前父节点不是最大值，则父节点与子节点交换
int tmp = arr[maxIndex];
arr[maxIndex] = arr[i];
arr[i] = tmp;
adjustMaxHead(arr, maxIndex, n); // 交换后，递归处理新的子节点，保证新的子节点是大顶堆
}
}
/* 堆排序 */
void headSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
adjustMaxHead(arr, i, n); // 从最后一行的非叶子节点开始，往前遍历，构造一个大顶堆
}
while (n > 0) {
// 把大顶堆的顶（最大值）放在数组最后----又排好一个元素了
int tmp = arr[0];
arr[0] = arr[n];
arr[n] = tmp;
n--;
adjustMaxHead(arr, 0, n); // 然后把剩下的n-1个元素再做同样操作
}
}
void headSortAdapter(int arr[], int n) {
headSort(arr, n - 1);
}
8.计数排序
/* 计数排序 */
void countingSort(int arr[], int n) {
if (n == 0)
return;
// 找出最大值和最小值
int max = arr[0], min = arr[0];
for (int i = 0; i < n; i++) {
max = max > arr[i] ? max : arr[i];
min = min < arr[i] ? min : arr[i];
}
// 为每个可能元素值初始化一个计数器，按出现的次数累加
vector<int> v(max - min + 1, 0);
for (int i = 0; i < n; i++) {
v[arr[i] - min]++;
}
// 根据计数器的顺序和元素出现的次数，写回原数组
int counter = 0;
for (unsigned int j = 0; j < v.size(); j++) {
for (int k = 0; k < v[j]; k++) {
arr[counter++] = j + min;
}
}
}
9.桶排序
/* 桶排序 */
void bucketSort(vector<int>& v, int bucketSize) {
if (v.size() <= 1)
return;
int n = v.size();
// 找出最大值和最小值
int min = v[0], max = v[0];
for (int i = 0; i < n; i++) {
max = max >= v[i] ? max : v[i];
min = min <= v[i] ? min : v[i];
}
// 根据桶尺寸，初始化桶的数量
int bucketCount = (max - min) / bucketSize + 1;
vector<vector<int>> bucket(bucketCount, vector<int>());
for (int i = 0; i < n; i++) {
int bucketIndex = (v[i] - min) / bucketSize;
bucket[bucketIndex].push_back(v[i]); // 按照元素的值装入各自的桶中
}
int index = 0;
for (int i = 0; i < bucketCount; i++) {
// 其实每个桶中可以用其他排序算法，但这里递归用桶排序
if (bucketSize > 1) { // 如果桶尺寸大于1 ,证明可以递归再次排序，直到桶尺寸为1
if (bucketCount == 1) {
bucketSize = 1; // 如果当前只有一个桶了，把桶尺寸收缩为1, 进行最后一次排序
}
bucketSort(bucket[i], bucketSize);
}
// 把已经排好序的桶填回到结果中
for (unsigned int j = 0; j < bucket[i].size(); j++) {
v[index++] = bucket[i][j];
}
}
}
void bucketSortAdepter(int arr[], int n) {
vector<int> v(n);
for (int i = 0; i < n; i++)
v[i] = arr[i];
bucketSort(v, 10);
for (int i = 0; i < n; i++)
arr[i] = v[i];
}
10.基数排序
/* 基数排序 */
void radixSort(int arr[], int n) {
if (0 == n) {
return;
}
// 先找出最大数
int max = arr[0];
for (int i = 0; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 根据最大数找出最多是多少位
int maxDigit = 0;
while (max != 0) {
maxDigit++;
max /= 10;
}
// 从最低位到最高位，按基数重排
int mod = 10, div = 1;
vector<vector<int>> v(10, vector<int>());
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
// 把原数组按基数排序
for (int j = 0; j < n; j++) {
int radix = arr[j] % mod / div;
v[radix].push_back(arr[j]);
}
// 把排了一次序的数放回原数组
int index = 0;
for (int j = 0; j < 10; j++) {
for (unsigned int k = 0; k < v[j].size(); k++) {
arr[index++] = v[j][k];
}
v[j].clear();
}
}
}
汇总：所有排序效率比较
源码:
#include <algorithm>
#include <stdlib.h>
#include <random>
#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <string.h>
#include <time.h>
using namespace std;
#define SIZE 100000
/* 冒泡排序 */
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
/* 选择排序 */
void selectionSort(int arr[], int n) {
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i; j < n; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
int tmp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = tmp;
}
}
/* 插入排序 */
void insertionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int current = arr[i + 1]; // 当前元素
int preIndex = i; // 前一元素
while (preIndex >= 0 && current < arr[preIndex]) { // 如果前一元素比当前元素大，则往后移一个位置
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current; // 把当前元素插在首个比当前元素小的下一位
}
}
/* 希尔排序 */
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) { // 选择增量为gap，每次gap减半(即分成gap组)
for (int i = gap; i < n; i++) { // 对每个组进行进行(n/gap-1)次排序
// 注意这里不是按组分别排序，而是交叉：先排第0组的第1个，然后第1组的第1个.....然后第0组的第2个，然后第1组的第2个
int current = arr[i]; // 当前元素
int preIndex = i - gap; // 本组前一元素
while (preIndex >= 0 && current < arr[preIndex]) { // 如果本组前一元素比当前元素大，则前一元素移到本组后一个位置
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = current; // 把当前元素插在首个比当前元素小的本组下一位
}
}
}
void merge(int arr[], int start, int middle, int end) {
vector<int> v; // 创建一个辅助队列，按大小顺序存放左右集合的元素
int i = start, j = middle + 1;
while (i <= middle && j <= end) {
if (arr[i] < arr[j]) {
v.push_back(arr[i++]);
} else {
v.push_back(arr[j++]);
}
}
while (i <= middle) {
v.push_back(arr[i++]);
}
while (j <= end) {
v.push_back(arr[j++]);
}
// 按排好序的元素放回原数组中
for (unsigned int i = 0; i < v.size(); i++) {
arr[start + i] = v[i];
}
}
/* 归并排序 */
void mergeSort(int arr[], int start, int end) {
if (start >= end) { // 如果只有一个元素，则不用继续排，直接返回
return;
}
int middle = (end + start) / 2; // 找到中间位置，左右分别递归排序
mergeSort(arr, start, middle);
mergeSort(arr, middle + 1, end);
merge(arr, start, middle, end); //把左右排序结果合并
}
void mergeSortAdepter(int arr[], int n) {
mergeSort(arr, 0, n - 1);
}
/* 快速排序 */
void quickSort(int arr[], int left, int right) {
if (left >= right) { // 只剩一个元素则不用再排序
return;
}
int i = left, j = right;
int base = arr[left]; // 设立一个基准，最后目标是基准的左边<=基准，基准的右边>=基准
while (i < j) {
while (i < j && arr[j] >= base) // 从右往左找到一个小于等于基准的A
j--;
while (i < j && arr[i] <= base) // 从左往右找到一个大于等于基准的B
i++;
if (i < j) { // 如果A在B的右边，则交换位置
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 让基准和最后一个<=基准换位，这样保证上述的最后目标
arr[left] = arr[i];
arr[i] = base;
// 递归处理左边和右边的数组
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
void quickSortAdpter(int arr[], int n) {
quickSort(arr, 0, n - 1);
}
void adjustMaxHead(int arr[], int i, int n) {
//参考堆和完全二叉树的性质，把以i为父节点的堆调整为大顶堆
int maxIndex = i;
if (i * 2 <= n && arr[i * 2] > arr[maxIndex]) { // 如果存在左子树且比当前节点大
maxIndex = i * 2;
}
if (i * 2 + 1 <= n && arr[i * 2 + 1] > arr[maxIndex]) { //如果存在右子树且比当前节点大
maxIndex = i * 2 + 1;
}
if (maxIndex != i) { // 如果当前父节点不是最大值，则父节点与子节点交换
int tmp = arr[maxIndex];
arr[maxIndex] = arr[i];
arr[i] = tmp;
adjustMaxHead(arr, maxIndex, n); // 交换后，递归处理新的子节点，保证新的子节点是大顶堆
}
}
/* 堆排序 */
void headSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
adjustMaxHead(arr, i, n); // 从最后一行的非叶子节点开始，往前遍历，构造一个大顶堆
}
while (n > 0) {
// 把大顶堆的顶（最大值）放在数组最后----又排好一个元素了
int tmp = arr[0];
arr[0] = arr[n];
arr[n] = tmp;
n--;
adjustMaxHead(arr, 0, n); // 然后把剩下的n-1个元素再做同样操作
}
}
void headSortAdapter(int arr[], int n) {
headSort(arr, n - 1);
}
/* 计数排序 */
void countingSort(int arr[], int n) {
if (n == 0)
return;
// 找出最大值和最小值
int max = arr[0], min = arr[0];
for (int i = 0; i < n; i++) {
max = max > arr[i] ? max : arr[i];
min = min < arr[i] ? min : arr[i];
}
// 为每个可能元素值初始化一个计数器，按出现的次数累加
vector<int> v(max - min + 1, 0);
for (int i = 0; i < n; i++) {
v[arr[i] - min]++;
}
// 根据计数器的顺序和元素出现的次数，写回原数组
int counter = 0;
for (unsigned int j = 0; j < v.size(); j++) {
for (int k = 0; k < v[j]; k++) {
arr[counter++] = j + min;
}
}
}
/* 桶排序 */
void bucketSort(vector<int>& v, int bucketSize) {
if (v.size() <= 1)
return;
int n = v.size();
// 找出最大值和最小值
int min = v[0], max = v[0];
for (int i = 0; i < n; i++) {
max = max >= v[i] ? max : v[i];
min = min <= v[i] ? min : v[i];
}
// 根据桶尺寸，初始化桶的数量
int bucketCount = (max - min) / bucketSize + 1;
vector<vector<int>> bucket(bucketCount, vector<int>());
for (int i = 0; i < n; i++) {
int bucketIndex = (v[i] - min) / bucketSize;
bucket[bucketIndex].push_back(v[i]); // 按照元素的值装入各自的桶中
}
int index = 0;
for (int i = 0; i < bucketCount; i++) {
// 其实每个桶中可以用其他排序算法，但这里递归用桶排序
if (bucketSize > 1) { // 如果桶尺寸大于1 ,证明可以递归再次排序，直到桶尺寸为1
if (bucketCount == 1) {
bucketSize = 1; // 如果当前只有一个桶了，把桶尺寸收缩为1, 进行最后一次排序
}
bucketSort(bucket[i], bucketSize);
}
// 把已经排好序的桶填回到结果中
for (unsigned int j = 0; j < bucket[i].size(); j++) {
v[index++] = bucket[i][j];
}
}
}
void bucketSortAdepter(int arr[], int n) {
vector<int> v(n);
for (int i = 0; i < n; i++)
v[i] = arr[i];
bucketSort(v, 10);
for (int i = 0; i < n; i++)
arr[i] = v[i];
}
/* 基数排序 */
void radixSort(int arr[], int n) {
if (0 == n) {
return;
}
// 先找出最大数
int max = arr[0];
for (int i = 0; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 根据最大数找出最多是多少位
int maxDigit = 0;
while (max != 0) {
maxDigit++;
max /= 10;
}
// 从最低位到最高位，按基数重排
int mod = 10, div = 1;
vector<vector<int>> v(10, vector<int>());
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
// 把原数组按基数排序
for (int j = 0; j < n; j++) {
int radix = arr[j] % mod / div;
v[radix].push_back(arr[j]);
}
// 把排了一次序的数放回原数组
int index = 0;
for (int j = 0; j < 10; j++) {
for (unsigned int k = 0; k < v[j].size(); k++) {
arr[index++] = v[j][k];
}
v[j].clear();
}
}
}
void testSort(int arr[], int n, string name, function<void(int*, int)> sortFunc) {
int newArr[SIZE] = {0};
memcpy(newArr, arr, sizeof(int) * n);
clock_t start = clock();
sortFunc(newArr, n);
cout << name << "\t usetime: " << clock() - start << "\t";
// cout << " nums:";
// for (int i = 0; i < n; i++) {
// cout << newArr[i] << " ";
// }
cout << '\t' << endl;
}
int main() {
int arr[SIZE] = {0};
srand(time(NULL));
for (int i = 0; i < SIZE; i++) {
arr[i] = rand() % SIZE;
}
testSort(arr, SIZE, "bubbleSort", bubbleSort);
testSort(arr, SIZE, "selectionSort", selectionSort);
testSort(arr, SIZE, "insertionSort", insertionSort);
testSort(arr, SIZE, "shellSort", shellSort);
testSort(arr, SIZE, "mergeSort", mergeSortAdepter);
testSort(arr, SIZE, "quickSort", quickSortAdpter);
testSort(arr, SIZE, "headSort", headSortAdapter);
testSort(arr, SIZE, "countingSort", countingSort);
testSort(arr, SIZE, "bucketSort", bucketSortAdepter);
testSort(arr, SIZE, "radixSort", radixSort);
return 0;
}
View Code
结果：
bubbleSort usetime: 34289
selectionSort usetime: 13229
insertionSort usetime: 8174
shellSort usetime: 31
mergeSort usetime: 172
quickSort usetime: 16
headSort usetime: 15
countingSort usetime: 16
bucketSort usetime: 109
radixSort usetime: 16
这里仅比较了10w个数的排序，再多数据冒泡算法实在太久了。这里深刻认识到幂次级的效率差异比，以后设计代码除了代码整洁，还要考虑下算法效率。