sorts

各种排序算法：

#include <stdio.h>    
#include <string.h>
#include <ctype.h>      
#include <stdlib.h>   
#include <io.h>  
#include <math.h>  
#include <time.h>

#define OK        1
#define ERROR    0
#define TRUE    1
#define FALSE    0

#define MAX_LENGTH_INSERT_SORT 7 /* 用于快速排序时判断是否选用插入排序阙值 */

typedef int Status; 

#define MAXSIZE 10000  /* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct
{
    int r[MAXSIZE+1];    /* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
    int length;            /* 用于记录顺序表的长度 */
}SqList;

/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j) 
{ 
    int temp=L->r[i]; 
    L->r[i]=L->r[j]; 
    L->r[j]=temp; 
}

void print(SqList L)
{
    int i;
    for(i=1;i<L.length;i++)
        printf("%d,",L.r[i]);

    printf("%d",L.r[i]);
    printf("
");
}

/* 对顺序表L作交换排序（冒泡排序初级版） */
void BubbleSort0(SqList *L)
{ 
    for( int i=1; i<L->length; i++)
    {
        for( int j=i+1; j<=L->length; j++)
        {
            if(L->r[i]>L->r[j])
            {
                 swap(L,i,j);        /* 交换L->r[i]与L->r[j]的值 */
            }
        }
    }
}

/* 对顺序表L作冒泡排序 */
void BubbleSort(SqList *L)
{ 
    for(int i=1;i<L->length;i++)
    {
        for(int j=L->length-1;j>=i;j--) /* 注意j是从后往前循环 */
        {
            if(L->r[j]>L->r[j+1])        /* 若前者大于后者（注意这里与上一算法的差异）*/
            {
                 swap(L,j,j+1);            /* 交换L->r[j]与L->r[j+1]的值 */
            }
        }
    }
}

/* 对顺序表L作改进冒泡算法 */
void BubbleSort2(SqList *L)
{ 
    Status flag = TRUE;            /* flag用来作为标记 */
    for( int i=1; i<L->length && flag; i++) /* 若flag为true说明有过数据交换，否则停止循环 */
    {
        flag = FALSE;                /* 初始为False */
        for(int j=L->length-1; j>=i; j--)
        {
            if(L->r[j] > L->r[j+1])
            {
                 swap(L, j, j+1);    /* 交换L->r[j]与L->r[j+1]的值 */
                 flag = TRUE;        /* 如果有数据交换，则flag为true */
            }
        }
    }
}

// 双向冒泡法
void Bubble_2 ( int r[], int n)
{  
    int low = 0;   
    int high = n-1; //设置变量的初始值  
    int tmp,j;

    while (low < high) 
    {  
        for (j = low; j< high; ++j)    // 正向冒泡,找到最大者  
            if (r[j] > r[j+1]) 
            {  
                tmp = r[j]; r[j] = r[j+1]; r[j+1] = tmp;  
            }   
        --high;            // 修改high值, 前移一位  
        for ( j = high; j > low; --j)    // 反向冒泡,找到最小者  
            if (r[j] < r[j-1]) 
            {  
                tmp = r[j]; r[j] = r[j-1]; r[j-1] = tmp;  
            }  
        ++low;            // 修改low值,后移一位  
    }   
} 

/*
多关键码排序方法：

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：

最高位优先(Most Significant Digit first)法，简称MSD法：
    1）先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等。
    2）再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后。
    3）再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

最低位优先(Least Significant Digit first)法，简称LSD法：
    1) 先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后。
    2) 最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

原理：
        按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
    有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。
    最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
    基数排序基于分别排序，分别收集，所以是稳定的。
@param:
    r: 原始数组
    
    // 原理版本
void RadixSort(int r[], int length, int maxradix )  
{  
    int k, lsp;  
    k = 1; 
    int n = 0;    // 基数内 序号
    int m = 1;  // 个位、十位

    int temp[10][length-1];  
    Empty( temp );    // 清空临时空间  

    while( k < maxradix )    // 遍历所有关键字  
    {  
        for(int i=0; i<length; i++) //分配过程  
        {  
            if(r[i] < m)  
                temp[0][n] = r[i];  
            else  
                lsp = (r[i]/m) % 10; //确定关键字  

            temp[lsp][n] = r[i];  
            n++;  
        } 

        CollectElement(r, temp); // 收集  
        n = 0;  
        m = m*10;  
        k++;  
    }  
} 
 */
    // 得到最大位数
int maxbit(int data[], int n)
{
    int nBit = 1;
    for(int i=0; i<n; i++)
    {
        int tempC = 1;
        int p = data[i];
        while( p/10 )
        {
            p = p/10;
            tempC++;
        }
        if( tempC > nBit )
            nBit = tempC;
    }
    return nBit;
}

void RadixSort(int data[], int n)
{  
    int* tmp = new int[n];
    int count[10];    // 每一桶中的个数
    int nBit = maxbit(data,n);
    int r=1;

    for(int i=0; i<nBit; i++)
    {
            // 装桶之前要先清桶
        for(int i=0;i<10;i++)
            count[i]=0;

        for(i=0;i<n;i++)    // 记录每个桶的个数
        {
            int k=data[i]/r;
            int q=k%10;
            count[q]++;
        }
        for(i=1; i<10; i++)    // 计算位置
        {
            count[i] += count[i-1];
        }
        for(int j=n-1; j>=0; j--)
        {
            int p = data[j]/r;
            int s = p%10;
            tmp[count[s]-1] = data[j];
            count[s]--;                
        }
        for(i=0; i<n; i++)
        {
            data[i] = tmp[i];        
        }            
        r = r*10;    // 更高一位

    }

}


// 计数排序
void CountSort(int* pData, int n)
{
    int* pCout = NULL;            // 记数的指针
    int* pSort = NULL;            // 暂存排序结果的指针
    pCout = (int*)malloc(sizeof(int) * n);    // 申请空间
    pSort = (int*)malloc(sizeof(int) * n);   


        // 初始化记数为0
    for (int i = 0; i < n; ++i)
    {
        pCout[i] = 0;
    }
        // 统计相同元素的个数
    for (int i = 0; i < n; ++i)
    {
        ++pCout[pData[i]];       
    }
        // pCout[i]中是 <= i 的元素个数
    for (int i = 1; i < n; ++i)
    {
        pCout[i] += pCout[i-1];    
    }
    for (int i = 0; i < n; ++i)
    {
        pSort[pCout[pData[i]]] = pData[i];    // 把每一个元素放在数组中相应的位置；因为pCout[pData[i]]的值就是不比他大数据的个数；      
        pCout[pData[i]]--;                    // 如果有相同数据的元素先减1
    }
        // 排序结束，复制到原来数组中
    for (int i = 0; i < n; ++i)
    {
        pData[i] = pSort[i];
    }
        // 释放申请的空间
    free(pCout);
    free(pSort);
}

/* 对顺序表L作简单选择排序 */
void SelectSort(SqList *L)
{
    int min;
    for( int i=1; i<L->length; i++)
    { 
        min = i;                        /* 将当前下标定义为最小值下标 */
        for ( int j = i+1;j<=L->length;j++)/* 循环之后的数据 */
        {
            if (L->r[min] > L->r[j])    /* 如果有小于当前最小值的关键字 */
                min = j;                /* 将此关键字的下标赋值给min */
        }
        if(i != min)                    /* 若min不等于i，说明找到最小值，交换 */
            swap(L, i, min);            /* 交换L->r[i]与L->r[min]的值 */
    }
}

// 简单选择排序的改进   二元选择排序
void SelectSort(int r[],int n) 
{  
    int i, j, min, max, tmp;  
    for (i = 1; i <= n/2; i++) 
    {    
            // 做不超过n/2趟选择排序   
        min = i; max = i ;    // 分别记录最大和最小关键字记录位置  
        for (j = i+1; j <= n-i; j++) 
        {  
            if (r[j] > r[max]) 
            {   
                max = j; 
                continue;   
            }    
            if (r[j] < r[min]) 
            {   
                min = j;   
            }     
        }    

        tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  // swap(a, min, i-1);
        tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;  // swap(a, max, n-i)
    }   
} 

/* 对顺序表L作直接插入排序 

插入排序（insert sorting)思想：
当插入第i个元素时，前面的v[0],v[1],v[2]......v[i-1],已经排好序了.
这时用v[i]的插入码与 v[i-1],v[i-2],......排序码进行比较，
找到插入的位置即插入v[i],原来位置上的元素从后向前依次后移。

时间复杂度:  平均比较次数O(n2),平均移动次数 O(n2).
直接插入排序是一种稳定的排序。元素大部分有序时 效率会更高，这时比较次数和移动次数都会减少。

*/
void InsertSort(SqList *L)
{ 
    int j;
    for( int i=2; i<=L->length; i++)
    {
        if (L->r[i] < L->r[i-1])        /* 需将L->r[i]插入有序子表 */
        {
            L->r[0] = L->r[i];            /* 设置哨兵 */
            for( j=i-1; L->r[j] > L->r[0]; j--)
                L->r[j+1] = L->r[j];    /* 记录后移 */

            L->r[j+1] = L->r[0];        /* 插入到正确位置 */
        }
    }
}

/* 对顺序表L作希尔排序 

希尔排序（Shell sort）基本思想: 改进的直接插入算法。
设待排序的元素序列有n个元素，首先取一整数gap（<n）作为间隔，将全部元素分为gap个子序列，
所有距离为gap的元素 放在同一序列中，在每个子序列中分别进行直接插入排序。
然后缩小gap，例如gap = gap/2,重复上述的子序列划分与排序工作。
开始由于gap取值大，每个子序列元素少，排序速度快，待排序后期，
gap值逐渐变小，子序列元素变多，但由于前面的工作基础，大多数元素已经有序，所以排序速度快。


希尔排序是一种不稳定的排序
*/
void ShellSort(SqList *L)
{
    int j, k = 0;
    int d = L->length;
    do
    {
        d = d/3 + 1;                /* 增量序列 */
        for(int i=d+1; i<=L->length; i++)
        {
            if (L->r[i] < L->r[i-d])    /*  需将L->r[i]插入有序增量子表 */ 
            { 
                L->r[0] = L->r[i];        /*  暂存在L->r[0] */
                for( j = i-d; j>0 && L->r[0]<L->r[j]; j -= d)
                    L->r[j+d]=L->r[j];    /*  记录后移，查找插入位置 */

                L->r[j+d]=L->r[0];        /*  插入 */
            }
        }
        printf("第%d趟排序结果: ",++k);
        print(*L);
    }
    while( d > 1 );

}


/*  
大根堆排序的基本思想： 
1) 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区; 
2) 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，
    由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key; 
3) 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。 
    然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，
    由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系 R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
*/

/*
 @brief:
     已知L->r[s..len]中记录的关键字除L->r[s]之外均满足堆的定义,
     本函数调整L->r[s]的关键字,使L->r[s..len]成为一个大顶堆
 @param:
    cur: 当前位置 s
    len: 当前状态的最大值

m:当前堆的大小
 */
void HeapAdjust(SqList *L, int cur, int len)
{ 
    int temp = L->r[cur];
    for(int j = 2*cur; j <= len; j *= 2)// 沿关键字较大的孩子结点向下筛选(大根堆)
    {
        if(j < len && L->r[j] < L->r[j+1])
            ++j;                        // j为关键字中较大的记录的下标
        if(temp >= L->r[j])
            break;                        /* 应插入在位置 cur 上 */

        L->r[cur] = L->r[j];
        cur = j;
    }
    L->r[cur] = temp;                    /* 插入 */
}

/*  对顺序表L进行堆排序 */
void HeapSort( SqList* L )
{
    for( int i = L->length/2; i>0; i--)    /*  把L中的r构建成一个大根堆 */
         HeapAdjust(L, i, L->length);

    for( int i = L->length; i>1; i--)
    { 
         swap(L, 1, i);                /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
         HeapAdjust(L, 1, i-1);        /* 将L->r[1..i-1]重新调整为大根堆 */
    }
}


#if 0


#include <iostream>
#include <algorithm>

using std::cout;
using std::cin;
using std::endl;

template<class T>
class Out
{
public:
    void operator()(T o)
    {
        cout<<o<<'	';
    }
};
template<class T>
void Swap(T& a,T&b)
{
    if(a == b)
        return;
    T t=a;
    a=b;
    b=t;
}
inline int Rt(int idx)
{
    return (idx<<1)+2;
}
inline int Lt(int idx)
{
    return (idx<<1)+1;
}

template<class T>
void HeapBuild(T* A,int idx,int size)
{
    int child;
    for(; idx<=size/2; idx=child)
    {
        child=Lt(idx);
        if (child<size&&A[child]>A[idx])
        {
            Swap(A[idx],A[child]);
        }
        child=Rt(idx);
        if (child<size&&A[child]>A[idx])
        {
            Swap(A[idx],A[child]);
        }
    }
}
template<class T>
void HeapSort(T* A, int size)
{
    if(size == 1)
        return;

    for (int i=size/2; i>=0; i--)
    {
        HeapBuild(A,i,size);
    }
    int i=size-1;
    cout<<"swap max number:"<<A[0]<<","<<A[i]<<endl;
    Swap(A[0],A[i]);
    //现在得到了一个最大值，对前size-1个递归调用HeapSort
    HeapSort(A, i);
}

int main()
{
    int size=0;
    cout<<"enter elements count num:"<<endl;
    cin>>size;
    //    size = 10;
    int* elems = new int[size];
    //    int elems[] = {1, 8, 4, 5, 6, 7, 11, 2, 3, 45};
    cout<<"Input all elements to be sorted:"<<endl;
    for(int i=0; i<size; cin>>elems[i++]);

    HeapSort(elems,size);
    std::for_each(elems,elems+size,Out<int>());
    delete []elems;

    system("pause");
    return 0;

}

#endif

#pragma region MergeSort
/*  
归并算法思想:
    分而治之(divide - conquer);每个递归过程涉及三个步骤
    1) 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
    2) 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
    3) 合并: 合并两个排好序的子序列,生成排序结果. 
*/

/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[],int TR[], int start, int mid, int end)
{
    int j,k,l;
    for(j=mid+1,k=start; start<=mid && j<=end; k++)    /* 将SR中记录由小到大地并入TR */
    {
        if (SR[start] < SR[j])
            TR[k] = SR[start++];
        else
            TR[k] = SR[j++];
    }
    if(start<=mid)
    {
        for(l=0; l<=mid-start; l++)
            TR[k+l] = SR[start+l];        /* 将剩余的SR[i..m]复制到TR */
    }
    if(j<=end)
    {
        for(l=0; l<=end-j; l++)
            TR[k+l] = SR[j+l];            /* 将剩余的SR[j..n]复制到TR */
    }
}

