排序的定义：
输入：n个数：a1,a2,a3,…,an
输出：n个数的排列:a1’,a2’,a3’,…,an’，使得a1’<=a2’<=a3’<=…<=an’。
In-place sort（不占用额外内存或占用常数的内存）：插入排序、选择排序、冒泡排序、堆排序、快速排序。
Out-place sort（内存和外存结合使用）：归并排序、计数排序、基数排序、桶排序。
①插入排序（直接插入排序）
将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。
步骤：
1、从第一个元素开始，该元素可以认为已经被排序。
2、取出下一个元素，在已经排序的元素序列中从后向前扫描。
3、如果该元素（已排序）大于新元素，将该元素移到下一位置。
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5、将新元素插入到该位置中。
6、重复步骤2。
#include <stdio.h>
#include <stdlib.h>
void swap(int *p1, int *p2)
{
int temp;
temp=*p1;
*p1=*p2;
*p2=temp;
}
void insertSort(int *a,int len)
{
int i,j;
for(i=0;i<len;i++)
{
for(j=i+1;j>=1;j--)
{
if(a[j]<a[j-1])
swap(&a[j],&a[j-1]);
}
}
}
②插入排序（希尔排序）
介绍：
希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1、插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率。
2、但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。
void shellsort1(int a[], int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2) //步长
for (i = 0; i < gap; i++) //直接插入排序
{
for (j = i + gap; j < n; j += gap)
if (a[j] < a[j - gap])
{
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}
}
③选择排序（简单选择排序）
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
操作方法：
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换。
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换。
以此类推…..
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换。
直到整个序列按关键码有序。
void selectSort(int *a, int len)
{
int i,j,min,mark;
for(i=0;i<len;i++)
{
min=a[i];
for(j=i+1;j<len;j++)
{
if(a[j]<min)
{
min=a[j];
mark=j
}
}
if(min!=a[i])
swap(&a[i],&a[mark]);
}
}
④选择排序（堆排序）
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
二叉堆的定义：
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：
1、父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2、每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
算法的实现：
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
* 已知H[s…m]除了H[s] 外均满足堆的定义
* 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,
*
* @param H是待调整的堆数组
* @param s是待调整的数组元素的位置
* @param length是数组的长度
*
*/
void HeapAdjust(int H[],int s, int length)
{
int tmp = H[s];
int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
while (child < length) {
if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
++child ;
}
if(H[s]<H[child]) { // 如果较大的子结点大于父结点
H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
s = child; // 重新设置s ,即待调整的下一个结点的位置
child = 2*s+1;
} else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
break;
}
H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
}
print(H,length);
}
/**
* 初始堆进行调整
* 将H[0..length-1]建成堆
* 调整完之后第一个元素是序列的最小的元素
*/
void BuildingHeap(int H[], int length)
{
//最后一个有孩子的节点的位置 i= (length -1) / 2
for (int i = (length -1) / 2 ; i >= 0; --i)
HeapAdjust(H,i,length);
}
/**
* 堆排序算法
*/
void HeapSort(int H[],int length)
{
//初始堆
BuildingHeap(H, length);
//从最后一个元素开始对序列进行调整
for (int i = length - 1; i > 0; --i)
{
//交换堆顶元素H[0]和堆中最后一个元素
int temp = H[i]; H[i] = H[0]; H[0] = temp;
//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
HeapAdjust(H,0,i);
}
}
int main(){
int H[10] = {3,1,5,7,2,4,9,6,10,8};
cout<<"初始值：";
print(H,10);
HeapSort(H,10);
//selectSort(a, 8);
cout<<"结果：";
print(H,10);
}
⑤归并排序
介绍：
归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
步骤：
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置。
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
4、重复步骤3直到某一指针达到序列尾。
5、将另一序列剩下的所有元素直接复制到合并序列尾。
解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
⑥交换排序（快速排序）
介绍：
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。
步骤：
从数列中挑出一个元素，称为 “基准”（pivot），重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
该方法的基本思想是：
1、先从数列中取出一个数作为基准数。
2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3、再对左右区间重复第二步，直到各区间只有一个数。
//快速排序
void quick_sort(int s[], int l, int r)
{
if (l < r)
{
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i + 1, r);
}
}
⑦交换排序（冒泡排序）
介绍：
冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
步骤：
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
static void bubble_sort(int[] unsorted)
{
for (int i = 0; i < unsorted.Length; i++)
{
for (int j = i; j < unsorted.Length; j++)
{
if (unsorted[i] > unsorted[j])
{
int temp = unsorted[i];
unsorted[i] = unsorted[j];
unsorted[j] = temp;
}
}
}
}
static void Main(string[] args)
{
int[] x = { 6, 2, 4, 1, 5, 9 };
bubble_sort(x);
foreach (var item in x)
{
Console.WriteLine(item);
}
Console.ReadLine();
}
⑧桶排序/基数排序
算法的主要思想: 待排序数组A[1…n]内的元素是随机分布在[0,1)区间内的的浮点数。辅助排序数组B[0….n-1]的每一个元素都连接一个链表。将A内每个元素乘以N(数组规模)取底,并以此为索引插入(插入排序)数组B的对应位置的连表中。最后将所有的链表依次连接起来就是排序结果。
这个过程可以简单的分步如下:
1、设置一个定量的数组当作空桶子。
2、寻访序列，并且把项目一个一个放到对应的桶子去。
3、对每个不是空的桶子进行排序。
4、从不是空的桶子里把项目再放回原来的序列中。