| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | in-place | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | in-place | 不稳定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | in-place | 稳定 |
| 希尔排序 | O(n log n) | O(n log^2 n) | O(n log^2 n) | O(1) | in-place | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | out-place | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n^2) | O(log n) | in-place | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | in-place | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | out-place | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n^2) | O(n+k) | out-place | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | out-place | 稳定 |
1、冒泡排序
#include<iostream>
using namespace std;
int a[100005];
void swap(int&a, int&b) {
int t = a;
a = b;
b = t;
}
void bubbleSort(int a[], int length) {
for (int i = length; i > 1; i--) {
bool re = true;
for (int j = 1; j < i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
re = false;
}
}
if (re) {
break;
}
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
bubbleSort(a, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}2、选择排序
#include<iostream>
using namespace std;
int a[100005];
void swap(int&a, int&b) {
int t = a;
a = b;
b = t;
}
void selectSort(int a[], int length) {
for (int i = length; i > 1; i--) {
int max = 1;
for (int j = 2; j <= i; j++) {
if (a[j] > a[max]) {
max = j;
}
}
if (i != max) {
swap(a[i], a[max]);
}
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
selectSort(a, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}3、插入排序
#include<iostream>
using namespace std;
int a[100005];
void swap(int&a, int&b) {
int t = a;
a = b;
b = t;
}
void insertSort(int a[], int length) {
for (int i = 2; i <= length; i++) {
int j = i - 1;
while (j >= 1 && a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
j--;
}
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
insertSort(a, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}4、希尔排序
#include<iostream>
using namespace std;
int a[100005];
void swap(int&a, int&b) {
int t = a;
a = b;
b = t;
}
void shellSort(int a[], int length) {
for (int gap = length / 2; gap > 0; gap /= 2) {
for (int i = gap + 1; i <= length; i++) {
int j = i - gap;
while (j >= 1 && a[j] > a[j + gap]) {
swap(a[j], a[j + gap]);
j -= gap;
}
}
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
shellSort(a, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}5、归并排序
#include<iostream>
using namespace std;
int a[100005];
void swap(int&a, int&b) {
int t = a;
a = b;
b = t;
}
void merge(int a[], int begin,int mid,int end) {
int temp[end-begin+1];
int i=begin,j=mid+1,k=0;
while(i<=mid&&j<=end){
temp[k++]=a[i]<a[j]?a[i++]:a[j++];
}
while(i<=mid){
temp[k++]=a[i++];
}
while(j<=end){
temp[k++]=a[j++];
}
k=0;
while(k<end-begin+1){
a[begin+k]=temp[k];
k++;
}
}
void mergeSort(int a[],int begin,int end){
if(begin==end){
return;
}
int mid=(begin+end)/2;
mergeSort(a,begin,mid);
mergeSort(a,mid+1,end);
merge(a,begin,mid,end);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
mergeSort(a, 1, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}6、快速排序
#include<iostream>
using namespace std;
int a[100005];
void swap(int&a, int&b) {
int t = a;
a = b;
b = t;
}
void quickSort(int a[], int begin, int end) {
if (begin >= end) {
return;
}
int t = a[begin];
int i = begin, j = end;
while (i < j) {
while (a[j] > t) {
j--;
}
while (a[i] <= t && i < j) {
i++;
}
if (i != j) {
swap(a[i], a[j]);
}
}
swap(a[begin], a[i]);
quickSort(a, begin, i - 1);
quickSort(a, i + 1, end);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
quickSort(a, 1, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}7、堆排序
#include<iostream>
using namespace std;
int a[100005];
void swap(int&a, int&b) {
int t = a;
a = b;
b = t;
}
void adjust(int a[], int end, int parent) {
int child = parent * 2;
if (child + 1 <= end && a[child] < a[child + 1]) {
child++;
}
if (a[child] > a[parent]) {
swap(a[child], a[parent]);
if (child <= end / 2) {
adjust(a, end, child);
}
}
}
void heapSort(int a[], int length) {
for (int i = length; i > 1; i--) {
for (int j = i / 2; j >= 1; j--) {
adjust(a, i, j);
}
swap(a[1], a[i]);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
heapSort(a, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}8、计数排序
#include<iostream>
using namespace std;
int a[100005];
void swap(int&a, int&b) {
int t = a;
a = b;
b = t;
}
void countingSort(int a[], int length) {
int temp[100005] = {0};
for (int i = 1; i <= length; i++) {
temp[a[i]]++;
}
int k = 1;
for (int i = 1; i <= 100000; i++) {
for (int j = 0; j < temp[i]; j++) {
a[k++] = i;
}
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
countingSort(a, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}9、桶排序
工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序。
10、基数排序
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
标签：log,int,void,算法,place,swap,经典,排序 From： https://blog.csdn.net/xhbqy/article/details/142107549