/* 递归法 */
/* 将SR[s..t]归并排序为TR1[s..t] */
void MSort(int SR[],int TR1[], int start, int end)
{
    int mid;
    int TR2[MAXSIZE+1];

    if(start == end)
    {
        TR1[start] = SR[start];
    }
    else
    {
        mid = (start + end)/2;        /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
        MSort(SR,TR2, start, mid);    /* 递归地将SR[s..m]归并为有序的TR2[s..m] */
        MSort(SR,TR2, mid+1, end);    /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */

        Merge(TR2,TR1, start, mid, end);    /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
    }
}

/* 对顺序表L作归并排序 */
void MergeSort(SqList *L)
{ 
    MSort(L->r, L->r, 1, L->length);
}


/* 非递归法 */
/* 
@brief:
    将SR[]中相邻长度为s的子序列两两归并到TR[] 
@param:
    size: 归并相邻字段的大小
     len: 原始数据的总长度
*/
void MergePass(int SR[],int TR[], int size,int len)
{
    int i = 1;

    while(i <= len-2*size+1)
    {            
        Merge(SR,TR, i, i+size-1, i+2*size-1);    // 两两归并（归并长度为 size 的两个相邻子序列）
        i += 2*size;        
    }

    if(i < len-size+1)                // 归并最后两个序列(尚有两个子序列，其中后一个长度小于len)
    {
        Merge(SR,TR, i, i+size-1, len);
    }
    else                            // 若最后只剩下单个子序列
    {
        for( int j = i; j <= len; j++)
            TR[j] = SR[j];
    }
}

