交换排序

冒泡排序

最坏情况下即元素全部逆序时间复杂度$O(n^2)$
平均时间复杂度也为$O(n^2)$
冒泡排序是一种稳定的排序方法

bool BubbleSort(SqList &L,int n){//n为表长
	for(int i=1;i<n;i++){
		int s=0;
		for(int j=n;j>i;j--){
			if(L.data[j-1]>L.data[j]) swap(L.data[j-1],L.data[j]);//若后面的小于前面的 交换位置 然后再跟前面的比较 
			s=1;
		}
		if(s==0) return 1;
	}
}

Swap()函数功能为交换这两个数的位置

快速排序

int Partition(SqList &L,int low,int high){
	int pivot=L.data[low];//第一个元素作为枢轴
	while(low<high){
		while(low<high&&L.data[high]>=pivot) high--;
		L.data[low]=L.data[high];//从序列的末端向前遍历 
		//把比枢轴小的第一个遍历到的元素放在low指向的位置
		while(low<high&&L.data[low]<=pivot) low++;
		L.data[high]=L.data[low];//从枢轴后的第一个元素开始向后遍历 
		//把第一个比枢轴大的元素放在刚刚high指向的位置
	}
	L.data[low]=pivot;
	return low;
}
void QuickSort(SqList &L,int low,int high){//low=1 high=n表长
	if(low<high){
		int pivotpos=Partition(L,low,high);
		QuickSort(L,low,pivotpos-1);
		QuickSort(L,pivotpos+1,high);
	}
}

eg:
Circle1:元素初始序列98 36 -9 0 47 23 1 8 10 7 以98为枢轴从序列末端选择比98小的元素 high指向7 7占据第一个位置
从枢轴后向后遍历选择比枢轴大的元素 low指到了最后一个元素也没有找到 low=high跳出循环枢轴98占据最后一个位置
Circle2:元素第二次序列变更为7 36 -9 0 47 23 1 8 10| 98原枢纽98左侧的序列以7位枢轴从序列末端选择比7小的元素 high指向1 1占据第一个位置
从枢轴后向后遍历选择比枢轴大的元素 low指向36 36换到第二次序列中1的位置 low<high继续循环
high继续向前遍历寻找比枢轴小的元素 high指向0 0换到第二次序列中36的位置
low继续向前遍历寻找比枢轴大的元素还未遍历到low=high 跳出循环枢轴7占据第二次序列中0的位置
Circle3:元素第三次序列变更为1 0 -9| 7| 47 23 36 8 10| 98 原枢轴7左侧的序列1 0 -9
以1为枢轴从序列末端寻找比1小的元素 high指向-9 -9占据第一个位置从枢轴向后遍历寻找比枢轴大的元素还未找到 low=high 跳出循环枢轴1占据第三次序列 -9的位置左侧序列变更为-9 0 |1
原枢轴7右侧的序列47 23 36 8 10以47为枢轴从末端寻找比47小的元素 high指向10 10占据第一个位置从枢轴向后遍历寻找比枢轴47大的元素还未找到 low=high 跳出循环 47占据第三次序列中10的位置右侧序列变更为10 23 36 8 |47
Circle4:元素第四次序列变更为-9 0| 1| 7| 10 23 36 8| 47| 98
左侧序列-9 0 -9为枢轴从序列末端寻找比枢轴-9小的元素还未找到low=high 跳出循环左侧序列依旧为-9| 0
右侧序列10 23 36 8 10为枢轴从序列末端寻找比10小的元素 high指向8 8占据第一个位置从枢轴向后遍历寻找比10大的元素 low指向23 23 占据第四次序列中8的位置 high继续向前遍历寻找比枢轴10小的元素还未找到 low=high 跳出循环枢轴10占据第四次序列中23的位置
序列变更为8 |10| 36 23
Circle5:元素第五次序列变更为-9| 0| 1| 7| 8| 10| 36 23| 47| 98 其中36 23以36为枢轴从序列末端选择比枢轴36小的元素 high指向23 23占据第一个位置从枢轴向后遍历寻找比36大的元素还未找到 low=high跳出循环 36占据第五次序列中23的位置
元素最终序列变更为-9 0 1 7 8 10 23 36 47 98 快排结束

时间复杂度：最好情况下(元素序列越无序) 算法效率越高 $O(nlogn)$ 即每一次Partition函数所得的枢轴都平分序列
最坏情况下(元素序列越有序) 算法效率越低 $O(n^2)$ 即每一次Partition函数所得的枢轴都是元素序列的两端点