这篇博客包含了数据结构中多种的排序算法：

（1）简单选择：第一趟在A[0]~A[n-1]之间找到最小的，与A[0]进行交换，之后在A[1]~A[n-1]之间进行。。。第i趟在A[i-1]~A[n-1]之间找到最小的，最后需要经过n-1趟，每次确定一个元素最终的位置；

（2）冒泡排序：从头到尾两两比较，每次要么冒一个最大值到最后，要么冒一个最小值到端头，可以使用last来保存最后交换的元素的前一个，如果为0，则说明已经完全有序，无需在进行 下一趟的排序，这种方法最多进行n-1趟，可以确定元素的最终的位置；

（3）双向冒泡排序：一趟排序后最大的元素沉底，最小的元素到最前面，同时避免重复的比较，使用了s和t；

（4）直接插入：认为第一堂的时候第一个元素是有序的，每一次将剩下的n-1个元素按关键字的大小依次插入到有序的队列，每一个元素从后往前找到自己能够插入的位置，最终需要经过n-1趟的排序；

（5）堆排序：构造一个最大堆，采用向下调整的思想，第一次将栈顶A[0]与栈底A[n-1]进行交换，在进行向下调整构造最大堆（排除A[n-1]来构造）。。。如此反复依次将最大的元素排到栈顶交换到栈底

（6）快速排序：以left为基准，i向后找大于等于A[left]的元素，j向前走找小于等于A[left]的元素，如果i<j，则进行交换，最后将A[left]和A[j]交换

（7）两路合并：开始全部看成n个长度为1的序列，之后进行两两的合并，最终得到结果。。。

代码：

#include
    
     using namespace std;void swap(int &a, int &b){	int tmp;	tmp = a;	a = b;	b = tmp;}void EasySelect(int a[], int n){//简单选择排序，利用的是循环n-1次，每次找到最小的那个，与当前第一个置换	int k;	for (int i = 0; i < n - 1; i++)	{		k = i;		for (int j = i + 1; j < n; j++)		{			if (a[k]>a[j])			{				k = j;			}		}		swap(a[i], a[k]);	}}void DirectInsert(int a[], int n){//直接插入排序，当前第一个元素是有序的，之后的元素从后往前查询是否比有序元素的某一个元素小，如果小，则不断的后移元素，然后将最后一个位置插入当前元素	for (int i = 1; i < n; i++)	{		int j = i;//j之前的元素全部是有序的		int tmp = a[j];//保留当前的元素的值		while (j>0 && a[j - 1] > tmp)		{			a[j] = a[j - 1];			j--;		}		a[j] = tmp;	}}void BubbleSort(int a[], int n){//冒泡排序，每次赋值一个last，表明当前一趟排序，最后置换的那一对元素的前一个，如果等于0，只说明没有发现变化，已经是有序的了	int i = n - 1;	int last;	while (i>0)	{		last = 0;		for (int j = 0; j < i; j++)		{			if (a[j]>a[j + 1])			{				swap(a[j], a[j + 1]);				last = j;			}		}		i = last;	}}  void QSort(int a[], int left, int right){//当left
     
      =j的时候停止	if (left < right){		int i = left;		int j = right + 1;		do{			do{ i++; } while (a[i] < a[left]);			do{ j--; } while (a[j]>a[left]);			if (i < j)				swap(a[i], a[j]);		} while (i < j);		swap(a[left], a[j]);		QSort(a, left, j - 1);		QSort(a, j + 1, right);	}}void QuickSort(int a[], int n){//快速排序	QSort(a, 0, n - 1);}void merge(int a[], int i1, int i2, int j1, int j2){	int i = i1;	int j = i2;	int *temp = new int[j2 - i1 + 1];	int k = 0;	while (i <= j1&&j <= j2)	{		if (a[i] < a[j])			temp[k++] = a[i++];		else		{			temp[k++] = a[j++];		}	}	while (i <= j1)		temp[k++] = a[i++];	while (j <= j2)		temp[k++] = a[j++];	for (int i = 0; i < k; i++)	{		a[i1++] = temp[i];	}	delete[]temp;}//两路合并排序void MergeSort(int a[], int n){	int i1, i2, j1, j2;	int size = 1;	while (size < n)	{		i1 = 0;		while (i1 + size < n)		{			i2 = i1 + size;			j1 = i2 - 1;			if (i2 + size - 1>n - 1)			{				j2 = n - 1;			}			else			{				j2 = i2 + size - 1;			}			merge(a, i1, j1, i2, j2);			i1 = j2 + 1;		}		size = size * 2;	}}  //堆排序，利用的是最大堆void adjustdown(int a[], int r, int j){//表示a[r]之后的元素都已经满足最大堆，	int child = 2 * r + 1;	int tmp = a[r];	while (child <= j)	{		if (child < j&&a[child] < a[child + 1])			child++;		if (tmp >= a[child])			break;		a[(child - 1) / 2] = a[child];		child = child * 2 + 1;	}	a[(child - 1) / 2] = tmp;}void HeapSort(int a[], int n){	for (int i = (n - 2) / 2; i > -1; i--)	{		adjustdown(a, i, n - 1);//首先构造堆	}	for (int i = n - 1; i > 0; i--)	{//构造出来的最大堆，然后把栈顶的元素与栈底元素交换，之后在进行堆排序		swap(a[0], a[i]);		adjustdown(a, 0, i - 1);	}}void DoubleBubbleSort(int a[], int n){	int left = 0;	int right = n - 1;	int s, t;	while (left < right)	{		s = left;		for (int i = left; i < right; i++)		{			if (a[i]>a[i + 1])			{				swap(a[i], a[i + 1]);				s = i;//循环结束后s后的元素已经有序			}		}		right = s;		t = right;		for (int i = right; i > left; i--)		{			if (a[i] < a[i - 1])			{				swap(a[i], a[i - 1]);				t = i;//t之前的元素已经有序			}		}		left = t;	}}int main(){	int a[7] = { 48, 36, 68, 72, 12, 48, 02 };	//HeapSort(a, 7);	//BubbleSort(a, 7);	//EasySelect(a, 7);	//DirectInsert(a, 7);	//QuickSort(a, 7);	DoubleBubbleSort(a, 7);	for (int i = 0; i < 7; i++)		cout << a[i] << " ";	cout << endl;	return 0;}