初等排序
一.插入排序
在插入排序中，只将比取出的值大的元素向后平移，不相邻的元素不会直接交换，因此排序十分稳定。
输入的数据的顺序会大幅度影响它的复杂度，所以插入排序的优势在于能快速处理相对有序的数据
复杂度
O（N2）
C++实现
#include<iostream>
using namespace std;
void trace(int a[],int n)
{
int i;
for (i = 0;i < n; i++)
{
if (i > 0)
cout << " ";
cout << a[i];
}
cout << endl;
}
void insertionsort(int a[], int n)
{
int i, j, v;
for (i = 1; i < n; i++)
{
v = a[i];
j = i - 1;
while (j>=0&&a[j]>v)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = v;
cout << "第" << i << "次排序:";
trace(a, n);
}
}
int main()
{
int n, i;
int a[100];
cout << "数据个数：";
cin >> n;
cout << "输入" << n << "个数据：";
for (i = 0; i < n; i++)
{
cin >> a[i];
}
insertionsort(a, n);
return 0;
}
二.冒泡排序
冒泡排序仅对数组中的相邻元素进行比较和交换，因此键相同的元素不会改变顺序，所以冒泡排序也是一种稳定的排序方法。交换次数又称反序数或逆序数，可用于体现数列的错乱程度。
复杂度
O(N2)
C++实现
#include<iostream>
using namespace std;
void trace(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
if (i > 0)
cout << " ";
cout << a[i];
}
cout << endl;
}
int bubblesort(int a[], int n)
{
int sw = 0;
for (int i = 0; i<n-1; i++)
{
for (int j = n - 1; j >= i + 1; j--)
{
if (a[j] < a[j - 1])
{
swap(a[j], a[j - 1]);
sw++;
}
}
}
return sw;
}
int main()
{
int a[100], n, sw=0;
cout << "数据个数：";
cin >> n;
cout << "输入" << n << "个数据：";
for (int i = 0; i < n; i++)
cin >> a[i];
sw = bubblesort(a, n);
cout << "交换次数：" << sw<<endl;
trace(a, n);
return 0;
}
