算法-排序

排序算法总结

一、快速排序

1.1 思想（递归）

函数merge(vector& array, int beginIndex, int endIndex)的功能是将数组array从beginIndex到endIndex按从小到大排列

第一步：找一个标志数据（一般为array[beginIndex]）

第二步：对array重新排列，将array中小于标志数据的放标志数据左边，大于的放右边，假设排列后标志数据的下标为flagIndex（重点）

? 初始三个索引flagIndex = beginIndex、leftIndex = beginIndex+1、rightIndex = endIndex

? 扫描除了标志数据的其他所有数据（leftIndex ~rightIndex ）（while（leftIndex <= rightIndex））

? 如果flagIndex 在（leftIndex ~rightIndex）的左侧，则判断rightIndex的值是否大于flagIndex 的值，如果非：将rightIndex的值放在flagIndex 的位置，flagIndex 更新为rightIndex；rightIndex–；

? 如果flagIndex 在（leftIndex ~rightIndex）的右侧，则判断leftIndex的值是否小于flagIndex 的值，如果非：将leftIndex的值放在flagIndex 的位置，flagIndex 更新为leftIndex；leftIndex++；

第三步：f(array,0,array.size - 1) = f(array,0,flagIndex-1) + f(array,flagIndex+1,array.size-1)

1.2 代码

void merge(vector<int>& array, int beginIndex, int endIndex) {
	//1 判断结束条件
	if (beginIndex > endIndex) return;
	if (beginIndex == endIndex) return;
	//2 重新排序
	else {
		int b = beginIndex + 1, e = endIndex, flagIndex = beginIndex,flag = array[beginIndex];
		while (b <= e) {
			if (flagIndex < b) {
				if (array[e] < flag) {
					array[flagIndex] = array[e];
					flagIndex = e;
				}
				e--;
			}
			else {
				if (array[b] > flag) {
					array[flagIndex] = array[b];
					flagIndex = b;
				}
				b++;
			}
		}
		array[flagIndex] = flag;
		//3 递归求解
		merge(array, beginIndex, flagIndex - 1);
		merge(array, flagIndex + 1, endIndex);
	}
}