排序算法

归并排序.cpp

//-----------------------------------------------------------------------------
// 作    者：adoredee
// 创建时间：2019.04.24
// 描    述：归并排序
//-----------------------------------------------------------------------------

#include <iostream>
#include <vector>
using namespace std;

//函数声明
void merge_sort(vector<int> &arr, int start, int end);
void merge(vector<int> &arr, int start, int mid, int end);
void output_array(vector<int> &arr);   //输出

// 递归
void merge_sort(vector<int> &arr, int start, int end) 
{
	if (start < end) 
	{
		int mid = (start + end) / 2;
		merge_sort(arr, start, mid);
		merge_sort(arr, mid + 1, end);
		merge(arr, start, mid, end);
	}
}

void merge(vector<int> &arr, int start, int mid, int end) 
{
	vector<int> tmp;  // 创建零食数组
	int i = start, j = mid + 1;
	while (i <= mid && j <= end ) {
		// 如果左边的元素小于右边
		if (arr[i] <= arr[j])
			tmp.push_back(arr[i++]);
		// 如果右边的元素小于左边
		else
			tmp.push_back(arr[j++]);
	}

	// 下面这几句是查漏补缺
	// 可能右边的子序列已经排序好了，左边的子序列可能有剩余元素
	while (i <= mid)
		tmp.push_back(arr[i++]);
	// 可能左边的子序列已经排序好了，右边的子序列可能有剩余元素
	while (j <= end)
		tmp.push_back(arr[j++]);

	// 将排序后的元素，全部都整合到数组arr，非常关键
	for (int i = 0; i < tmp.size(); i++)
		arr[start + i] = tmp[i];
}

void output_array(vector<int> &arr) 
{
	for (auto i : arr)
		cout << i << " ";
	cout << endl;
}

int main() 
{
	vector<int> data = { 2, 4, 6, 0, 9, 8, 5, 10};
	merge_sort(data, 0, (int)data.size() - 1);
	output_array(data);

	return 0;
}

插入排序.cpp

//-----------------------------------------------------------------------------
// 作    者：adoredee
// 创建时间：2019.04.23
// 描    述：插入排序
//-----------------------------------------------------------------------------
/*
    数组前面是排序好的，乱序的数依次向有序的数比较

*/
#include <iostream>
#include <vector>

using namespace std;

void InsertSort(vector<int>& arr)
{
	// 默认第一个元素是有序的
	for (int i = 1; i < arr.size(); i++)
	{
		int key = arr[i];
		int j = i - 1;
		// 从小到大排序
		/*
		    从后向前逐个比较已经排序过数组，如果比它小，则把后者用前者代替，
			从而找到合适的位置插入key值
		*/
		while (j >= 0 && key < arr[j])
		{
			arr[j + 1] = arr[j];   // 把前一位的值赋值给后一位
			j--;  // 向前移动
		}
		arr[j + 1] = key;   // 找到合适的位置了，把key值放到j索引的后面
	}
}

int main()
{
	vector<int> arr = { 5, 3, 7, 6, 6, 8, 10, 1 };
	InsertSort(arr);

	// for (int i = 0; i < arr.size(); i++)
	//     cout << arr[i] << " ";
	for(auto i : arr)    // i为容器里的元素，不为索引
		cout << i << " ";

	return 0;
}