各种排序比较

直接插入排序

void InsertSort(ElemType A[], int n){
	int i, j;
	for(i = 2; i <= n; i++)           //依次将A[2]~A[n]插入到前面已排序序列
		if(A[i].key < A[i-1].key){    //若A[i]的关键码小于其前驱，需将A[i]插入有序表
			A[0] = A[i];         //复制为哨兵，A[0]不存放元素
			for(j = i-1; A[0].key < A[j].key; --j)   //从后往前查找待插入位置
				A[j+1] = A[j];    //向后挪位
			A[j+1] = A[0];     //复制到插入位置
		}
}

冒泡排序

void BubbleSort(int a[], int n){
	int i = n - 1; //初始时，最后位置保持不变
	while(i > 0){
		int pos = 0;   //每趟开始时，无记录交换
		for(int j = 0; j < i; j++)
			if(a[j] > a[j+1]){
				pos = j;   //记录交换位置
				int tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
			}
		i = pos ;  //为下一趟排序作准备
	}
}

快速排序

int Partition(ElemType A[], int low, int high){
	//划分算法（一趟排序过程）
	ElemType pivot = A[low];     //将当前表中第一个元素设为枢轴，对表进行划分
	while(low < high){     //循环跳出条件
		while(low < high && A[high] >= pivot) --high;
		A[low] = A[high];    //将比枢轴值小的元素移到左端
		while(low < high && A[low] <= pivot) ++low;
		A[high] = A[low];    //将比枢轴值大的元素移到右端
	}
	A[low] = pivot;     //枢轴值元素存放到最终到最终位置
	return low;         //返回存放枢轴的最终位置
}

void QuickSort(ElemType A[], int low, int high){
	if(low < high){    //递归跳出的条件
		//Partition()就是划分操作，将表A[low...high]划分为满足上述条件的两个子表
		int pivotpos = Partition(A, low, high);   //划分
		QuickSort(A, low, pivotpos-1);    //依次对两个子表进行递归排序
		QuickSort(A, pivotpos+1, high);
	}
}

简单选择排序（直接选择排序）

(1)

void SelectSort(ElemType A[], int n){
	//对A作简单选择排序，A[]从0开始存放元素
	for(int i=0;i<n-1;i++){
		min=i;
		for(int j=i+1;j<n;j++)
			if(A[j]<A[min]) min=j;
		if(min!=i) swap(A[i],A[min]);
	}
}

(2)

int SelectMinkey(int a[],int n,int i){
	//数组最小值
	int k=i;
	for(int j=i+1;j<n;++j)
		if(a[k]>a[j]) k=j;
	return k;
}
void SelectSort(int a[],int n){
	int key,tmp;
	for(int i=0;i<n;++i){
		key=SelectMinkey(a,n,i); //选择最小的元素
		if(key!=i){
			tmp=a[i];
			a[i]=a[key];
			a[key]=tmp;
		}
	}
}

记忆口诀：

（1）稳定性：心情不稳定，快些选一堆好友来聊天吧

          快指快速排序，些（希）指希尔排序，选指选择排序，堆指堆排序，这4个排序是不稳定的。

（2）时间复杂度：快些以nlog(2,n)的速度归队

          快指快速排序，些（希）指希尔排序，归指归并排序，队（堆）指堆排序，这4个排序的时间复杂度为nlog(2,n)，其他均              为O(n^2)（基数除外，为O(d(n+r))）。

（3）空间复杂度：快归基除外为O(1)

          快是log(2,n)，归是n，基是r。

经过一趟排序，能保证一个元素到达最终位置，有交换类（冒泡排序，快速排序）和选择类（简单排序、堆排序）排序，即插入类排序不可得到最终位置。

排序方法的元素比较次数与原始序列无关的有简单选择排序。

排序方法的排序趟数与原始序列有关的有交换类（冒泡排序，快速排序）排序。