冒排、简单排、插入排、折半插入排、快排、堆排
冒泡排序：（稳定）
void maopao(int *a, int n)
{
for(int i=1; i<=n-1; ++i)
for(int j=1; j<=n-i; ++j)
if(a[j] > a[j+1])
{
int tem = a[j];
a[j] = a[j+1];
a[j+1] = tem;
}
}
简单选择排序：（稳定）
void simple(int *a, int n)
{
for(int i=1; i<=n; ++i)
{
int k = i;
for(int j=i+1; j<=n; ++j)
{
if(a[k] > a[j])
k = j;
}
if(i!=k)
{
int tem = a[k];
a[k] = a[i];
a[i] = tem;
}
}
}
希尔排序：（不稳定）
void shell(int *a, int n)
{
int dk = n;
while(dk > 1)
{
dk = dk/3+1;
for(int i=dk; i<=n; ++i)
{
int key = a[i];
for(int j = i-dk; j>0; j-=dk)
{
if(key < a[j])
{
int tem = a[j];
a[j] = key;
a[j+dk] = tem;
}
}
}
}
}
插入排序：（稳定）
void Insert(int *a, int n)
{
for(int i=2; i<=n; ++i)
{
if(a[i] < a[i-1])
{
int x=a[i], j;
a[i] = a[i-1]; //后移。。。
for(j=i-2; x<a[j]; --j)
a[j+1] = a[j];
a[j+1] = x;
}
}
}
折半插入排序：（稳定）
void zheinsert(int *a, int n)
{
for(int i=2; i<=n; ++i)
{
int x = a[i];
int low=1, high = i-1;
while(low<=high)
{
int m = (low+high)/2;
if(x < a[m])
high = m-1;
else
low = low+1;
}
for(int j=i-1; j>=high+1; --j)
a[j+1] = a[j];
a[high+1] = x;
}
}
快速排序：（不稳定）
int par(int *a, int low, int high)
{
int y = a[low]; //
while(low < high)
{
while(low < high && a[high] >= y) --high;
if(low<high) {a[low] = a[high]; ++low;};
while(low < high && a[low] <= y) ++low;
if(low < high){a[high] = a[low]; --high;};
}
a[low] = y;
return low;
}
void Sort(int *a, int low, int high)
{
if(low < high)
{
int x = par(a, low, high);
Sort(a, low, x-1);
Sort(a, x+1, high);
}
}
堆排序：（不稳定）
void heap(int *a, int s, int m)
{
int rc = a[s];
for(int j=2*s; j<=m; j*=2) //沿数较大的孩子结点向下筛选
{
if(j < m && a[j] < a[j+1]) ++j; //选择较大的儿子结点
if(rc >= a[j]) break; //rc插入到位置s上
a[s] = a[j];
s = j;
}
a[s] = rc;
}
void heapsort(int *a, int n)
{
for(int i=n/2; i>0; --i) //创建大堆
heap(a, i, n);
for(int i=n; i>1; --i)
{
int x = a[1];
a[1] = a[i];
a[i] = x;
heap(a, 1, i-1);
}
}
测试样例：
8
49 38 65 97 76 13 27 49
样例输出：完全代码：
//#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std ;
typedef long long ll;
#define MAXN 105
#define INF 0x3f3f3f3f
#define MALL (Bithrnode *)malloc(sizeof(Bithrnode));
void maopao(int *a, int n)
{
for(int i=1; i<=n-1; ++i)
for(int j=1; j<=n-i; ++j)
if(a[j] > a[j+1])
{
int tem = a[j];
a[j] = a[j+1];
a[j+1] = tem;
}
}
void simple(int *a, int n)
{
for(int i=1; i<=n; ++i)
{
int k = i;
for(int j=i+1; j<=n; ++j)
{
if(a[k] > a[j])
k = j;
}
if(i!=k)
{
int tem = a[k];
a[k] = a[i];
a[i] = tem;
}
}
}
void shell(int *a, int n)
{
int dk = n;
while(dk > 1)
{
dk = dk/3+1;
for(int i=dk; i<=n; ++i)
{
int key = a[i];
for(int j = i-dk; j>0; j-=dk)
{
if(key < a[j])
{
int tem = a[j];
a[j] = key;
a[j+dk] = tem;
}
}
}
}
}
void Insert(int *a, int n)
{
for(int i=2; i<=n; ++i)
{
if(a[i] < a[i-1])
{
int x=a[i], j;
a[i] = a[i-1]; //后移。。。
for(j=i-2; x<a[j]; --j)
a[j+1] = a[j];
a[j+1] = x;
}
}
}
void zheinsert(int *a, int n)
{
for(int i=2; i<=n; ++i)
{
int x = a[i];
int low=1, high = i-1;
while(low<=high)
{
int m = (low+high)/2;
if(x < a[m])
high = m-1;
else
low = low+1;
}
for(int j=i-1; j>=high+1; --j)
a[j+1] = a[j];
a[high+1] = x;
}
}
int par(int *a, int low, int high)
{
int y = a[low]; //
while(low < high)
{
while(low < high && a[high] >= y) --high;
if(low<high) {a[low] = a[high]; ++low;};
while(low < high && a[low] <= y) ++low;
if(low < high){a[high] = a[low]; --high;};
}
a[low] = y;
return low;
}
void Sort(int *a, int low, int high)
{
if(low < high)
{
int x = par(a, low, high);
Sort(a, low, x-1);
Sort(a, x+1, high);
}
}
void heap(int *a, int s, int m)
{
int rc = a[s];
for(int j=2*s; j<=m; j*=2) //沿数较大的孩子结点向下筛选
{
if(j < m && a[j] < a[j+1]) ++j; //选择较大的儿子结点
if(rc >= a[j]) break; //rc插入到位置s上
a[s] = a[j];
s = j;
}
a[s] = rc;
}
void heapsort(int *a, int n)
{
for(int i=n/2; i>0; --i) //创建大堆
heap(a, i, n);
for(int i=n; i>1; --i)
{
int x = a[1];
a[1] = a[i];
a[i] = x;
heap(a, 1, i-1);
}
}
void print(int *a, int n)
{
for(int i=1; i<=n; ++i)
cout << a[i] << ' ';
cout << '\n' << '\n';
}
int main()
{
int A[MAXN];
int B[MAXN];
int C[MAXN];
int D[MAXN];
int E[MAXN];
int F[MAXN];
int G[MAXN];
int n;
cin >> n;
for(int i=1; i<=n; ++i)
{
cin >> A[i];
G[i] = F[i] = E[i] = D[i] = C[i] = B[i] = A[i];
}
cout << '\n';
cout << "--------冒泡排序--------" << '\n';
maopao(A, n);
print(A, n);
cout << "-------简单选择排序-------" << '\n';
simple(B, n);
print(B, n);
cout << "--------希尔排序---------" << '\n';
shell(C, n);
print(C, n);
cout << "--------插入排序-------" << '\n';
Insert(D, n);
print(D, n);
cout << "--------折半插入排序------" << '\n';
zheinsert(E, n);
print(E, n);
cout << "---------快速排序---------" << '\n';
Sort(F, 1, n);
print(F, n);
cout << "----------堆排序----------" << '\n';
heapsort(G, n);
print(G, n);
return 0;
}