#include <iostream>
using namespace std;
const int N = 100001;
int q[N], n;
//直接插入排序函数
void insert_sort()
{
for(int i = 1; i < n; i ++)
{
int t = q[i], j = i;
while(q[j - 1] > t && j)//j > 0,从q[j]开始往前寻找是否有大于当前q[i]的元素
{
q[j] = q[j - 1];
-- j;
}
q[j] = t;
}
}
//直接插入排序主程序
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
insert_sort();
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
}
#include <iostream>
using namespace std;
const int N = 100001;
int q[N], n;
//折半插入排序函数
void binary_search_insert_sort()
{
for(int i = 1; i < n; i ++)
{
if(q[i - 1] < q[i]) continue;//前面的元素均小于q[i],无需插入
int low = 0, high = i - 1, mid;
int t = q[i];
while(low < high)//寻找插入q[i]的位置
{
mid = (low + high) / 2;
if(q[mid] > t)//二分出第一个大于q[i]的元素q[high]
high = mid;
else
low = mid + 1;
}
for(int j = i - 1; j >= high; j --)
q[j + 1] = q[j];
q[high] = t;
}
}
//折半插入排序主程序
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
binary_search_insert_sort();
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
}
#include <iostream>
using namespace std;
const int N = 100001;
int q[N], n;
//冒泡排序函数
void bubble_sort()
{
for(int i = 0; i < n - 1; i ++)
{
bool has_swap = false;
for(int j = n -1; j > i; j --)
{
if(q[j] < q[j-1])
{
swap(q[j], q[j - 1]);
has_swap = true;
}
}
if(!has_swap) break;
}
}
//冒泡排序主程序
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
bubble_sort();
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
}
#include <iostream>
using namespace std;
const int N = 100001;
int q[N], n;
//简单选择排序函数
void select_sort()
{
for(int i = 0; i < n - 1; i ++)
{
int t = i;//q[i ~ n - 1]中最小值下标
for(int j = i + 1; j < n; j ++)
if(q[j] < q[t])
t = j;
swap(q[i], q[t]);
}
}
//简单选择排序主程序
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
select_sort();
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
}
#include <iostream>
using namespace std;
const int N = 100001;
int q[N], n;
//希尔排序函数
void shall_sort1()//未优化：增量为n/(2^i)
{
for(int d = n / 2; d ; d /= 2)
{
for(int start = 0; start < d; start ++)
{
for(int i = start + d; i < n; i += d)//{(start),start+d,start+2d,...,}start已经有序
{
int t = q[i], j = i;
while(j > start && q[j - d] > t)
{
q[j] = q[j - d];
j -= d;
}
q[j] = t;
}
}
}
}
void shall_sort()//优化后：增量为n/(3^i)
{
for(int d = n / 3; d ; d = d == 2 ? 1 : d / 3)
{
for(int start = 0; start < d; start ++)
{
for(int i = start + d; i < n; i += d)//{(start),start+d,start+2d,...,}start已经有序
{
int t = q[i], j = i;
while(j > start && q[j - d] > t)
{
q[j] = q[j - d];
j -= d;
}
q[j] = t;
}
}
}
}
//希尔排序主程序
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
shall_sort();
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
}
#include <iostream>
using namespace std;
const int N = 100001;
int q[N], n;
//划分函数
int Partition(int a[], int low, int high)//将下标为pivotpos的元素放置到最终位置
{
int pivot = a[low];//将第一个元素作为枢轴元素
while(low < high)
{
while(low < high && a[high] >= pivot) high --;
a[low] = a[high];
while(low < high && a[low] <= pivot) low ++;
a[high] = a[low];
}
a[low] = pivot;
return low;
}
//快速排序函数
void quick_sort(int a[], int low, int high)
{
if(low < high)//判断是否进行快排
{
int pivotpos = Partition(a, low, high);
quick_sort(a, low, pivotpos - 1);
quick_sort(a, pivotpos + 1, high);
}
}
//快速排序主程序
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
quick_sort(q, 0, n - 1);
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
}
#include <iostream>
using namespace std;
const int N = 100001;
int q[N], n;
int sz;//记录当前未进行排序的元素个数
void down(int x)//调整为q[x]为根的堆为大根堆
{
int t = x;
if(x * 2 <= sz && q[x * 2] > q[t]) t = x * 2;
if(x * 2 + 1 <= sz && q[x * 2 + 1] > q[t]) t = x * 2 + 1;//t保存值较大的孩子节点下标
if(t != x)//孩子大于根
{
swap(q[t], q[x]);
down(t);
}
//q[x]大于其孩子节点
}
//堆排序函数
void heap_sort()
{
sz = n;
for(int i = n / 2; i >= 1; i --)//建立初始堆
down(i);
for(int i = 0; i < n-1; i ++)//进行n-1次排序
{
swap(q[1], q[sz]);
sz --;
down(1);
}
}
//堆排序主程序
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> q[i];
heap_sort();
for(int i = 1; i <= n; i ++) cout << q[i] << ' ';
}
#include <iostream>
using namespace std;
const int N = 100001;
int q[N], n;
//归并函数
void merge(int l, int mid, int r)
{
int i = l, j = mid + 1, k = 0;
int w[n];
while(i <= mid && j <= r)
{
if(q[i] <= q[j])
w[k ++] = q[i ++];
else
w[k ++] = q[j ++];
}
while(i <= mid) w[k ++] = q[i ++];
while(j <= r) w[k ++] = q[j ++];
for(int i = l, j = 0; j < k; i ++, j ++)
q[i] = w[j];
}
//归并排序函数
void merge_sort(int l, int r) // 归并排序
{
if(l < r)
{
int mid = (l + r) / 2;
merge_sort(l, mid);
merge_sort(mid + 1, r);
merge(l, mid, r);//将mid左右两个子序列归并在一起
}
}
//归并排序主程序
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
merge_sort(0, n - 1);
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
}
#include <iostream>
using namespace std;
const int N = 1000001;//数据上限
int q[N];
int s[N], w[N];//s为桶，w存储排序后的结果
//桶排序函数
void bucket_sort()
{
for(int i = 0; i < n; i ++) s[q[i]] ++;
for(int i = 1; i < N; i ++)//更新前缀和,注意i要小于数据最大上限N
s[i] += s[i-1];
for(int j = n - 1; j >= 0; j --)
{
int t = s[q[j]];
t --;
w[t] = q[j];
}
for(int i = 0; i < n; i ++) q[i] = w[i];
}
//桶排序主程序
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
bucket_sort();
for(int i = 0; i < n; i ++) cout << q[i] << ' ';
}
