1、直接插入排序，冒泡排序，快速排序，堆排序和归并排序
整个序列分为有序区和无序区，取第一个元素作为初始有序区，然后第二个开始，依次插入到有序区的合适位置，直到排好序。
void InsertSort(int arr[],int n){
for (int i =1;i <= n;++i){
for(int j = i;j > 0;--j)
{
if(arr[j] < arr[j -1])
{
int temp = arr[j];
arr[j] = arr[j -1];
arr[j -1] = temp;
}
}
}
}
/*直接插入排序
整个序列分为有序区和无序区，取第一个元素作为初始有序区，然后第二个开始，依次插入到有序区的合适位置，直到排好序。
*/
//从小到大排序
#include<iostream>
using namespace std;
int main()
{
int i=0,j=0,N=0,temp=0;
int a[16]={13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};
N=sizeof(a)/sizeof(a[0]);
for(i=0;i<N-1;i++)
{
for(j=i;j>=0;j--)//是将新加入的数在有序区里比较，有序区是从前往后逐渐建立的
{
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<N;i++)
cout<<a[i]<<" ";
return 0;
}
（第一个for循环对从第二个开始的所有的数字遍历，嵌套的for循环是每次遍历数字时都取无序区的一个元素与有序区的元素比较，如果比有序区的要小则交换，直到合适的位置。）
插入排序的时间复杂度最好的情况是已经是正序的序列，只需比较(n-1)次，时间复杂度为O(n)，最坏的情况是倒序的序列，要比较n(n-1)/2次，时间复杂度为O(n^2 ) ，平均的话要比较时间复杂度为O(n^2 )
插入排序是一种稳定的排序方法，排序元素比较少的时候很好，大量元素便会效率低下
解释1：比较相邻的元素，如果反序则交换，过程也是分为有序区和无序区，初始时有序区为空，所有元素都在无序区，经过第一趟后就能找出最大的元素，然后重复便可。
（
解释2：比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
）
（解释3：冒泡排序的思想就是将第一个元素与第二个元素比较，如果第一个元素比第二个元素大，那么就将两者交换，并继续用第二个元素和第三个元素比较，在一个循环结束后，最大的元素会沉到数组的最右边，因此，下次循环就直接到倒数第二个元素为止，最后的一次循环就只剩第一个元素，至此，所有元素都排列完成。这种排序是按照从小到大排序，；还可以按照从大到小的顺序排列，即最大的向左沉）
void BubbleSort(int arr[],int n)
{
for (int i = 0; i < n -1; i++)//控制最外层的循环次数，如果循环1次后，最右边的已经是最大的，第二次循环是i=1,那内存循环J就不用比较最后一个数了。
{
for (int j = 0; j < n - i -1; j++) {
if (arr[j] > arr[j +1]) {
int temp = arr[j];
arr[j] = arr[j +1];
arr[j +1] = temp;
}
}
}
}
#include<iostream>
using namespace std;
//int a[]={13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10}
int main()
{
int i=0,j=0,temp=0;
//冒泡算法，比较相邻元素，将大的沉底。i=0时，第一轮循环将最大数已经放到最后了，
//第二轮循环i=1时，这是比较相邻元素时需要将最后一个排除，以此类推，比较i轮，则排除i个在最后的元素
int a[16]={13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};
int N=sizeof(a)/sizeof(a[0]);
cout<<"N="<<N<<endl;
for(i=0;i<N-1;i++)
{
for(j=0;j<N-1-i;j++)//N-1-i 中的i是已经比较后的有序区的数字，位于最后面
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<N;i++)
cout<<a[i]<<" ";
return 0;
}
时间复杂度最坏的情况是反序序列，要比较n(n-1)/2次，时间复杂度为O(n^2 )，最好的情况是正序，只进行(n-1)次比较，不需要移动，时间复杂度为O(n)，而平均的时间复杂度为O(n^2 )
快速排序时间复杂度的最好情况和平均情况一样为O(nlog2 n)，最坏情况下为O(n^2 )，这个看起来比前面两种排序都要好，但是这是不稳定的算法，并且空间复杂度高一点（ O(nlog2 n)。快速排序适用于元素多的情况
http://blog.csdn.net/morewindows/article/details/6684558
对挖坑填数进行总结
1．i =L; j = R;将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
照着这个总结很容易实现挖坑填数的代码：
int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
{
int i = l, j = r;
int x = s[l]; //s[l]即s[i]就是第一个坑
while (i < j)
{
// 从右向左找小于x的数来填s[i]
while(i < j && s[j] >= x)
j--;
if(i < j)
{
s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
i++;
}
// 从左向右找大于或等于x的数来填s[j]
while(i < j && s[i] < x)
i++;
if(i < j)
{
s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
j--;
}
}
//退出时，i等于j。将x填到这个坑中。
s[i] = x;
return i;
}
再写分治法的代码：
void quick_sort1(int s[], int l, int r)
{
if (l < r)
{
int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
quick_sort1(s, l, i - 1); // 递归调用
quick_sort1(s, i + 1, r);
}
}
这样的代码显然不够简洁，对其组合整理下：
//快速排序
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);
}
}
/*
快速排序
选一个基准值，将待排序记录划分为独立的两部分，左侧的元素小于基准值，右侧的元素大于基准值，然后再分别对着两部分重复，直到整个序列有序
过程是和二叉搜索树相似，就是一个递归的过程
*/
/*
1．i =L; j = R;将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
*/
//在台式电脑上能运行成功
#include<iostream>
using namespace std;
int main()
{
int a[16]={13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};
int N=sizeof(a)/sizeof(a[0]);
quicksort(a,0,N-1);
for(int k=0;k<N;k++)
cout<<a[k]<<",";
cout<<endl;
}
int quicksort(int a[],int left,int right )
{
if(left<right)
{
int x=a[left], i=left,j=right;
while(i<j)
{
while(i<j && x<=a[j]) //从后向前寻找比a[i]小的数
j--;
if(i<j)//跳出循环后，i<j说明找到了比a[i]小的数
a[i++] = a[j];
while(i<j && a[i]<x)//从前向后寻找比a[i]大或者等于的数 从左向右找第一个大于等于x的数
i++;
if(i<j)
a[j--] = a[i];
}
a[i] = x;
quicksort(a, left, i - 1); // 递归调用
quicksort(a, i + 1, right);
}
}
直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。设数组为a[0… n-1]。
1. 初始时，数组全为无序区为a[0..n-1]。令i=0
2. 在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。
3. i++并重复第二步直到i==n-1。排序完成。
直接选择排序无疑是最容易实现的，下面给出代码：
void Selectsort(int a[], int n)
1. {
2. int i, j, nMinIndex;
3. for (i = 0; i < n; i++)
4. {
5. nMinIndex = i; //找最小元素的位置
6. for (j = i + 1; j < n; j++)
7. if (a[j] < a[nMinIndex])
8. nMinIndex = j;
9.
10. Swap(a[i], a[nMinIndex]); //将这个元素放到无序区的开头
11. }
12. }
在这里，要特别提醒各位注意下Swap()的实现，建议用：
1. inline void Swap(int &a, int &b) //inline是用于频繁调用函数时:inline 说明这个函数是内联的,在编译过程中内联函数会直接被源代码替换,提高执行效率
2. {
3. int c = a;
4. a = b;
5. b = c;
6. }
如果是不用中间数，即c交换数据，则函数为：
inline void Swap1(int &a, int &b)
{
if (a != b)
{
a ^= b; （a异或b)
b ^= a;
a ^= b;
}
}
/*
直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，
所不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，
而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。
*/
#include<iostream>
using namespace std;
int main()
{
int i=0,j=0,N=0,temp=0;
int a[16]={13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};
N=sizeof(a)/sizeof(a[0]);
for(i=0;i<N-1;i++)
{
temp=i; //假设最小数就是i对应的，然后从无序区里比较所有的数和i相比，找到最小数。
for(j=i+1;j<=N-1;j++) //要保证最后一个数也要比较，应该是小于等于
{
if(a[j]<a[temp])
temp=j;
}
swap(a[i],a[temp]);
}
for(i=0;i<N;i++)
cout<<a[i]<<" ";
return 0;
}
void Swap1(int &a, int &b) //这个是不采用中间数。就用a,b自身就能交换数据
{
if (a != b)
{
a ^= b; //（a异或b)
b ^= a;
a ^= b;
}
}
堆的结构类似于完全二叉树，每个结点的值都小于或者等于其左右孩子结点的值，或者每个节点的值都大于或等于其左右孩子的值
堆排序过程将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序
最小堆排序后是递减数组，要得到递增数组，可以使用最大堆。
//堆排序
void HeapSort(int arr[],int len){
int i;
//初始化堆，从最后一个父节点开始
for(i = len/2 - 1; i >= 0; --i){
Heapify(arr,i,len);
}
//初始化堆后，现在最上面的是最大的数了
//从堆中的取出最大的元素再调整堆
//堆排序是一种选择排序。建立的初始堆为初始的无序区。
排序开始，首先输出堆顶元素（因为它是最值），将堆顶元素和最后一个元素交换，这样，第n个位置（即最后一个位置）作为有序区，前n-1个位置仍是无序区，对无序区进行调整，得到堆之后，再交换堆顶和最后一个元素，这样有序区长度变为2。。。不断进行此操作，将剩下的元素重新调整为堆，然后输出堆顶元素到有序区。每次交换都导致无序区-1，有序区+1。不断重复此过程直到有序区长度增长为n-1，排序完成。
for(i = len - 1;i > 0;--i){
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;//就是将第一个数（最大的）和最后一个数对调了。
再在无序区里建立堆
Heapify(arr,0,i); //first=0,从新出现的堆从0开始网线看，i表示的当前参与比较的数组的长度 （这个操作是将大的数往下沉。）
void Heapify(int arr[], int first, int end){
int father = first;
int son = father * 2 + 1;//左孩子节点，
while(son < end){
if(son + 1 < end && arr[son] < arr[son+1])//存在右孩子节点，且右孩子节点比左孩子节点大，那就用右孩子来算。
{ ++son;}
//如果父节点大于子节点则表示调整完毕
if(arr[father] > arr[son]) break; //break是跳出while循环了
else {
//不然就交换父节点和子节点的元素
int temp = arr[father];
arr[father] = arr[son];
arr[son] = temp;
//父和子节点变成下一个要比较的位置
father = son;//（就是把原来的儿子节点看成根节点后，发现他下面还挂的有儿子节点，如果儿子节点比他大的话，还需要在while循环里换位置。
son = 2 * father + 1; //这一步有改变while循环条件里son的值，这是进行到中间层次的时候，相互交换后，把儿子的位置赋给father节点，然后再检查他下面有没有儿子节点，如果有的话还要执行while循环。
}
}
}
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1< nobr="">重复上述的分组和排序，直至所取的增量dt=1(dt<dt?l<…<d2<d1)< nobr="">，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。实际上当dt=1时，完全就是直接插入排序。但是经过多个分组的直接插入排序，最后一次完整的插入排序前数据表几乎已经是排好序了，因此shell sort充分利用了直接插入排序在数据表几乎已经有序的条件下工作高效的特点。
#include<iostream>
using namespace std;
int ShellPass(int* pData, int d) //一组增量为d的希尔插入排序
{
int temp;
int k=0;
for(int i=d+1;i<13;i++) //13代表'size+1'
{
if(pData[i]<pData[i-d])
{
temp=pData[i];
int j=i-d;
do
{
pData[j+d]=pData[j];
j=j-d;
k++;
}
while( (j>0) && (temp<pData[j]) );
pData[j+d]=temp;
}
k++;
}
return k;
}
void ShellSort(int* pData) //希尔排序
{
int count=0;
int ShellCount=0;
int d=12; //一般增量设置为数组元素个数，不断除以2以取小
do
{
d=d/2;
ShellCount=ShellPass(pData,d); //做一组增量为d的希尔插入排序
count+=ShellCount;
}
while(d>1);
cout<<"希尔排序中，关键字移动次数为:"<<count<<endl;
}
void main()
{
int data[]={10,9,8,7,6,5,4,3,2,1,-10,-1};
int size=sizeof(data)/sizeof(int);
cout<<"size="<<size<<endl; //计算数组的大小
ShellSort(data);
for(int i=0;i<size;i++)
cout<<data[i]<<" ";
cout<<endl;
}
