1.冒泡排序 2.选择排序
3.插入排序 4.希尔排序
5.计数排序
6.归并排序 7.快速排序
Notice：数组大小为n，除计排外数组均定义为a[]，下标为1~n，排序默认均为升序，时间复杂度为平均复杂度
1.冒泡排序
时间复杂度：O(N^2)
（两两元素进行比较，较小的数向前浮动）
void Bubble_sort(int a[],int n)
{
for(int i = 1;i < n; i++){
for(int j = 1; j <= n-i; j++){
if(a[j] > a[j+1]) swap(a[j], a[j+1]);
}
}
}
2.选择排序
时间复杂度：O(N^2)
（不断执行操作：选出未经排序的一系列数的最小值，放到数组最前面）
void Select_sort(int a[], int n)
{
int minx,minn;
for(int i=1;i < n;i++){
//minn存放每一趟排序中的最小数，minx存放下标
minn=a[i]; minx=i;
for(int j=i+1;j<=n;j++){
if(minn > a[j]) minn = a[j],minx=j;
}
if(minx != i)
swap(a[i],a[minx]);
}
}
3.插入排序
时间复杂度：O(N^2)
（拿出第一个乱序数，放到已经排好序的序列的合适位置）
void insert_sort(int a[],int n)
{
int i,j,temp;
for(i = 2; i <= n; i++)
{
//取出要插入的数
temp = a[i];
for(j = i; j > 1 && a[j - 1] > temp; j--)
//寻找合适的插入位置
a[j] = a[j - 1];
//插入数值
a[j] = temp;
}
}
4.希尔排序（对半式增量）
时间复杂度：O(N^1.5)左右
（不断的进行操作：在原数组中按照一定间隔mid从头到尾取出一系列数形成几个新的序列——>对每个新的序列进行排序——>序列合并）
对半式增量：
比如一个长度为8的数组，8/2 = 4，所以第一次就按间隔为4取数，那么形成的新序列的下标就是：<1 5>,<2 6>,<3 7>,<4 8>
第二次间隔为4/2 = 2，则新取出的序列为<1 3 5 7>,<2 4 6 8>
最后一次间隔就是2/2 = 1，直接进行插入排序搞定
void Shell_sort(int a[],int n)
{
int j,i,temp,mid; //增量定义为mid
for(mid = n/2; mid > 0; mid /= 2){
//一个插入排序的过程代码，只不过要注意间隔的存在
for(i = mid; i <= n; i++){
temp = a[i];
for(j = i; j > mid; j -= mid) {
if(a[j - mid] > temp)
a[j] = a[j - mid];
else break;
}
a[j] = temp;
}
}
}
5.计数排序
时间复杂度：O(d(n+r))
(例如a[2] = 1，意思是2这个元素出现了1次）
(适用于数据集中，数据范围较小且比较明确的情况)
#includeusing namespace std; #define MAXN 10000 int cnt[MAXN+1],n,temp;; int main(void) { //输入 memset(cnt,0,sizeof(cnt)); cin >>n; for(int i = 1; i <= n; i++){ cin >>temp; cnt[temp]++; //计数 } //输出 for(int i = 0; i <= MAXN; i++){ if(cnt[i]){ //检测数字i有没有出现过 //出现几次输出几个i for(int j = 1; j <= cnt[i]; j++) cout < 6.归并排序（递归，分治）
时间复杂度：O(nlog2n)(2是底数)
//这里a和b数组没有声明，应该写到外面，a数组是录入数据的数组 void Merge_sort(int l, int r) { //递归到了只有一个元素，直接返回 if(l == r) return; //找到中点，然后两边分别再归并 int mid = (l + r) / 2; Merge_sort(1, mid); Merge_sort(mid + 1, r); //合并序列 int p = 1, q = mid + 1; for(int i = 1; i <= r; i++){ if(q > r || (p <= mid && a[p] <= a[q])) b[i] = a[p++]; else b[i] = a[q++]; } //还原到a数组里 for(int i = 1; i <= r; i++) a[i] = b[i]; }7.快速排序
时间复杂度：O(nlog2n)(2是底数)
(找一个基准，然后将小于这个基准的数放到索引的左边，大于基准的数放到索引右边
不断执行这个操作直到有序，这里基准取的是中间数)
//a数组未定义 void Quick_sort( int L, int R) { int l = L, r = R; //定义基准点 int mid = (L + R) / 2; int x = a[mid]; while(l < r){ //找到两边的逆序点 while(a[l] < x && l < r) l++; while(a[r] > x && l < r) r--; //交换 if(l < r){ swap(a[l], a[r]); l++,r--; } } //左右两边继续快排 if(L < r) Quick_sort(L, r); if(l > R) Quick_sort(l,R); }
