数据结构：排序

排序一般分为：插入排序，选择排序，交换排序，归并排序和分配排序。

 

1.插入排序，基本思想：每次将一个待排序记录按其关键字大小插入到前面已排好序的子文件中的适当位置，直到全部记录插入为止。时间复杂度：O(n^2), 稳定的。

  算法描述：

 

//递增
void insertSort(SeqList R){
 int i,j;
 for(i=2; i<=n; i++){
  if(R[i].key < R[i-1].key){
   R[0] = R[i];
   j = i-1;
   do{
     R[j+1] = R[j];
     j--;
   }while(R[0]<R[j]);
  }// end if
 }//end for
}

 

 

  直接插入排序：假设待排序记录存放在数组R[1..N]中，初始时，R[1]自成一个有序区，无序区为R[2..N]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]，生成含有n个记录的有序区。

  一趟直接插入排序：

      简单方法：首先在当前有序区R[1..i-1]找出R[i]正确插入位置k，然后将R[k,i-1]均后移一位，腾出k位置插入R[i]。

      改进的方法：将待插入的R[i]从右向左依次与有序区R[j]比较，若R[j] > R[i]，则R[j]右移一位，若R[j]<=R[i]，查找结束，j+1即为R[i]插入位置。

 

2.希尔排序，也属于插入排序一种。基本思想：先取一个小于n的整数d1，作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组进行直接插入排序；然后，取第二个增量d2<d1重复上述分组和排序，直到所取的增量dt=1，实质是一种分组插入排序。不稳定。

//d 为增量,整体按递增排序 
void shellPass(int d, int n){
	int i,j;
	
	for(i=d+1; i<=n; i++){
		if(R[i] < R[i-d]){
			R[0] = R[i];
			j = i - d;
			do{
				R[j+d] = R[j];
				j = j - d;
			}while(j>0 && R[0] < R[j]);
			R[j+d] = R[0];
		}//end if
	}//end for
}

  

3.冒泡排序

void bubbleSort(int n){
	int i,j,t;
	int changed;
	
	for(i=1; i<n; i++){
		changed = 0;
		for(j=n-1; j>=i; j--){
			if(R[j+1] < R[j]){
				R[0] = R[j+1];
				R[j+1] = R[j];
				R[j] = R[0];
				changed = 1;
			}
		}
		if(!changed) return;
	}
} 

 

4.快速排序，划分交换排序，采用分治的策略。将问题分解为若干个规模更小但结构与原问题相似的子问题，递归地解这些子问题，然后把子问题的解组合为原问题的解。

基本思想：（1）分解，R[low..high]任选一个记录为基准Pivot，划分为左右子区间，并使左边子区间所有记录小于Pivot，右边区间大于等于Pivot。（2）求解。通过递归调用快速排序对左右子区间快速排序。（3）组合。快速排序无需

int partition(int low, int high){
	int pivot = R[low];
	while(low<high){
		while(low<high && R[high]>=pivot){
			high--;
		}
		if(low<high){
			R[low++] = R[high];
		}
		while(low<high && R[low]<=pivot){
			low++;
		}
		if(low<high){
			R[high--] = R[low];
		}//end while 
	}
	R[low] = pivot;
	return low;
}

void quickSort(int low,int high){
	int pivotPos;
	if(low < high){
		pivotPos = partition(low,high);
		quickSort(low,pivotPos-1);
		quickSort(pivotPos+1,high);
	}
}

 

5.选择排序，基本思想：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的子文件最后，直到全部记录排序完毕。常用有直接选择排序和堆排序。

  直接选择排序：n个记录的文件的直接选择排序可以经过n-1趟直接选择排序得到有序结果。

 

void selectSort(int n){
	int i,j,k;
	for(i=1; i<=n; i++){
		k=i;
		for(j=i+1; j<=n; j++){
			if(R[j] <R[k]){
				k=j;	
			}
			if(k!=i){
				R[0] = R[i];
				R[i] = R[k];
				R[k] = R[0];
			}
		}
	}
}

 

堆排序：