首页 计算机科学 数据结构 排序

# 3. 交换类排序

# 1. 冒泡排序

（相邻比序法）
基本思想：
通过不断比较相邻元素大小，进行交换实现排序。
第一趟排序：
首先将第一个元素和第二个元素比较大小，若为逆序，则交换；然后比较第二个与第三个，一直到第 n-1 和第 n 个，这样就使最大的元素放到了最后一个位置。

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

性能分析：
最好情况正序：O (n)
最坏情况逆序：O (n2)
时间复杂度 O (n2)
空间复杂度 O (1）
稳定

# 2. 快速排序

基本思想
以某个记录为界（支点或枢轴），将待排序列分成两部分，一部分所有记录的关键码小于支点记录的关键码，而另一部分大于支点的关键码。然后对每一部分再划分，直至整个序列有序。

// 完整的快速排序算法
/* 对记录数组 r [low..high] 用快速排序算法进行排序 */
void QKSort(RecordType r[],int low, int high ){
	if(1ow<high){
 		pos=QKPass(r, low, high); /* 调用一趟快速排序，将枢轴元素为界划分两个子表 */
		QKSort(r, low, pos-1); /* 对左部子表快速排序 */
		QKSort(r, pos+1, high); /* 对右部子表快速排序 */
	}
}
// 一趟快速排序算法
/* 对记录数组 r 中的 r [left] 至 r [right] 部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录 */
int QKPass(RecordType r[],int left,int right){
	x= r[left]; /* 选择基准记录 */
	low=left ;
    high=right;
	while ( low<high ){
        /* high 从右到左找小于 x.key 的记录 */
		while (low< high && r[high].key>=x.key )  high--;
		if ( low <high ) {
            r[low]= r[high];
            low++;
        }
        
		/* 找到小于 x.key 的记录，则进行交换 */
		while (low<high && r[low].key<x.key )low++; /* low 从左到右找大于 x.key 的记录 */
	     
        /* 找到大于 x.key 的记录，则交换 */
		if ( low<high ) {
            r[high]= r[low];
            high--; 
        }
	}
	r[low]=x; /* 将基准记录保存到 low=high 的位置 */
	return low; /* 返回基准记录的位置 */
} /* QKPass */
性能分析：
最好情况：O (nlog2n)
最坏情况：O (n2)
时间复杂度 O (nlog2n)
空间复杂度 O (log2n）
不稳定
-->