排序小结

插入排序----直接插入排序：
直接插入算法思想：
从第一个开始放置哨兵，
将前端不断的生成已经排好序的队列，
然后哨兵位不断的向后移动，将哨兵位的数不断的
插入前端排好序的队列中，直到哨兵到队列的最后
一位完成排序。
升序算法实现：
void sort(int a[],int n)
{
for(int i=1;i<n;i++)
{
int x=a[i];
int j=i-1;
for(;x<a[j]&&j>=0;j--)
{
a[j+1]=a[j];
}
a[j+1]=x;    
}
}
插入排序---希尔排序：
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
算法思想：
希尔排序是插入排序的一种，是对直接插入算法的改进，在一定程度上可以减少数据的移动次数，在一定规模上减少空间的浪费和加快排序的效率。
我们将整个待排序列按照希尔增量分割为若干个子序列进行直接插入排序，其中希尔增量的值是随意指定的，唯一要求是最后增量要减少到1，即最后一次进行直接插入排序。
升序排序算法实现：
void shellinsertsort(int a[],int n,int dk)
{
for(int i=dk;i<n;++i)
{
int x=a[i];
int j=i-dk;
for(;a[i-dk]>a[i]&&j>=0;j-=dk)
{
a[j+dk]=a[j];
}
a[j+dk]=x;    
}
}
void shellsort(int a[],int n)
{
int dk=n/2;
while(dk>=1)
{
shellinsertsort(a,n,dk);
dk=dk/2;
}
}


交换算法——冒泡算法：
算法思想：
冒泡算法的思想是用交换的方式将，最大数或者最小数不断向后放，直到序列生成
升序算法实现：
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
int t;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
交换排序——快速排序：
算法思想：
快速排序的思想是一般先选定最前端数，在从最前端和最后端开始向中间跳转，当后端数小于前端数时，交换两个数的位置，前端数向后移动一个单位，再进行比较，即将每次比较的大值交换到后面，将小值交换到前面，每次比较的值中一个为我们最先选定的值，当第一次遍历结束时将数据分为两个部分，前面部分的数都是小于选定值得，选定值后面的数都是大于选定值得，即我们一次遍历可以确定一个选定值得位置。在对我们分为的两个部分分别做类似的交换排序。即得从小到大的排序序列。从大到小的顺序思路正好相反。
升序算法实现：
void swap(int *a,int *b)  //完成两数的交换
{
int t=*a;
*a=*b;
*b=t;
}
int dingyuan(int a[],int low,int high)  //每一趟确定出一个选定值得位置，需要length-1趟即可完成排序
{
int key=a[low];
while(low<high)
{
while(low<high&&a[high]>=key)
high--;
swap(&a[low],&a[high]);
while(low<high&&a[low]<=key)
low++;
swap(&a[low],&a[high]);
}
a[low]=key;
return low;
}
void sort(int a[],int low,int high)
{
if(low<high)
{
int key=dingyuan(a,low,high); //以选定数将序列分为两部分
sort(a,low,key-1);     //递归选定数前面的子序列
sort(a,key+1,high);    //地柜选定数后面的子序列
}
}
选择排序---简单选择排序：
算法思想：
简单选择排序的思想和冒泡排序的思想类似，冒泡排序的思想是将最大的数或最小的数不断的选出构成排好序的序列，简单排序则是将最大数或者最小数向前放置最后产生一个有序的序列
升序算法实现：
for(int i=0;i<n;i++)
{
int k;
for(int j=i;j<n;j++)
{k=a[i];
if(k>a[j])
k=a[j];
}
a[i]=k;
}

选择排序---堆排序
堆排序是一种树形选择排序，是对简单选择排序的改进。将待排序列构造成为一个堆（完全二叉树），其中所有的父节点都大于或者小于他的所有子节点。
大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。
升序算法实现：
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;         // 当前待调整的结点放到比其大的孩子结点位置上  
    }  
}  
 
 
/**
 * 初始堆进行调整
 * 将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);  
  }  
}

归并迭代算法
算法思想：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素
升序算法实现：
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1)
    {
        if(sourceArr[i] >= sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}
 
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
    int midIndex;
    if(startIndex < endIndex)
    {
        midIndex = (startIndex + endIndex) / 2;
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}