排序算法

　排序算法稳定性的简单形式化定义为：如果A_i = A_j，排序前A_i在A_j之前，排序后A_i还在A_j之前，则称这种排序算法是稳定的。

通俗地讲就是保证排序前后两个相等的数的相对顺序不变。

　　对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。

需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

　　例如，对于冒泡排序，原本是稳定的排序算法，如果将记录交换的条件改成A[i] >= A[i + 1]，则两个相等的记录就会交换位置，从而变成不稳定的排序算法。

快速排序：以一个数为基数，从右向左寻找比它小的数放在左边

　　　　　　　　　　　　　从左向右寻找比它大的数放在右边

// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)
#include<iostream> 
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[100];

void quick(int l,int r)
{
    int i,j,temp;
    i=l,j=r;
    if(l>r)//若左大于右结束
        return ;
    temp=a[l];//基数
    while(i!=j)
    {
        while(a[j]>=temp&&i<j)//从右寻找第一个比基数小的数
            j--;
        while(a[i]<=temp&&i<j)//从左寻找第一个比基数大的数
            i++;
        if(i<j)//交换
        {
            int t;
            t=a[i]; a[i]=a[j]; a[j]=t;
        }
    }
    a[l]=a[i];
    a[i]=temp;//将基数放到应到的位置
    quick(l,i-1);
    quick(i+1,r);
}

int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
            cin>>a[i];
        quick(1,n);
        for(int i=1;i<=n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

冒泡排序：共查找n-1趟每次循环n-i，每次把最大的元素放在最后

#include<iostream> 
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[100],n;

void bubblesort()//核心代码
{
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[j]<a[i])
				swap(a[i],a[j]);
		}
	}
}

int main()
{
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
			cin>>a[i];
		bubblesort();
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

选择排序：首先从n个数中选出1个最小数，并与第一个数交换，再从剩下的n-1个数中选择最小的数，与第二个数交换

以此类推·

void simpleselctsort()
{
    int i,j,k;
    for(int i=1;i<n;i++)//每次选择一个最小元素的位置和第i个元素交换 
    {
        k=i;//记下当前最小元素的位置 
        for(int j=i+1;j<=n;j++)//向右查找更小元素 
        {
            if(a[j]<a[k])
                k=j;//更新最小元素位置 
        }
        if(k!=i)//如果有更小的数，交换 
        {
        //    a[0]=a[i];a[i]=a[k];a[k]=a[0];
            swap(a[i],a[k]);
        }
    }
}

shell插入排序：对n个数排序，首先取一个整数d（d=n/2）将这n个数分为d组，所有位置相差为d的分为一组，在每组中使用直接插入排序实现组内排序，然后缩小d的值，重复进行分组和组内排序，直到d=1结束。

　　

void shellinsertsort()
{
    int i,j,d;
    d=n/2;
    while(d>=1)
    {
        for(i=d+1;i<=n;i++)//从d+1个元素开始将所有元素有序的插入分组中 
        {
            a[0]=a[i];//用a[0]保存第i个元素 
            j=i-d;//向前找距离为d的元素比较大小进行组内排序 
            while(j>0&&a[j]>a[0])
            {
                a[j+d]=a[j];//排序码后移 
                j=j-d;//继续向前查找 
            }
            a[j+d]=a[0];//将第i个元素插入 
        }
        d=d/2;//缩小d的范围 
    }
}

二分插入排序：在找第i个位置的插入顺序时，前i-1个记录已排序，与中间位置比较，确定查找的区间在前半个还是后半个

void binarysort()
{
    int left,right,mid;
    for(int i=2;i<=n;i++)//从第二个元素开始插入所有元素 
    {
        a[0]=a[i];//用a[0]存放待插入的元素 
        left=1;right=i-1;//确定左右边界 
        while(left<=right)//左<右取中间值比较 分开左右区间 
        {
            mid=(left+right)/2;
            if(a[mid]>a[i])
                right=mid-1;
            else
                left=mid+1;
        }
        for(int j=i-1;j>=left;j--)//将大于该数的值向后移一个位置 
        {
            a[j+1]=a[j];    
        }    
        a[left]=a[0];//插入位置为left 
    }
}

直接插入排序：从第二个数开始如果该数比前面的数小就将大于它的数后移

void insertsort() 
{
    int j;
    for(int i=2;i<=n;i++)
    {
        j=i-1;//看前i-1个数 
        a[0]=a[i];//先存到a[0] 
        while(a[j]>a[0])
        {
            a[j+1]=a[j];//将大于a[0]的数后移 
            j--;//继续往前找 
        }
        a[j+1]=a[0];//存放a[0]，前面的数均比它 
    }
}