排序算法汇总

1.冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

void BubbleSort(int a[])
{
	for (int i = 0; i<10; i++)
	{
		for (int j = 9; j > i; j--)
			if (a[j] < a[j - 1])
				swap(a[j], a[j - 1]);
	}
}

 2.选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

void SelectSort(int a[]) 
{
	int min,i,j;
	for (i = 0; i < 9; i++)
	{
		min = i;
		for (j = i + 1; j < 10; j++)
			if (a[min] > a[j])
			{
				min = j;
			}
		if (min != i)
			swap(a[min], a[i]);
	}
}

3.插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

void InsertSort(int a[])
{
	int i = 0, j = 0,t;
	for  (i = 1; i <10; i++)
	{
		if (a[i-1]>a[i])
		{
			t = a[i];
			for (j = i-1;j>=0&&a[j]>t;j--)
				a[j+1] = a[j];
			a[j+1] = t;
		}
	}	
}

4.希尔排序 

是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。

void ShellSort(int a[]) 
{
	int i, j, t;
	for (int dk= 5; dk >=1; dk=dk/2)
	{
		for (i = dk; i <10; i++)
		{
			if (a[i] < a[i - dk])
			{
				t= a[i];
				for (j = i - dk; j >= 0 && t < a[j]; j=j-dk)
					a[j+dk] = a[j];
					a[j+dk] =t;
			}
		}
	}
}

5. 归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 

int n=10;
int *b = (int *)malloc((n + 1) * sizeof(int));//辅助数组B
void Merge(int a[],int low,int mid,int high)
{//表的两段a[low...high]和a[mid+1...high]各自有序，将他们合并成一个有序表
	int i, j, k;
	for (int k=low; k<=high;k++)
		b[k] = a[k];
	for (i = low,j = mid + 1, k = i; i <= mid && j <=high; k++)
	{
		if (b[i] < b[j])
			a[k] = b[i++];
		else a[k] = b[j++];
	}
	while (i<=mid)		a[k++] = b[i++];//若第一个表未检测完，复制
	while (j<=high)		a[k++] = b[j++];//若第二个表未检测完，复制
}

void MergeSort(int a[],int low,int high)
{
	if (low < high)
	{
		int mid = (low + high) / 2;
		MergeSort(a, low, mid);
		MergeSort(a, mid + 1, high);
		Merge(a, low,mid, high);
	}
}

 6.快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

int Partition(int a[], int low, int high)
{
	int pivot = a[low];
	while (low < high)
	{
		while (low < high&&a[high] >= pivot) high--;
		a[low] = a[high];//将比枢轴小的移动到左端
		while (low < high&&a[low] <= pivot) low++;
		a[high] = a[low];//将比枢轴大的移动到右端
	}
	a[low] = pivot;//枢轴元素存放到最终位置
	return low;//返回存放枢轴的最终位置
}
void QuickSort(int a[], int low, int high)
{
	if (low < high)
	{
		int pivotpos = Partition(a,low,high);//对其进行划分为两个子表的操作。
		QuickSort(a, low, pivotpos-1);
		QuickSort(a, pivotpos + 1, high);
	}
}

7.堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质

void HeadAdjust(int a[], int k, int len)
{
	int i, j,t;
	t = a[k];//a[0]暂存子树的根节点
	for (i=2*k;i<=len;i=i*2)//沿key较大的子节点向下筛选
	{
		if (i < len&&a[i] < a[i + 1])i++;//取key较大的子节点的下标
		if (t>= a[i])break;//筛选结束
		else
		{
			a[k] = a[i];//将a[i]调整到双亲节点上
			k = i;//修改k的值，以便继续向下筛选。
		}
	}
	a[k] = t;//被筛选节点的值放在最终位置
}
void BuildMaxHeap(int a[],int len) 
{
	for (int i = len / 2; i >0; i--)
		HeadAdjust(a, i, len);
}

void HeapSort(int a[],int len) 
{
	int i;
	BuildMaxHeap(a, len);
	for ( i = len; i >1; i--)
	{
		swap(a[i], a[1]);
		HeadAdjust(a, 1, i-1);
	}
}