程序员必备排序算法

（一）冒泡排序（稳定）
1.基本思想：每一趟从数组的头部开始，两两做比较，根据大小进行位置的交换，直到最后一个数到达末尾，即该数为此趟的最大值，在循环中继续重复此操作，最终得到排序好的序列
2.时间复杂度：
最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，则时间花销为：[ n(n-1) ] / 2；所以最优的情况时间复杂度为：O( n^2 )；

最差的情况也就是开始的时候元素就是逆序的，那么每一次排序都需要交换元素，则时间花销为：[3n(n-1) ] / 2；所以最差的情况时间复杂度为：O( n^2 )；
综上所述：
最优时间复杂度：O(n^2);
最差时间复杂度：O(n^2);
平均时间复杂度：O(n^2);

3.空间复杂度（空间复杂度就是在交换元素时那个临时变量所占的内存空间）：
最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；
最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
平均的空间复杂度为：O(1)；

4.代码实现：

void bubble_sort(int a[], int n)
{
	int t;
	for(int i=0;i<n-1;i++)
		for (int j = 0; j < n-1-i; j++)
			if (a[j] > a[j + 1]) {
				t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
			}
}

（二）选择排序（不稳定）
1.基本思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。
2.时间复杂度：
比较时间：T=(n-1)+(n-2)+…+1=n(n-1)/2
交换时间：全部有序，则交换次数为0；全部逆序，则交换次数为n-1
综上所述：
最优时间复杂度：O(n^2);
最差时间复杂度：O(n^2);
平均时间复杂度：O(n^2);
3.空间复杂度：同冒泡排序
4.代码实现：

void select_sort(int a[], int n)
{
	int i,j,min;
	for (i = 0; i < n - 1; i++)
	{
		min = i;
		for (j = i + 1; j < n; j++)
		{
			if (a[j] < a[min])
				min = j;
		}
		int t;
		t = a[i]; a[i] = a[min]; a[min] = t;
	}
}

（三）插入排序（稳定）
1.基本思想：将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
2.时间复杂度：O(n^2);
3.空间复杂度:O(1);
4.代码实现：

void insert_sort(int a[], int n)
{
	int i,j,key;
	for (i = 1; i < n; i++)
	{
		key = a[i];
		j = i - 1;
		while (j >= 0 && key < a[j])
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = key;
	}
}

（四）快速排序（不稳定）
1.基本思想：在数组中选一个基准数（通常为数组第一个）；
将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边；
对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序
2.时间复杂度：O(nlogn);
3.空间复杂度:O(nlogn);
4.代码实现：

void quick_sort(int a[], int begin, int end)
{
	if (begin < end)
	{
		int i = begin, j = end,temp=a[begin];
		while (i < j)
		{
			while (i<j&&a[j]>temp)
				j--;
			a[i] = a[j];
			while (i < j&&a[i]<=temp)
				i++;
			a[j] = a[i];
		}
		a[i] = temp;
		quick_sort(a, begin, i - 1);
		quick_sort(a, i + 1, end);
	}
}

（五）堆排序（不稳定）
1.基本思想：
堆的定义如下：n个元素的序列{k1,k2，···，kn}当且满足以下关系时，称之为堆

对于一个小顶堆，若在输出堆顶的最小值之后， 使剩余n-1个元素的序列再次筛选形成一个堆，再输出次小值，由此反复进行，便能得到一个有序的序列，这个过程就称之为堆排序。
2.时间复杂度：O(nlogn);
3.空间复杂度:O(1);
4.代码实现：

#include <iostream>
const int N =10;
using namespace std;
void HeapAdjust(int a[],int s,int m)//一次筛选的过程
{
    int rc,j;
    rc=a[s];
    for(j=2*s;j<=m;j=j*2)//通过循环沿较大的孩子结点向下筛选
    {
        if(j<m&&a[j]<a[j+1]) j++;//j为较大的记录的下标
        if(rc>a[j]) break;
        a[s]=a[j];s=j;
    }
    a[s]=rc;//插入
}
void HeapSort(int a[],int n)
{
    int temp,i,j;
    for(i=n/2;i>0;i--)//通过循环初始化顶堆
    {
        HeapAdjust(a,i,n);
    }
    for(i=n;i>0;i--)
    {
        temp=a[1];
        a[1]=a[i];
        a[i]=temp;//将堆顶记录与未排序的最后一个记录交换
        HeapAdjust(a,1,i-1);//重新调整为顶堆
    }
}
void print(int a[],int n)
{
for(int i=1;i<=n;i++)
    cout<<a[i]<<" ";
}
int main()
{
    int n,i;
    cin>>n;
    int a[N];
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    HeapSort(a,n);
    print(a,n);
    return 0;
}

（六）归并排序（稳定）
1.基本思想：分而治之

2.时间复杂度：O(nlogn);
3.空间复杂度:O(n);
4.代码实现：

#include<iostream>
using namespace std;
template<typename T>
void merge(T a[], int first, int mid, int last, T temp[])
{
	int i = first,j=mid+1;
	int m = mid,n=last,k=0;
	while (i <= m && j <= n)
	{
		if (a[i] < a[j])temp[k++] = a[i++];
		else temp[k++] = a[j++];
	}
	while (i <= m)
		temp[k++] = a[i++];
	while(j<=n)
		temp[k++] = a[j++];
	for (i = 0; i < k; i++)
		a[i+first] = temp[i];
}
template<typename T>
void mergesort(T a[], int first, int last, T temp[])
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		mergesort(a, first, mid, temp);
		mergesort(a, mid + 1, last, temp);
		merge(a, first, mid, last, temp);
	}
}
void main()
{
	int a[8] = { 8,3,2,6,7,1,5,4 }, temp[8] = { 0 };
	mergesort(a, 0, 7, temp);
	for (int i = 0; i < 8; i++)
		cout << a[i] << " ";
	cout << endl;
	system("pause");
}