排序的特征
- 稳定性
稳定性是指关键字相同的数据，在排序完成后位置会不会发生变化。比如现在一个成绩单，A的成绩是86，B的成绩也是86，现在分别位于 数组的第10个位置，和第11个位置。当然还有很多其他的人成绩，比如一共50个人。在对这50个人排序的完成后，A的位置会不会和B的位置交换。如果发生了交换B出现在了A前面，不是按照原来的先后顺序了，发生这样的情况就是不稳定的排序。如果排序后相同的关键字所在的位置的先后顺序并没有发生变化就是稳定的排序。 - 内排序和外排序
排序过程中待排序的数据是否全部被放置在内存中，排序分为内排序和外排序。内排序所有的数据必须全部放在内存中，外排序是排序记录的个数太多，内存放不下， 需要在内外村多次交换数据才行。
排序性能影响因素:
- 时间
主要是比较和移动，高效率的排序算法应该是尽量少的移动和比较次数 - 空间
空间包括存放数据所需要的空间还有其他的辅助空间 - 算法复杂性
这里是算法本身的复杂度。
以下的讨论中都是对包含n个整形元素的无序数组进行升序排序。
常见的排序算法
- 冒泡排序
学习计算机语言时学到的最基本的排序算法之一，每两个相邻的元素比较大小，根据规则交换位置，第一趟冒泡可以保证第n个元素归位，第二趟是n-1位，依次类推。经过n趟排序可以使得所有元素归位。
下面这个是一个非正规的冒泡排序,它用当前位置的元素和后面的元素依次比较，然后交换位置，实现排序的。
第i次移动完成可以保证第i小元素处于正确的位置。
int Arr[] = {9,5,7,6,4,8,1,3,2};
int cnt = sizeof(Arr)/sizeof(Arr[0]);
for (int i = 0; i < cnt ; i++) {
for (int j = i+1; j < cnt; j++) {
if (Arr[i] > Arr[j]) {
int t = Arr[i];
Arr[i] = Arr[j];
Arr[j] = t;
}
}
}
冒泡排序:第i趟排序保证第i大的数移动到相应位置，每次都是和相邻的元素比较的
for (int i = 0; i < cnt ; i++) {
for (int j = 0; j < cnt-i-1; j++) {
if (Arr[j] > Arr[j+1]) {
int t = Arr[j+1];
Arr[j+1] = Arr[j];
Arr[j] = t;
}
}
}
冒泡排序内层循环因为没有条件判断所以无条件执行，影响效率，比如如果排序的内容后半部分本来就是有序的，上述程序依然要走内部循环，最差的情况下是数组本来就是有序的，依然要经过两层循环判断，所以可以考虑增加标志位优化下。
int flag = 1;
for (int i = 0; i < cnt && flag == 1; i++) {
flag = 0;
for (int j = 0; j < cnt-i-1; j++) {
if (Arr[j] > Arr[j+1]) { //如果这里一次都没有走说明从j到n-1的元素本来有序
int t = Arr[j+1];
Arr[j+1] = Arr[j];
Arr[j] = t;
flag = 1;
}
}
}
冒泡算法没有改进前时间复杂度固定是O(n^2)改进后的，改进后 最好的情况下没有数据要交换就是需要进行n-1次比较，所以时间复杂度是O(n)，最坏的情况下，数据都是逆序的，一次交换都不会少复杂度是O(n^2）。
2.选择排序
for (int i = 0; i<cnt; i++) {
int min = i;//假定当前位置的元素的大小是最小的
for (int j = i+1; j < cnt; j++) {//用当前位置的元素和后面的元素依次比较，取的最小位置的下标
if (Arr[min] > Arr[j]) {
min = j;
}
}
if (min!=i) {//循环结束以后交换遍历得到的最小值和当前值的位置
int t =Arr[i];
Arr[i] = Arr[min];
Arr[min] = t;
}
}
选择排序交换的次数非常少。交换次树等于外部循环的次数。节约了很多时间。无论最好还是最坏。比较的次数是一样的第i趟排序需要进行n-i次关键字比较，一共需要n*(n-1)/2次。对于交换次数，最好时候是0次。最差的时候是n-1次。所以时间复杂度为O（n^2),但是因为交换的次数少性能高于冒泡排序
3 . 插入排序
插入排序是通过维持从0到i-1部分是有序的序列，然后通过比较i和i-1的大小，然后根据规则将逆序的元素插入有序序列合适的位置，并且维持0到i-1的元素依然有序，这样当i =n时所有的元素都有序了
for (int i = 1; i<cnt; i++) {
//后面的数据小于前面的数据说明位置反了。需要插入到有序的序列。[0,i-1]的都是有序的
if (Arr[i]<Arr[i-1]) {
//将Arr[i]插入到[0,i-1]的有序区间，并且保证区间仍然有序
int t = Arr[i];
for (j = i-1; Arr[j] >t ;j--) {
Arr[j+1] =Arr[j];
}
Arr[j+1] = t;
}
}
//这个是自己写的，算不上插入排序，因为是不断的交换位置保证前面的序列有序的
for (int i = 1; i<cnt; i++) {
//后面的数据小于前面的数据说明位置反了。需要插入到有序的序列。[0,i-1]的都是有序的
if (Arr[i]<Arr[i-1]) {
//将Arr[i]插入到[0,i-1]的有序区间，并且保证区间仍然有序
for (int j = i; j>0&&Arr[j]<Arr[j-1];j--) {
int t = Arr[j];
Arr[j] = Arr[j-1];
Arr[j-1] = t;
}
}
}
复杂度分析。当排序本身有序的时候只是进行了比较n-1次，并没有一次插入。时间复杂度是O(n).最坏的情况下逆序的情况需要比较 1+2+3+..n-1 大约n2/2次，而同时，移动次数也达到最大值大约是n2/2,如果排序记录是随机的，概率相同，平均比较和移动次数大约是n^2/4，所以插入排序比选择和冒泡要好。
** 上面三种都是时间复杂度为O(n^2)的内排序算法。**
4 . 希尔排序
希尔排序是对插入排序的优化。
希尔排序法让待排序的记录个数减少，将原来的大量记录数的记录分割成多个组，保证每个组基本有序。基本有序是小的关键字基本在前面，大的基本在后面，{2，1，3，6，4，7，5，8，9}就可以称为基本有序。{1，5，9，，3，8，7，2，4，6}就不能。希尔排序采用了分割跳跃的策略，将相聚某个增量的记录组成一个子序列，在子序列内分别进行直接插入得到基本有序的结果。
int i,j,t;
int increment = cnt;//通过设置了increment，作为步数。达到先构建局部有序的，局部的操作是插入排序
do {
increment = increment/3;
//increment最后的值必须为1，此时相当于插入排序，但是经过前面的跳跃
//比较能够使得数组基本有序，所以increment等于1的时候效率会很高
//如果最后的increment没有在等于1的时候运行下面代码，会导致某些元素
//漏掉导致排序不成功
for (i = increment+1; i<cnt; i++) {
if (Arr[i]<Arr[i-increment]) {
t = Arr[i];
for (j=i-increment; j>=0&&t<Arr[j]; j-=increment) {//局部的
Arr[j+increment] = Arr[j];
}
Arr[j+increment] =t ;
}
}
} while (increment>1);
因为插入排序在O(n^2)的算法中，平均效率相对较好，尤其是在元素基本有序的情况下或者记录较少的时候会效率会提高很多，所以希尔排序通过设置
步长使得数据不在相邻的比较，将数组按照步长分组，使得整体基本有序，然后不断缩小步长提高效率。increment量的最后必须是1，否则无法完成排序。increment取值为2(t-k+1)，0<=k<=t<=[log2(n+1)]为O(n1.5)。
5 . 归并排序
归并排序是利用归并的思想进行排序，假设排序序列有n个记录，可以看成n个有序序列，每个子序列的长度为1，然后将每个子序列的两两合并得到n/2向上取整个有序子序列，然后两两合并直到得到一个长度为n的有序序列。主要就是分割，合并。
/*
SR中有两个有序的子序列分别是[i,m],和[m+1,n]，将这两个子序列合并成一个有序的序列，放到TR。
*/
void merge(int SR[],int TR[],int i,int m,int n)
{
int j,k,t;
//同时便利两个序列,按大小顺序放入TR
for (j=m+1,k=i,t=i;k<=m&&j<=n; t++) {
if (SR[k]<SR[j]) {
TR[t]=SR[k++];
}else{
TR[t]=SR[j++];
}
}
//如果其中一方有剩余，直接将追加到TR中就可以了
for (; k<=m; k++) {
TR[t]=SR[k];
t++;
}
for (; j<=n; j++) {
TR[t] = SR[j];
t++;
}
}
/*
SR 源数组，TR1是排序后数据存放的数组，s表示数组的起点索引，t表示终点索引
*/
void Msort(int SR[],int TR1[],int s,int t)
{
int m;
int TR2[10];
if (s==t) {//只有一个元素说明是最小子序列无法继续拆分了，直接放入目标数组
TR1[s]=SR[s];
}
else
{
m = (s+t)/2;//讲SR平分
//-- 这里的TR2传值方式是传递地址
Msort(SR, TR2, s, m);//对左边[s,m]归并为有序的TR2[s,m];
Msort(SR, TR2, m+1, t);//对右边[m+1,t]归并到有序的TR2[m+1,t]
merge(TR2, TR1, s, m, t);//将在[s,m]和[m+1,t]分别有序的TR2通过合并算法合并到TR1
}
}
一趟归并需要将SR[0]到SR[n]相邻的长度为h的有序序列进行两两归并，并将结果放入TR1里面，需要将待排序序列所有记录扫描一遍，耗费O(n),整个归并排序需要log2n次，所有总的事假复杂度为nlogn,和原始数据的顺序无关;归并排序过程中需要与原始记录长度相同的控件存放结果，以及递归时需要深度为log2n的栈空间，时间复杂度是O(n+log2n),并且是一种稳定排序的算法，
归并排序是比较占内存，但是效率缺高稳定的算法。
6 . 快速排序
通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字比另一部分小，可以对这两部分记录继续进行按照这个规则排序，使得整个数组有序。
void Qsort(int * arr,int start,int end)
{
if (start>end) {
return;
}
int base = arr[start];//取左边的第一个元素作为基准元素
int i = start;
int j = end;
// 基准数是任意的，但是为了方便和递归方便，所以找可以选择最左边的,基准数是 //最左边的时候要从最右边开始寻找进行j--。
//这是为了保证一定会停在比基准数大的位置上。
while (i!=j) {
while (arr[j]>=base&&j>i) {//右边找一个比基准数小的数，从右边开始找
j--;
}
while (arr[i]<=base&&i<j) {//左端找比基准数大的数
i++;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;//找到后交换两个数的位置
}
if (i==j) {//当前后相遇的时候，交换基准数和当前位置的数
arr[start] = arr[i];
arr[i] = base;
}
//然后对相遇的左边序列和右边序列继续递归排序
Qsort( arr, start,i-1);
Qsort (arr, i+1 ,end);
}
快速排序的时间性能，取决于递归的深度，在最优的情况下，每次都是平分两半，总共需要log2n次，然后每次都是遍历平分序列需要时间O(n)，所以最优情况O(nlog2n),最坏的情况下，排序的序列为正序或者逆序，每次划分比上次划分少一个记录的子序列，另一个为空，需要进行n-1次递归调用，时间复杂度为O(n^2)，快速排序相当于对冒泡排序算法的升级;利用数学归纳法可以证明平均情况下时间复杂度为nlog2n、，算法的效率体现在基准数大小，太大或者太小都会造成浪费，如果选取的数总是中间数的话，while里面的交换次数就会增加，相对俩说遍历过程利用率就高了，所以快速排序可以在选取基准数上进行优化，这里只是最基本的。
7 . 堆排序
堆：堆是完全二叉树最典型的应用。最大堆，完全二叉树的所有的父节点都比子节点大。反之为最小堆。这里可以用二叉树的性质来建立堆。用二叉树的性质来描述父子节点的关系，也可以使用包含左右子树只针对结构表示节点和节点之间的关系。
堆排序：
将待排序的序列构成一个大顶堆，最大值在堆顶，将最大值与数组的末尾交换，此时末尾元素就是最大值，然后将剩下的n-1一个元素重新构建成一个堆，可以得到n个元素中次大值，反复执行，可以得到一个有序序列，根据实际需求确认建立最大堆还是最小堆。
实现步骤
- 把无序序列构建成完全二叉树
构建完全二叉树。直接用数组保存树的节点，然后利用二叉树的性质实现树的遍历和调整节点的位置，比起二叉链表的实现要方便很多。
for (int i =1; i<=sum; i++) {
heapArr[i] = arr[i-1];//根据原始数组里面的数据，构建一个完全二叉树,完全二叉树的节点从1开始，方便计算
}
- 将完全二叉树调整成为堆
可以选择递归方式，也可以选择非递归方式。
//在一个完全二叉树中调整curIdx节点的位置，使得完全二叉树满足堆的特性
void setNodeP(int curIdx,int maxNode)
{
if (curIdx*2>maxNode) {//这里说明访问的节点是叶子节点
return;
}
int t=curIdx;
//和左子树比较节点大小
if (heapArr[curIdx]>heapArr[curIdx*2]) {
//向下调整
t = curIdx*2;
}
if (curIdx*2+1<=maxNode) {//和右节点比较大小
if (heapArr[t]>heapArr[curIdx*2+1]) {
t =curIdx*2+1;
}
}
if (t!=curIdx) {//应该继续向下调整，就是和左孩子节点或者右孩子节点交换位置
int tem = heapArr[curIdx];
heapArr[curIdx] = heapArr[t];
heapArr[t]=tem;
setNodeP(t,maxNode);//递归调整
}
}
void swap(int x,int y)
{
int t;
t =heapArr[x];
heapArr[x]=heapArr[y];
heapArr[y]=t;
return;
}
void siftdown(int i)
{
int t,flag =0;
while (i*2<=max && flag==0) {
if (heapArr[i]>heapArr[2*i]) {
t = i*2;
}
else{
t=i;
}
if (i*2+1<=max) {
if (heapArr[t]>heapArr[i*2+1]) {
t=i*2+1;
}
}
if (t!=i) {
swap(t, i);
i=t;
}else{
flag =1;
}
}
}
for (int idx = max /2; idx >=1; idx --) {
setNodeP(idx, max);
}
3.排序
可以直接依次取出堆顶元素，然后调整剩下的元素，使得二叉树依旧保持堆特性，比如上面建立的是最小堆，堆顶元素永远是当前集合中最小的。仅仅排序可以依次取出，但是这样不好，灵活性不够
// max = sum; //每次取走最上面的元素，然后把最大节点的元素放在顶部，重新调整，使得剩余的节点依旧满足最小堆的特性。
for (int i = 1; i<=sum; i++) {
int t = heapArr[1];
heapArr[1]=heapArr[max];
max--;
setNodeP(1, max);
printf("%d ",t);
}
可以通过依次调整堆的每个元素，使得完全二叉树按照层次遍历就可以得到有序的序列
,这样就对于介绍的时候应该建立最大堆，然后通过调节节点位置称为最小堆然后完成排序的过程了，因为上面建立的是最小堆。所以下面排序是从大到小，下面这个灵活性强，比如当某个元素大小改变时。可以很快的重新构建成有序序列，依然仅仅是下面的代码。
for (int i = sum; i>1; i--) {
swap(1, i);//第一个元素和最后一个元素的位置，此时最后一个元素的最小值
setNodeP(1, i-1);//重新调整第一个元素的位置，使得二叉树仍然满足最小堆特性。
}
for (int i=1; i<=sum; i++) {
printf("%d ",heapArr[i]);
}
堆排序的运行时间主要是构建堆和重建堆的反复筛选，对于每个非叶子节点来说最多进行两次比较和互换，时间复杂度为O(n)，正式排序时第i次取堆顶元素用O(log2i)的时间（完全二叉树节点到根节点的距离是log2i + 1）,并且需要取n-1次堆顶记录，重建堆的复杂度为nlog2n。对数据原始状态不敏感，仅仅用了一个交换的临时单元作为辅助空间。此外因为初始化构建堆比较次数多，所以适合数据量非常大的情况,堆排序是不稳定的算法，相当于简单选择排序算法的升级。