/* 对顺序表L作归并非递归排序 */
void MergeSort2(SqList *L)
{
    int* TR = (int*)malloc( L->length * sizeof(int) );    /* 申请额外空间 */

    int _size = 1;
    while( _size < L->length )
    {
        MergePass(L->r, TR, _size, L->length);
        _size *= 2;        /* 子序列长度加倍 */

        MergePass(TR, L->r, _size, L->length);
        _size *= 2;        /* 子序列长度加倍 */
    }
}

/*
(归并)算法分析

1、稳定性
    归并排序是一种稳定的排序。

2、存储结构要求
    可用顺序存储结构,也易于在链表上实现。

3、时间复杂度
    对长度为n的文件，需进行log(n)趟二路归并,每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

4、空间复杂度
    需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
*/

#pragma endregion MergeSort

#pragma region QuickSort
/* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{ 
    int pivotkey;

    pivotkey = L->r[low]; /* 用子表的第一个记录作枢轴记录 */
    while(low < high)          /* 从表的两端交替地向中间扫描 */
    { 
        while(low<high && L->r[high]>=pivotkey)
            high--;
        swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */
        while(low<high && L->r[low]<=pivotkey)
            low++;
        swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */
    }
    return low; /* 返回枢轴所在位置 */
}

/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{ 
    int pivot;
    if(low < high)
    {
        pivot = Partition(L,low,high);    /*  将L->r[low..high]一分为二，算出枢轴值pivot */
        QSort(L, low, pivot-1);            /*  对低子表递归排序 */
        QSort(L, pivot+1, high);        /*  对高子表递归排序 */
    }
}

