排序稳定性和分类
稳定性:
如果在元素序列中有两个元素R[i]和R[j]，他们的排序码K[i]==K[j]，且在排序之前，R[i]在R[j]前面。若在排序后，R[i]仍然在R[j]前面，则称这个算法是稳定的。否则，这个算法是不稳定的。
怎么理解稳定性？稳定性是指相同元素在排序后相对位置保持不变。举个例子，如果A和B的值相同，排序前B是在A的后面，那么按值排序后B仍然在A的后面，这就叫稳定。
分类
内排序和外排序
内排序是在排序的整个过程中，待排序的所有记录全部被放置在内存中。
外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。
我们把内排序分为插入排序、交换排序、选择排序和归并排序
交换排序
冒泡排序
最简单的一种排序算法，小的往左移动，大的往右，整个过程就像是水中气泡上浮。在相邻两个元素的比较中，如果相等，则没有必要交换。
void BubbleSorting(int a[] , int n)
{
for(int i = 0; i < n-1; i++)
{
for(int j = 0; j < n-1-i; j++)
{
if(a[j] > a[j+1])
{
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
冒泡排序优化
如果我们的待排序序列已经是有序的，那么之后的大量比较就是多余的了，所以我们设置标记flag，如果有数据交换，则flag为true，直到没有数据交换的时候，退出最外层循环。这样可以避免因已经有序的情况下的无意义循环判断。
void BubbleSorting(int a[] , int n)
{
Status flag=TRUE;
for(int i = 0; i < n-1 && flag; i++)
{
flag = FALSE;
for(int j = 0; j < n-1-i; j++)
{
if(a[j] > a[j+1])
{
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag=TRUE; /*有数据交换*/
}
}
}
}
快速排序
快速排序（Quick Sort）的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
这里分享一篇介绍快排的文章，看了之后会更容易理解快排。
坐在马桶上看算法：快速排序
从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。
需要让右边的哨兵先出动，这一点非常重要。
左边的哨兵找到了比6大的值，右边的哨兵找到了比6小的值，交换。
再次寻找
然后哨兵们相遇了，停留在3这里
我们将基准数6和3进行交换。
到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。
先选取一个关键字，然后想尽办法将它放到一个位置，使得它的左边的值都比它小，右边的值都比它大，我们将这样的关键字成为枢轴（pivot）。
最开始选取的6就是枢轴，完成第一轮排序之后，再对6两边的低子表和高子表进行同样的操作，也就是递归操作。
void quicksort(int* a,int low,int high)
{ //注意参数，low指的是数组的最小下标，high指的是数组的最大下标
int i,j,t,temp;
if(low>high)
return; //递归出口
temp=a[low]; //temp中存的就是基准数
i=low;
j=high;
while(i!=j)
{
//顺序很重要，要先从右边开始找
while(a[j]>=temp && i<j)
j--;
//再找左边的
while(a[i]<=temp && i<j)
i++;
//交换两个数在数组中的位置
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最终将基准数归位
a[low]=a[i];
a[i]=temp;
quicksort(a,low,i-1);//继续处理左边的，这里是一个递归的过程
quicksort(a,i+1,high);//继续处理右边的 ，这里是一个递归的过程
}
快排优化
- 优化选取枢轴
- 随机选取：如果首个关键字太大或者太小都会影响性能，我们选取首个作为枢轴就变成了一种不合理的做法。所以随机选取获得一个low与high之间的数rnd有利于解决。
- 三数取中法：取三个关键字先进行排序，将中间数作为枢轴，一般是左、右、中间三个数。
- 九数取中：分三次取样，每次取三个数，三个样品各取中数，再从中取中数。
- 优化不必要的交换
-
优化小数组时的排序方案
增加一个判断，当high-low不大于某个常数时（7或者50或者其它的）就用直接插入排序，保证最大化地利用两种排序的优势来完成工作。 -
优化递归操作
尾递归优化，两次递归变成迭代，缩减堆栈深度，提高整体性能。
选择排序
直接选择排序
通过遍历比较，记录下最小值，然后和目标元素进行交换。
void selectSort(int* a,int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
int min=i;
for(j=i+1;j<n;j++) //遍历完剩下的数字
{ //如果有比当前最小值小的数字，把下标赋给它
if(a[j]<a[min])
{
min=j;
}
}
if(i!=min){ //如果min不等于i，说明找到最小值，交换
temp = a[i];
a[i]=a[min];
a[min]=temp;
}
}
}
推排序
直接选择排序的升级版
分享一篇不错的文章：图解排序算法之堆排序
完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是==完全二叉树==。
堆
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为==大顶堆==（最大堆）；或者每个结点的值都小于或等于其左右孩子结点的值，称为==小顶堆==（最小堆）。如下图：
用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的基本步骤
-
构造初始堆
将给定的无序序列依次存入数组，该数组即为一颗完全二叉树，将这棵二叉树构造成堆（一般升序采用大顶堆，降序采用小顶堆）。从最后一个非叶节点开始递减，逐次将每个相应的二叉树调整成大顶堆，最后，整个二叉树即为大顶堆。必须注意的是，在交换之后，必须考量节点对其子节点是否有影响，判断是否还满足大顶堆（小顶堆）的原则，每一次交换都必须要循环把子树部分判断清楚。 - 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
- 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤。数组分为两部分：堆与已排序列，直至最后一个堆元素，整个序列有序**
简单点说就是：
1.存入数据（完全二叉树）
2.将前n个元素调整为最大堆
3.交换堆顶和堆尾元素，n=n-1，转2
void swap(int* a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void HeapAdjust(int H[],int start,int end)//堆调整，将start和end之间的元素调整为最大堆
{
//元素从数组下标1开始储存，所以parent访问二叉树左右儿子分别为2*parent 和 2*parent+1；
int temp=H[start];
int parent=start,child;
while(2*parent<=end)
{
child=2*parent;
if(child!=end&&H[child]<H[child+1])++child;
if(temp>H[child])break;
else H[parent]=H[child];
parent=child;
}
H[parent]=temp;
}
void HeapSort(int H[],int L,int R)//堆排序
{
for(int i=(R-L+1)/2;i>=L;--i)//调整整个二叉树为最大堆
HeapAdjust(H,i,R);
for(int i=R;i>=L;--i)
{
swap(H,L,i);
HeapAdjust(H,L,i-1);
}
}
使用实例：
int a[10]={0,50,10,90,30,70,40,80,60,20};
HeapSort(a,1,9);
其实以上代码还不算很好理解，可以看看《大话数据结构》里面的代码实例。
