排序算法

排序算法

冒泡排序,插入排序,选择排序

冒泡,插入,选择排序是最基础的交换排序

时间复杂度
$$
O(n^2)
$$
冒泡排序:

冒泡排序是一种离线的算法

1
2
3
4
5
6
7
8
9
10
for(int i = 0; i < n; i++){
bool tmp = 0;
for(int j = 0; j < n - i; j++){
if(a[j] > a[j + 1]){
swap(a[j], a[j + 1]);
tmp = 1;
}
}
if(!tmp) break;
}

插入排序:

插入排序是一种在线的算法

1
2
3
4
5
6
7
8
9
void insert(int arr[], key)
{
int key = arr[len];
while(len > 1 && arr[len - 1] > key){
arr[len] = arr[len - 1];
len--;
}
arr[len] = key;
}

选择排序:

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0; i < n - 1; i++){
int tmp = arr[i];
int mx = i;
for(int j = i + 1; j < n; j++){
if(tmp > arr[i]){
tmp = arr[i];
mx = j;
}
}
if(mx != i) swap(arr[i], arr[mx]);
}

桶排序

桶排序是排序算法的一种,适用于待排序数据值域较小的情况

1
2
3
4
5
6
7
8
int bucket[110];
for(int i = 1; i <= n; i++){
bucket[a[i]]++;
}
for(int i = 0; i <= 100; i++){
if(bucket[i] == 0) continue;
while(bucket[i]--) cout << i << " ";
}

快速排序

1
2
3
4
5
void qsort(int l, int r)
{
int i = l, j = r;
int piovt;
}

归并排序

堆排序