插入排序

插入排序将数组分为未排序和已排序。首先将数组第一个默认为已排序。然后将后面的未排序的元素不断的插入到已排序的区域。
该排序算法的缺点：每次插入时，都必须将元素与前面已排序的元素比较，来确定正确的位置。这样的话，需要大量的赋值操作。时间复杂度：最好O(n)，最差O(n^2).稳定算法。

	/*插入排序 N为数组个数*/
	static void InsertSort(int[] M)
	{
		int pos=0,temp;
		for (int i = 1; i < M.length; i++) 
		{
			pos=i;
			temp=M[i];
			while (pos>0 && M[pos]<M[pos-1])
			{
				M[pos]=M[pos-1];
				M[pos-1]=temp;
				pos--;
			}
		}   
	}

冒泡排序

元素同样分为已排序和未排序两个区域。该排序算法需要将效率特别低，不建议使用。时间复杂度:最好O(n),最差O(n^2),稳定算法。

static void BubbleSort(int[] M)
	{
		int temp; //中间变量
		for (int i = 0; i < M.length-1; i++) 
			for (int j = i+1; j < M.length; j++) 
				if (M[i]>M[j])
					{
						temp=M[j];
						M[j]=M[i];
						M[i]=temp;
					}
	}

选择排序

选择排序每次遍历的时候是选出一个最大值或者最小值的索引，放到数组的指定位置。相比于其他赋值次数较少。时间复杂度:最好O(n)，最差O(n^2).不稳定算法。

static void SelectSort(int[] M)
	{
		int pos,temp;
		for (int i = 0; i < M.length-1; i++) 
		{
			pos=i;
			for (int j = i+1; j < M.length; j++)
				if(M[pos]>M[j])  pos=j;
			temp=M[i];
			M[i]=M[pos];
			M[pos]=temp;
		}
	}

希尔排序

由于开始时，步长的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期步长取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。当步长取到1的时候，则变为了简单的插入排序。

static void ShellSort(int[] M)
	{
		int gap=M.length/2-1;
		int pos,temp;
		while(gap>0)
		{
			for (int i = 0; i < gap+1; i++) {
				for (int j = i+gap; j < M.length; j+=gap) {
					pos=j;
					temp=M[j];
					while (pos>i && M[pos]<M[pos-gap]) {
						M[pos]=M[pos-gap];
						M[pos-1]=temp;
						pos-=gap;
					}
				}
			}
			gap/=2;
		}
	}

算法的稳定性

考察排序算法的时候有一个很重要的特性，就是算法的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定的。