「数组」十大排序：精讲与分析（C++）

概述

截止目前，我们已经讲解并分析了十种最常见的排序算法，下附对应文章链接和全体Code。

链接

「数组」冒泡排序|选择排序|插入排序 / 及优化方案（C++）

「数组」归并排序 / if语句优化|小区间插入优化（C++）

「数组」快速排序 / 随机值优化|小区间插入优化（C++）

「数组」堆排序 / 大根堆优化（C++）

「数组」希尔排序 / 区间增量优化（C++）

「数组」计数排序|桶排序|基数排序（C++）

Code

#pragma once
using namespace std;
void show(int arr[], int len) {for (int i = 0; i < len; i++)cout << arr[i] << ' ';cout << endl;
}
void swap(int& a, int& b) {int temp = b;b = a, a = temp;
}
//冒泡排序
void bubble_sort(int arr[], int len) {while (len--) {for (int i = 0; i < len; i++) {if (arr[i + 1] < arr[i])swap(arr[i + 1], arr[i]);}}
}
void bubble_sort_pro(int arr[], int len) {bool flag = true;while (len-- && flag) {flag = false;for (int i = 0; i < len; i++) {if (arr[i + 1] < arr[i]) {swap(arr[i + 1], arr[i]);flag = true;}}}
}
//选择排序
void selection_sort(int arr[], int len) {for (int i = 0; i < len ; i++) {int min = i;for (int j = i + 1; j < len ; j++) if (arr[j] < arr[min])min = j;swap(arr[i], arr[min]);}
}
void selection_sort_pro(int arr[], int len) {for (int i = 0; i <= len / 2; i++) {int min = i, max = i,j;for (j = i + 1; j < len - i; j++) {if (arr[j] < arr[min])min = j;if (arr[j] > arr[max])max = j;}if (max==i)max = min;swap(arr[i], arr[min]); swap(arr[len - i - 1], arr[max]); }
}
//插入排序
void insertion_sort(int arr[], int len) {for (int i = 1; i < len; i++) {int temp = arr[i], j = i - 1;for (; j >=0; j--) {if (temp<arr[j])arr[j + 1] = arr[j];else break;}arr[j+1] = temp;}
}
void insertion_sort_pro(int arr[], int len) {for (int i = 1; i < len; i++) {int temp = arr[i], j = i - 1;int l = -1, r = i;while (l + 1 != r) {int mid = (l + r) / 2;if (arr[mid] >arr[i])r = mid;else l = mid;}for (; j >=r; j--)arr[j + 1] = arr[j];arr[j+1] = temp;}
}
//归并排序（分治）
void merge(int arr[], int l, int m, int r, int assist[]) {memcpy(&assist[l], &arr[l], sizeof(int) * (r - l));int i, j, k;for (i = l, j = m, k = l;; k++) {if (i == m || j == r)break;if (assist[i] <= assist[j])arr[k] = assist[i++];else arr[k] = assist[j++];}while (i != m)arr[k++] = assist[i++];while (j != r)arr[k++] = assist[j++];
}
void recursion(int arr[], int l, int r, int assist[]) {if (r - l <= 1)return;int m = (l + r) / 2;recursion(arr, l, m, assist);recursion(arr, m, r, assist);merge(arr, l, m, r, assist);
}
void merge_sort(int arr[], int len) {int* assist = new int[len];recursion(arr, 0, len, assist);delete[] assist;
}
void merge_if(int arr[], int l, int m, int r, int assist[]) {if (arr[m - 1] <= arr[m])return;memcpy(&assist[l], &arr[l], sizeof(int) * (r - l));int i, j, k;for (i = l, j = m, k = l;; k++) {if (i == m || j == r)break;if (assist[i] <= assist[j])arr[k] = assist[i++];else arr[k] = assist[j++];}while (i != m)arr[k++] = assist[i++];while (j != r)arr[k++] = assist[j++];
}
void recursion_with_insertion(int arr[], int l, int r, int assist[]) {if (r - l <= 20) {insertion_sort(&arr[l], r - l);return;}int m = (l + r) / 2;recursion_with_insertion(arr, l, m, assist);recursion_with_insertion(arr, m, r, assist);merge_if(arr, l, m, r, assist);
}
void MGsort(int arr[], int len) {int* assist = new int[len];recursion_with_insertion(arr, 0, len, assist);delete[] assist;
}
//快速排序（冒泡+分治）
int partition(int arr[], int l, int r) {swap(arr[l], arr[r-1]);int i, j;for (i = l, j = l; j <= r - 1; j++) if (arr[j] <= arr[r - 1])swap(arr[i++], arr[j]);return i-1;
}
void quick_sort(int arr[], int l,int r) {if (r-l<=1)return ;int pos = partition(arr, l, r);quick_sort(arr, l, pos);quick_sort(arr, pos + 1, r);
}
#include <random>
mt19937 mt;
int random_partition(int arr[], int l, int r) {int pos = mt() % (r - l) + l;swap(arr[pos], arr[r - 1]);int i, j;for (i = l, j = l; j <= r - 1; j++)if (arr[j] <= arr[r - 1])swap(arr[i++], arr[j]);return i - 1;
}
void QKsort(int arr[], int l, int r) {if (r - l <= 20) {insertion_sort(&arr[l],r-l); return;}int pos = random_partition(arr, l, r);QKsort(arr, l, pos);QKsort(arr, pos + 1, r);
}
//堆排序（选择+分治）
#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void up(int arr[], int idx) {if (idx && arr[father(idx)] > arr[idx]) {swap(arr[father(idx)], arr[idx]);up(arr, father(idx));}
}
void down(int arr[], int idx, int size) {int pos;if (rchild(idx) < size)pos = arr[lchild(idx)] < arr[rchild(idx)] ? lchild(idx) : rchild(idx);else if (lchild(idx) < size)pos = lchild(idx);else return;if (arr[idx] > arr[pos]) {swap(arr[idx], arr[pos]);down(arr,pos,size);}
}
void heap_sort(int arr[], int len) {int size = 0;for (int i = 0; i < len; i++) {up(arr, i);size++;}int* assist = new int[len];for (int j = 0; j < len; j++) {assist[j] = arr[0];arr[0] = arr[--size];down(arr,0,size);}memcpy(arr, assist, sizeof(int) * len);delete[] assist;
}
void bigger_up(int arr[], int idx) {if (idx && arr[father(idx)] < arr[idx]) {swap(arr[father(idx)], arr[idx]);bigger_up(arr, father(idx));}
}
void smaller_down(int arr[], int idx, int size) {int pos;if (rchild(idx) < size)pos = arr[lchild(idx)] > arr[rchild(idx)] ? lchild(idx) : rchild(idx);else if (lchild(idx) < size)pos = lchild(idx);else return;if (arr[idx] < arr[pos]) {swap(arr[idx], arr[pos]);smaller_down(arr, pos, size);}
}
void HPsort(int arr[], int len) {int size = 0;for (int i = 0; i < len; i++,size++) bigger_up(arr, i);while (size--) {swap(arr[0], arr[size]);smaller_down(arr, 0, size);}
}
//希尔排序（插入+分治）
void shell_sort(int arr[], int len) {int d = len;while (d /= 2) {for (int group = 0; group < d; group++) {for (int i = group+d; i < len; i += d) {int temp = arr[i], j = i - d;for (; j >= 0; j -= d) {if (temp < arr[j])arr[j + d] = arr[j];else break;}arr[j + d] = temp;}}}
}
void SLsort(int arr[], int len) {int d = len;while (d=d/3+1) {for (int group = 0; group < d; group++) {for (int i = group + d; i < len; i += d) {int temp = arr[i], j = i - d;for (; j >= 0; j -= d) {if (temp < arr[j])arr[j + d] = arr[j];else break;}arr[j + d] = temp;}}if (d == 1)break;}
}
//计数排序（基础非比较排序）
#include <algorithm>
void count_sort(int arr[], int len) {int size = *max_element(arr, arr + len) + 1;int* cnt=new int[size]();for (int i = 0; i < len; i++)cnt[arr[i]]++;for (int j = 0, k = 0; j < size; j++)while(cnt[j])arr[k++] = cnt[j]--;delete[] cnt;
}
//桶排序（大范围非比较+小区间比较排序）
#include <algorithm>
#include <vector>
void bucket_sort(int arr[], int len) {using bucket = vector<int>;int max_limit = *max_element(arr, arr + len);int min_limit = *min_element(arr, arr + len);int num_of_buckets = (max_limit - min_limit) / len + 1;int size_of_bucket = (max_limit - min_limit) / num_of_buckets + 1;vector<bucket>buckets(num_of_buckets);for (int i = 0; i < len; i++)buckets[(arr[i] - min_limit) / size_of_bucket].push_back(arr[i]);for (bucket& b : buckets)insertion_sort(b.data(), b.size());int k = 0;for (const bucket& b : buckets) {memcpy(arr + k, b.data(), b.size() * sizeof(int));k += b.size();}
}
//基数排序（整数数位非比较排序）
#include <algorithm>
#include <vector>
void radix_sort(int arr[], int len) {using bucket = vector<int>;bucket buckets[10];int limit = *max_element(arr, arr + len);for(int mask=1;mask<limit;mask*=10){for (int i = 0; i < len; i++)buckets[arr[i] / mask % 10].push_back(arr[i]);for (int j = 0, k = 0; j < 10; j++) {memcpy(arr + k, buckets[j].data(), buckets[j].size() * sizeof(int));k += buckets[j].size();buckets[j].clear();}}
}

