排序算法的C++实现

排序算法比较

1. 冒泡排序2. 选择排序3. 插入排序4. 希尔排序5. 归并排序6. 快速排序代码实现7. 堆排序

稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，则具备稳定性。

原理：在已给的序列中选择最大（最小）的数放到末尾，再从剩余元素中选择最大的，放到未排序的序列末尾，重复这个过程。直到全部排序完成。

选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

原理：对于未排序序列，默认首元素是有序的，从后往前扫描已排序数据，将未排序元素依次插入到已经有序序列的对应位置。

原理：希尔排序是将待排序的序列分成若干待排序的子序列，分别进行插入排序。关键在于间隔序列的设定。希尔排序是第一个突破O(n²)的排序算法。

原理：如果要排序一个数组，先将数组从中间分成前后两部分，对前后两部分分别排序，再将排好序的两部分合并在一起。

归并排序时间复杂度分析：
对n个数组进行归并的时间复杂度是T(n)，分解成两个子数组进行排序的时间复杂的是T(n/2),合并有序数组的操作时间复杂度是O(n)。所以归并排序的时间复杂度就是：

T(n) = 2T(n/2) + n
= 2(2T(n/4) + n/2) + n = 4T(n/4) + 2n
= 4(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n
…
= 2^k * T(n/2^k) + k * n
…
n/2^k 表示分解后的数据规模， k表示把数据规模分解到1时的分解次数，当算法完成，数据规模分解到1，此时n/2^k=1,k=log2n。将k带回原公式，可以计算得到T(n)=Cn+nlog2n，时间复杂度就是O(nlogn)。

原理：在数列中挑选一个数，称为基准(pivot)，将比这个数小的元素放在左半边，其余元素放在右半边。递归地选择基准，并对两边的元素进行排序。

#include
using namespace std;
#include
#include

//冒泡排序基础
void bubbleSort1(vector &q)
{
	for (int i = q.size() - 1; i > 0; i--)
	{ 
		for (int j = 0; j < i; j++)
		{
			if (q[j] > q[j + 1])
			{
				swap(q[j], q[j + 1]);
			}
		}
	}
}
//冒泡排序改进
void bubbleSort2(vector& q)
{
	for (int i = q.size() - 1; i > 0; i--)
	{
		bool flag = false;
		for (int j = 0; j < i; j++)
		{
			if (q[j] > q[j + 1])
			{
				swap(q[j], q[j + 1]);
				flag = true;
			}
		}
		//若内层循环没有进行一次交换说明已经有序，直接break
		if (!flag) break;
	}
}

//选择排序
void selectSort(vector& q)
{
	for (int i = 0; i < q.size(); i++)
	{
		//int max = q[i];
		for (int j = i + 1; j < q.size(); j++)
		{
			if (q[i] > q[j])
			{
				swap(q[i], q[j]);
			}
		}
	}
}

//插入排序
void insertSort(vector& q)
{
	for (int i = 1; i < q.size(); i++)
	{
		int t = q[i], j;
		for (j = i - 1; j >= 0; j--)
		{
			if (q[j] > t)
			{
				q[j + 1] = q[j];
			}
			else
				break;
		}
		q[j + 1] = t;

	}
}

//归并排序
//l,r分别代表区间的左右
void merges_sort(vector& q, int l, int r)
{
	if (l >= r) return; //只有一个元素

	int mid = (l + r) / 2;

	merges_sort(q, l, mid);  //左边做归并
	merges_sort(q, mid + 1, r); //右边做归并

	//归并操作
	static vector w; //辅助数组
	w.clear();

	int i = l, j = mid + 1;//两个指针指向两个序列的起点
	while (i <= mid && j <= r)
	{
		//判断当前两个指针指向的数哪个小
		if (q[i] < q[j])
		{
			w.push_back(q[i++]);
		}
		else
		{
			w.push_back(q[j++]);
		}
	}
	while (i <= mid) w.push_back(q[i++]);
	while (j <= r) w.push_back(q[j++]);

	for (int i = l, j = 0; j < w.size(); i++, j++)
	{
		q[i] = w[j];
	}
}

//快速排序
void quick_sort(vector& q, int l, int r)
{
	if (l >= r) return;
	int i = l - 1, j = r + 1, x = q[l + r >> 1];// x：基准，可以写成随机
	while (i < j)
	{
		do j--; while (q[j] > x); //大于x在右边
		do i++; while (q[i] < x); //小于x在左边
		if (i < j) swap(q[i], q[j]);
		else
			quick_sort(q, l, j), quick_sort(q, j + 1, r);
	}
}


int main()
{
	int n;
	vectorq;
	
	cin >> n;
	for (int i = 0, t; i < n; i++)
	{
		cin >> t;
		q.push_back(t);
	}

	//bubbleSort2(q);
	//selectSort(q);
	
	//insertSort(q);
	//merges_sort(q, 0, q.size() - 1);
	quick_sort(q, 0, q.size() - 1);
	for (auto x : q) cout << x <<' ';
	cout << endl;

	return 0;
}

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。