冒泡排序
思想：每一轮确定一个最大值移到最右边。
点击查看代码
for(int i = n; i >= 1; i --) {
for(int j = 1; j < i; j ++) {
if(a[j] > a[j + 1]) swap(a[j],a[j + 1]);
}
}
选择排序
思想：与冒泡相似。
点击查看代码
for(int i = n; i >= 1; i --) {
int max_id = 0;
for(int j = 1; j <= i; j ++) {
if(a[j] > a[max_id]) max_id = j;
}
swap(a[i],a[max_id]);
}
插入排序
思想：将待确定元素插到已排序序列中。
点击查看代码
for(int i = 2; i <= n; i ++) {
int val = a[i],j;
for(j = i; i > 1 && val < a[j - 1]; j --) {
a[j] = a[j - 1];
}
a[j] = val;
}
快速排序
思想：基于分治法，将一个数组分为两个子数组，其中一个数组的所有元素都小于另一个子数组的元素，然后递归地对这两个数组进行排序。
点击查看代码
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
归并排序
思想：与快速排序类似，也是基于分治法地排序方法。将一个数组分为两个子数组，分别排序再合并。
点击查看代码
void merg(int q[], int l, int r)
{
if (l >= r) return;
int mid = (l + r) >> 1;
merg(q, l, mid);
merg(q, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r) {
if(q[i] < q[j]) tmp[k ++] = q[i ++];
else tmp[k ++] = q[j ++];
}
while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++] = q[j ++];
for(i = l,j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
桶排序
思想：桶排序(Bucket sont)是一种非比较的排序算法。桶排序采用了一些分类和分治的思想，把元素的值域分成若干段，每一段对应一个桶。在排序的时候，首先把每一个元素放到其对应的桶中，再对每一个桶中的元素分别排序，再按顺序把每个桶中的元素依次取出，合并成最终答案。
点击查看代码
vector<int> bucket[MAXN];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) {
int x;
cin >> x;
bucket[x / 1000].push_back(x);
}
for (int i = 0; i < MAXN; i ++ ) {
sort(bucket[i].begin(), bucket[i].end());
}
for (int i = 0; i < MAXN; i ++ ) {
for (auto item: bucket[i]) {
cout << item << " ";
}
}
cout << endl;
}