/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{ 
    QSort(L, 1, L->length);
}


/* 改进后快速排序******************************** */

/* 快速排序优化算法 */
int Partition1(SqList *L,int low,int high)
{ 
    int pivotkey;

    int m = low + (high - low) / 2; /* 计算数组中间的元素的下标 */  
    if (L->r[low]>L->r[high])            
        swap(L,low,high);    /* 交换左端与右端数据，保证左端较小 */
    if (L->r[m]>L->r[high])
        swap(L,high,m);        /* 交换中间与右端数据，保证中间较小 */
    if (L->r[m]>L->r[low])
        swap(L,m,low);        /* 交换中间与左端数据，保证左端较小 */

    pivotkey = L->r[low]; /* 用子表的第一个记录作枢轴记录 */
    L->r[0]  = pivotkey;    /* 将枢轴关键字备份到L->r[0] */
    while(low<high) /*  从表的两端交替地向中间扫描 */
    { 
        while(low<high&&L->r[high]>=pivotkey)
            high--;
        L->r[low]=L->r[high];
        while(low<high&&L->r[low]<=pivotkey)
            low++;
        L->r[high]=L->r[low];
    }
    L->r[low]=L->r[0];
    return low;        /* 返回枢轴所在位置 */
}

void QSort1(SqList *L,int low,int high)
{ 
    int pivot;
    if( (high-low) > MAX_LENGTH_INSERT_SORT )
    {
        while(low < high)
        {
            pivot = Partition1(L, low, high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */
            QSort1(L,low,pivot-1);        /*  对低子表递归排序 */
            QSort1(L,pivot+1,high);        /*  对高子表递归排序 */
            low=pivot+1;    /* 尾递归 */
        }
    }
    else
        InsertSort(L);
}

/* 对顺序表L作快速排序 */
void QuickSort1(SqList *L)
{ 
    QSort1(L, 1, L->length);
}

#pragma endregion QuickSort



#define N 9
int main()
{
   int i;
   
   /* int d[N]={9,1,5,8,3,7,4,6,2}; */
   int d[N]={50,10,90,30,70,40,80,60,20};
   /* int d[N]={9,8,7,6,5,4,3,2,1}; */

   SqList l0,l1,l2,l3,l4,l5,l6,l7,l8,l9,l10;
   
   for(i=0;i<N;i++)
     l0.r[i+1] = d[i];
   l0.length = N;

   l1=l2=l3=l4=l5=l6=l7=l8=l9=l10=l0;

   printf("排序前:
");
   print(l0);

   printf("初级冒泡排序:
");
   BubbleSort0(&l0);
   print(l0);
   
   printf("冒泡排序:
");
   BubbleSort(&l1);
   print(l1);
   
   printf("改进冒泡排序:
");
   BubbleSort2(&l2);
   print(l2);
   
   printf("选择排序:
");
   SelectSort(&l3);
   print(l3);
   
   printf("直接插入排序:
");
   InsertSort(&l4);
   print(l4);

   printf("希尔排序:
");
   ShellSort(&l5);
   print(l5);
    
   printf("堆排序:
");
   HeapSort(&l6);
   print(l6);

   printf("归并排序（递归）:
");
   MergeSort(&l7);
   print(l7);

   printf("归并排序（非递归）:
");
   MergeSort2(&l8);
   print(l8);

   printf("快速排序:
");
   QuickSort(&l9);
   print(l9);

   printf("改进快速排序:
");
   QuickSort1(&l10);
   print(l10);


/*大数据排序*/
/* 
    srand(time(0));  
    int Max=10000;
    int d[10000];
    int i;
    SqList l0;
    for(i=0;i<Max;i++)
        d[i]=rand()%Max+1;
    for(i=0;i<Max;i++)
        l0.r[i+1]=d[i];
    l0.length=Max;
    MergeSort(l0);
    print(l0);
*/

    system("pause");
    return 0;
}