排序算法

附上常用排序算法的一览表

冒泡排序

依次遍历序列每个元素，进行两两比大小，如果顺序错误则交换，遍历完所有即为有序序列。
算法步骤：

• 比较相邻元素大小，错误则交换
• 对每一组元素做上述工作，从开头到尾进行处理
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

void bubble_sort(std::vector<int>& vec) {
	int length = vec.size();
	for (int i = 0; i < length - 1;i++) {
		for (int j = 0; j < length - 1 - i;j++) {
			if (vec[j] > vec[j+1]) {
				int temp = vec[j];
				vec[j] = vec[j + 1];
				vec[j + 1] = temp;
			}
		}
	}
}

选择排序

每次选择一个最小（最大）的元素排列到最前
算法步骤：

• 在未排序的序列中找到最大（小）元素，放到序列首位。
• 在剩余未排序的元素中找到最大（小）元素，放到已排列序列的末尾。

void select_sort(std::vector<int>& vec) {
	int length = vec.size();
	int minIndex = 0;
	for (int i = 0; i < length - 1;i++) {
		minIndex = i;
		for (int j = i+1; j < length - 1;j++) {
			if (vec[j]< vec[minIndex]) {
				minIndex = j;
			}
		}
		int temp = vec[minIndex];
		vec[minIndex] = vec[i];
		vec[i] = temp;
	}
}

插入排序

取无序序列中的第一个元素选择合适的位置插入到有序序列中。
算法步骤：

• 将第一个元素视为有序序列，后面的元素为无序序列。
• 遍历有序序列，将有序序列元素依次后移，直到为无序序列的首位元素找到符合规则的位置，最后放入无序序列的元素至有序序列。
• 重复上步过程。

void insert_sort(std::vector<int>& vec) {
	int length = vec.size();
	int preIndex,current;
	for (int i = 1; i < length;i++) {
		preIndex = i - 1;
		current = vec[i];
		//找到插入位置
		while (preIndex>=0 && current<vec[preIndex]) {
			vec[preIndex+1] = vec[preIndex];
			preIndex--;
		}
		//插入元素
		vec[preIndex+1] = current;
	}
}

希尔排序

可以看作是插入排序的高效改进版本。在插入排序中，我们是依次（一个一个）交换移动数据的，如果数据量级大，就是$n^2$的复杂度。因此，在希尔排序中考虑增加每次元素交换的步长，从而降低大量数据排序时的复杂度。

算法步骤：

• 先计算步长
• 使用插入排序对间隔步长的元素进行排序，并缩减步长。
• 重复上步过程

void shell_sort(std::vector<int>& vec) {
	int length = vec.size();
	int s = 1;
	while (s<length/3) {
		s = s * 3 + 1;
	}

	while (s>=1) {
		for (int i = s; i < length;i++) {
			for (int j = i; j >= s && vec[j]<vec[j-s];j-=s) {
				std::swap(vec[j],vec[j-s]);
			}
		}
		s = s / 3;
	}
}

归并排序

通过多次归并两个有序序列，对原序列完成排序。

算法步骤：

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
• 重复步骤 3 直到某一指针达到序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾。

归并操作

考虑两个有序序列，分别从两个序列头部开始，比较指向的元素大小，将符合要求的放入中间缓存序列（长度为两序列之和）。从而得到一个有序的序列

void merge(std::vector<int>& vec, int front,int mid, int back) {
	int length = back-front;
	std::vector<int> tempVec(length,0);
	int left = front;
	int right = mid;
	int i = 0;

	while (left<mid && right<back) {
		if (vec[left]<vec[right]) {
			tempVec[i] = vec[left];
			left++;
		}
		else {
			tempVec[i] = vec[right];
			right++;
		}
		i++;
	}

	while (left<mid) {
		tempVec[i++] = vec[left++];
	}

	while (right<back) {
		tempVec[i++] = vec[right++];
	}

	for (int index = 0; index < length;index++) {
		vec[front+index] = tempVec[index];
	}
}

归并排序

自顶向下的递归版本

这里先完成的是递归版本的归并排序。考虑自顶向下的方法，有了每一步的操作，就可以进行递归了。

void merge_sort(std::vector<int>& vec ,int front,int back) {
	if (front>=back-1) //考虑清楚区间
	{
		return;
	}
	int mid = (front + back) / 2;
	merge_sort(vec,front,mid);
	merge_sort(vec,mid,back);
	merge(vec,front,mid,back);
}

自底向上的迭代版本

快速排序

堆排序

计数排序

桶排序

基数排序