直接插入排序

每次把一个新数据插入到有序队列中的合适位置里。

假设有一组无序序列 R₀, R₁, … , R_N-1。

(1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。

(2) 然后，我们要依次把 R₀, R₁, … , R_N-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1 。

(3) 接下来描述插入过程。假设这是要将 R_i 插入到前面有序的序列中。由前面所述，我们可知，插入 R_i时，前 i-1 个数肯定已经是有序了。

所以我们需要将 R_i 和R₀ ~ R_i-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。

#include<vector>  
#include<iostream>  

using namespace std;

vector<int> insertionSort(const vector<int>& input) {
	vector<int> result;
	if (input.empty()) {
		return result;
	}
	result = input;

	for (int i = 1; i < result.size(); i++) {
		int temp = result[i];
		int j = i - 1;
		for (; j >= 0 && result[j] > temp; j--) {
			result[j + 1] = result[j];
		}
		result[j + 1] = temp;

	}
	return result;
}

int main()

{
	int a[] = { 2, 4, 8, 7, 5, 3 };
	vector<int> iv(a, a + sizeof(a) / sizeof(int));
	for (int e : iv) {
		cout << e << " ";
	}
	cout << endl;
	vector<int> solve = insertionSort(iv);
	for (int i = 0; i < solve.size(); i++) {
		cout << solve[i] << " ";
	}
	return 0;

}

简单选择排序

每趟从待排序的序列中选出最小的元素，顺序放在已排序的序列末尾。

从待排序序列中，找到关键字最小的元素；
如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

#include<vector>  
#include<iostream>  

using namespace std;

vector<int> selectSort(const vector<int>& input) {
	vector<int> result;
	if (input.empty()) {
		return result;
	}
	result = input;

	for (int i = 0; i < result.size(); i++) {
		int index = i;
		for (int j = i + 1; j < result.size(); j++) {
			if (result[index] > result[j]) {
				index = j;
			}
		}
		if (index == i) {
			continue;
		}
		swap(result[index], result[i]);
		cout << "第" << i + 1 << "次循环:  " ;
		for (int e : result) {
			cout << e << " ";
		}
		cout << endl;
		

	}
	return result;
}

int main()

{
	int a[] = { 2, 4, 8, 7, 5, 3 };
	vector<int> iv(a, a + sizeof(a) / sizeof(int));
	cout << "排序前 ：";
	for (int e : iv) {
		cout << e << " ";
	}
	cout << endl;
	vector<int> solve = selectSort(iv);
	
	return 0;

}

Quick Sort

快速排序的精髓在于partition()，我们把第一个元素作为pivot的培养对象，经过一次partition()后，数组分为两部分，第一部分<=pivot,第二部分>=pivot。
快速排序算法需要两个指针 i、j 分别指向数组的两端， i之前的元素 <=pivot, j之后的元素 >=pivot。两个指针向中间移动，直到遇到一个不符合条件的元素才停止移动。当两个指针都停下时，交换i 、 j 指针指向的元素。
重复这个过程。

while (...) {
    while (a[i] <= pivot) i++;
    while (a[i] >= pivot) j--;
    swap(a[i], a[j]);
}

有了循环就自然要考虑循环的终止条件。可以发现，当i、j两个指针穷尽了各自的区间时循环应该停止，此时两指针处于 交错状态，i指向 >=区域的第一个元素， j指向<=区域的最后一个元素。

此时不应该再进行交换操作了。这时，我们把pivot移动到j处，并且return j这位置，这样，一次partition操作就完成了。
关于i、j两个指针的while循环有数组越界的危险，假设所有元素都<=pivot，那么i会越界；假设所有元素都>=pivot，那么j会越界。因此要加上i<=j这个判断来避免越界（注意要有=，保证i、j会交错）。


int partition (vector<int> a, int first, int last) {
    int i = first;
    int j = last;
    int pivot = a[first];
while (i < j) {
    while (i<=j && a[i] <= pivot) i++;
    while (i<=j && a[i] >= pivot) j--;
    if (i < j) {
        swap (a[i], a[j]);
    }
}
swap (a[first],a[j]);

return j;
}

下面是完整的程序：

#include<vector>  
#include<iostream>  

using namespace std;

int partition(vector<int>& vec, int first, int last) {
	int i = first;
	int j = last;
	int p = first;
	while (i < j) {
		while (i <= j && vec[i] <= vec[p]) i++;
		while (i <= j && vec[j] >= vec[p]) j--;
		if (i < j) {
			swap(vec[i], vec[j]);
		}
		
	}
	swap(vec[p], vec[j]);
	
	return j;


}

void quickSort(vector<int>& vec, int first, int last) {
	if (last > first) {
		int pivot = partition(vec, first, last);
		quickSort (vec, first, pivot - 1);
		quickSort (vec, pivot + 1, last);
	}

	
}

int main()

{
	int a[] = { 3, 4, 1, 9, 7, 2, 5 };
	vector<int> input(a, a + sizeof(a) / sizeof(int));
	cout << "排序前： ";
	for (int e : input) {
		cout << e << " ";
	}
	cout << endl;
	cout << "排序后： ";
	quickSort(input, 0, input.size() - 1);
	for (int e : input) {
		cout << e << " ";
	}
	cout << endl;
	
	return 0;

}

sort

直接插入排序

简单选择排序

Quick Sort

Merge Sort

Heap Sort