C语言实现八种排序（2）

2. 交换排序

 

2.1 冒泡排序

什么是冒泡排序？

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

代码实现如下:

void BubbleSort(int *a,int length){
	int i,j;
	int flag=1; //判断是否进行循环
	for(i=0;i<length-1&&flag==1;i++){
		for(j=0;j<length-1-i;j++){
			flag=0;
			if(a[j]>a[j+1]){
				flag=1;
				int temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}
}

但由于冒泡排序的时间复杂度过高，所有引申出了一种新型的排序 -- 快速排序（QuickSort）。

这个名字就能彰显出其速率之快.

那这种排序是如何实现的？

代码如下:

//快速排序 
int Partition(int*a,int left,int right){
	int temp=a[left];//left下标作为基准数
	while(left<right){
		while(left<right&&a[right]>temp){
			right--;
		}
		if(left<right){
			a[left]=a[right];
		}
		while(left<right&&a[left]<temp){
			left++;
		}
		if(left<right){
			a[right]=a[left];
		}
	} 
	a[right]=temp;
	return right;
}
void QuickSort(int*a,int left,int right){
	if(left<right){
		int pivot=Partition(a,left,right);
		QuickSort(a,left,pivot-1);
		QuickSort(a,pivot+1,right);
	}
}

我们首先选择一个作为基准数，然后遍历整个数组（除了基准数），将小于基准数的放在它的左边，大于基准数的放在它的右边。

然后将基准数的左边和右边右看成一个数组，重复上述操作，直到每个数组只剩一个元素。

---

让我再水一期