测试Code

#include <iostream>
#include <Windows.h>
#include "sort.h"
int main()
{int nums = 500000;int* arr1 = new int[nums];int* arr2 = new int[nums];DWORD tick1, tick2;for (int i = 0; i < nums; i++) {int x = mt() % 100000000;arr1[i] =arr2[i]= x;}cout << "________________________________________________________________________________" << endl;cout << "                              data num : "<< nums << endl;cout << "________________________________________________________________________________" << endl;cout << "|         index          |          name          |          time(ms)          "  << endl;cout << "________________________________________________________________________________" << endl;tick1 = GetTickCount64();bubble_sort_pro(arr1, nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            1           |       bubble sort      |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);tick1 = GetTickCount64();selection_sort_pro(arr1, nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            2           |     selection sort     |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);tick1 = GetTickCount64();insertion_sort(arr1, nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            3           |     insertion sort     |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);tick1 = GetTickCount64();MGsort(arr1, nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            4           |       merge sort       |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);tick1 = GetTickCount64();QKsort(arr1,0,nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            5           |       quick sort       |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);tick1 = GetTickCount64();HPsort(arr1, nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            6           |       heap sort        |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);tick1 = GetTickCount64();SLsort(arr1, nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            7           |       shell sort       |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);tick1 = GetTickCount64();count_sort(arr1, nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            8           |       count sort       |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);tick1 = GetTickCount64();bucket_sort(arr1, nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            8           |       bucket sort      |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);tick1 = GetTickCount64();radix_sort(arr1, nums);//show(arr1, nums);tick2 = GetTickCount64();cout << "|            8           |       radidx sort      |         " << tick2 - tick1 << endl;memcpy(arr1, arr2, sizeof(int) * nums);cout << "________________________________________________________________________________" << endl;delete[] arr1;delete[] arr2;return 0;
}