数据结构之常见的排序算法1

后面2篇文章将介绍几种常见的排序算法：直接插入排序，冒泡排序，快速排序，简单选择排序，堆排序

1，直接插入排序

（1）算法思想

每趟将一个待排序的元素作为关键字，按照起关键字值的大小插入到已经排好的部分序列的适当位置，直到插入完成。

比如说递增顺序排列：

初始序列：（48）36，68，72，12，02

第1趟 （36，48）68，72，12，02

第2趟 （36，48，68）72，12，02

第3趟 （36，48，68，72）12，02

第4趟 （12，36，48，68，72）02

第5趟 （02，12，36，48，68，72）

排序结果： （02，12，36，48，68，72）

（2）代码如下

                    void  InserSort(){
		int a[] = {48,36,68,72,12,2};
		for(int i=1;i<a.length;i++){//a[0]有序，从a[1]开始处理
			int key = a[i];//将待插元素存于key中
			int j =i-1;
			while(j>=0&&a[j]>key){
				a[j+1]=a[j];
				j=j-1;
			}
			a[j+1]=key;//找到插入位置，将key中的元素插入
		}

2，冒泡排序

（1）算法思想

首先第一个记录和第二个记录比，如果第一个大，则而这交换，否则不交换；然后第二个记录和第三个记录比，同上。

最终最大的被交换到最后，一趟冒泡排序完成

上杰宝：

（2）代码如下

 void BubbleSort(int[] a){
		int temp=0;
		int flag;
		for(int j=a.length;j>=1;j--){
			flag=0;
			for(int i=1;i<j;i++){
				if(a[i-1]>a[i]){
					temp=a[i];
					a[i]=a[i-1];
					a[i-1]=temp;
					flag=1;
				}
			}
			if(flag==0){
				break;
			}
		}
		
	}