浅谈排序算法（冒泡，插入，归并）

对于数据的排序，有多种方法，对应这不同的时间复杂度（效率不同）。

一、冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）是一种简单的排序算法。

算法思路：

1. 从第一对相邻数据开始到最后一组相邻数据比较，两两依次比较，最后一组数据结束时，数组 下标n对应的数即为最大数。

2.重复上述操作，直至下标为n-1 （下标为n的数已经是最大的，不需要重复操作）

3.最后重复操作直至不需要再比较任意一对数（即总共进行n次）

时间复杂度 $O(x^{2})$

图示（省略比较不交换的操作）：

冒泡排序代码：

#include<cstdio>
#include<iostream>
using namespace std;
int a[1001];
int n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	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]); 
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}

二、插入排序（Insert sort）

插入排序很好理解，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法思路：

1.默认第一个元素为已排序序列

2.取出下一个元素，在已排序序列中从后向前扫描

3.如果该元素（已排序）大于新元素，将该元素移到下一位置（前移一位）

4.重复操作3，直到找到已排序的元素小于或者等于新元素的位置，并将新元素插入到该位置后

5.重复2~4操作，直至对最后一个元素插入操作结束。

时间复杂度： $O(x^{2})$

关键操作：步骤3 从后向前扫描以上图④为例

代码实现插入排序：

#include<cstdio>
#include<iostream>
using namespace std;
int a[1001];
int n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j>=1;j--)
			if(a[j]<a[j-1]) swap(a[j],a[j-1]);
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}

三、归并排序（Merge sort）

归并排序（Merge sort）是一种采用分治法的排序方法，将已有的子序列合并，合并成一个有

序的新序列。时间复杂度： $O(nlogn)$

算法思路（分支法）：

1.分：将原序列分成相应的子序列（二分方法）。时间复杂度为 $O(logn )$ ，相比上述两种排序方法的效率大大提高，因此更适合数据范围更大的情况。

// “分”的伪代码
void merge(int l,int r)
{
    int mid=l+(r-l)/2; // 二分
    if(l<r)
    {
	  	merge(l,mid); 
	    merge(mid+1,r);
	    merge_sort(l,mid,r); // 并
	}
}

2.并：将分的子序列合并成一个新的有序数列（合并的过程是线性的，时间复杂度为 $O(n)$ ）

“并”的过程思路很简单，但与递归结合代码实现较难

将 [ l , r ] 与 [ mid+1 , r ] 的序列合并，采用线性方法，如图所示：

从两个序列的第一个数一次比较，取出较小的数放入新的有序数组，然后再将新数组赋值到原来的数组中。

void merge_sort(int l,int mid,int r) // 将[l,mid]与[mid+1,r]的序列合并
{
    int i=l,j=mid+1,k=l;
    while(i!=mid+1 && j!=r+1) // 采用线性的方法
    {
        if(a[i]>a[j]) 
        {
            b[k++]=a[j];
            j++;
        }
        else 
        {   
            b[k++]=a[i];
            i++;
        }
    }
	while(i!=mid+1) b[k++]=a[i++]; // 将剩下未被完全取出的序列依次取出放入新数组
    while(j!=r+1) b[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=b[i];
}