排序

插入排序：

1.直接插入排序：

include[HTML_REMOVED]

using namespace std;

const int N = 100010;

int n;
int q[N];

void insertsort(){
for(int i = 1; i <= n; i ++){
int t = q[i], j = i;
while(j && q[j-1] > t){
q[j] = q[j-1];
j –;
}
q[j] = t;
}

}

int main(){
cin >> n;
for(int i = 0; i < n; i ++){
cin >> q[i];
}

insertsort();

for(int i = 0; i < n; i ++){
    cout << q[i] << ' ';
}

}

2.折半插入//基于直接插入进行优化，可以优化比较次数，但是移动次数不变

include[HTML_REMOVED]

using namespace std;

const int N = 100010;

int n;
int q[N];

void binary(){
for(int i = 1; i < n; i++){
if(q[i-1] <= q[i]) continue;// 如果当前元素不小于前一个元素，则继续遍历下一个元素
int t = q[i];
int l = 0, r = i-1;
while(l < r){
int mid = l + r >> 1;
if(q[mid] > t) r = mid;
else l = mid + 1;
}
for(int j = i - 1; j >= r; j –)
q[j+1] = q[j];
q[r] = t;

}

}

int main(){
cin >> n;
for(int i = 0; i < n; i ++){
cin >> q[i];
}

binary();

for(int i = 0; i < n; i ++){
    cout << q[i] << ' ';
}

}

3.希尔排序

void shell(){
for(int d = n / 2; d; d /= 2){
for(int start = 0; start < d; start ++){
for(int i = start + d; i < n; i += d){
int t = q[i], j = i;
while(j > start && q[j-d] > t){
q[j] = q[j-d];
j -= d;
}
q[j] = t;
}
}
}
}

交换排序

1.冒泡排序：
交换次数受初始序列影响，稳定，每次排序都将一个元素放到最终位置上，每次将最小的放大最前面；

void bubble(){
for(int i = 0; i < n - 1; i++){
bool has_swap = false;
for(int j = n - 1; j > i;j –){//由于每次都将一个元素放到最终位置上，所以只用循环n-1次，因为最后一个元素肯定是在最终位置上
if(q[j-1] > q[j]){//由此可以看出，冒牌排序的交换次数是受初始序列影响的，如果初始的大部分有序，则交换的次数更少
swap(q[j-1], q[j]);
}
has_swap = true;
}
if(!has_swap) break;
}
}

2.快速排序

void quick(int l, int r)
{
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[(l + r) / 2];
while(i < j)
{
do i ++; while(q[i] < x);
do j –; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick(l, j);
quick(j + 1, r);
}

简单选择排序：
选择排序比较次数不受影响，时间复杂度都是n方

void select_sort(){
for(int i = 0; i < n - 1; i ){
int k = i;
for(int j = i + 1; j < n - 1; j )
if(q[j] < q[k])
k = j;//k 存储的是最小元素的下标
swap(q[k], q[i]);
}
}

堆排序：

void down(int u){
int t = u;
if(u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
if(u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;
if(u != t)
{
swap(q[u], q[t]);
down(t);
}
}

void head_sort()
{
sz = n;//堆排序需要维护一个sz
for(int i = n / 2; i; i–) down(i);
for(int i = 0; i < n - 1; i++){
swap(q[1], q[sz]);
sz –;
down(1);
}
}

归并排序：
void merge_sort(int l, int r)
{
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
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( i = l, j = 0; i < k; i , j ) q[i] = w[j];
}