/*******************************************************************************/* <PRE>/* 版权所有    : -/* 模块名      : 排序/* 文件名      : sort.cpp/* 功能描述    : 排序方法的实现/* 作者        : <xxx>/* 版本        : 1.0/* -----------------------------------------------------------------------------/* 备注        : -/* -----------------------------------------------------------------------------/* 修改记录    :/* 日 期        版本     修改人        修改内容/* 2011/01/01   1.0      <xxx>         创建/* </PRE>/*******************************************************************************/*/*   1. 排序方法分类 (稳定的排序用‘Y‘表示，不稳定的排序用‘N‘表示)   /*/*   插入排序：直接插入排序(Y)、希尔排序/*   交换排序：冒泡排序(Y)、快速排序(N)/*   选择排序：直接选择排序(N)、堆排序(N)/*   归并排序：二路归并排序(Y)/*/*==============================================================================/*/*   2. 排序方法的特点/* /*   快速排序：适合对无序记录排序，平均性能最好，时间复杂度为O(nlogn)/*   直插排序：从待排序列中依次取出元素与已排子序列比较，找出在已排子序列中的位置。元素有序时比较次数最少。/*   冒泡排序：每一趟把最大元素置后/*   选择排序：从待排序列中选出最小的元素，放在已排子序列的末端。能在排序完成前能输出前几个最小的元素/*   堆排序：类似于选择排序，是完全二叉树的一种应用。一趟排序后最后一个元素或最大或最小/*   直接插入排序和冒泡排序：元素逐个比较，时间复杂度为O(n^2)/********************************************************************************/#include <stdio.h>/******************************************************************************/* 数据类型和常量定义/******************************************************************************/#define LQ(a, b) ((a) <= (b))/******************************************************************************/* 函数原型声明/******************************************************************************/void InsertSort(int x[], int n); //直接插入排序void BubbleSort(int x[], int n); //冒泡排序void QuickSort(int x[], int low, int high); //快速排序void SelectSort(int x[], int n); //简单选择排序/*******************************************************************************/* <FUNC>/* 函数名   : InsertSort/* 功能     : 直接插入排序/* 参数     : int x[],   待排序列/*            int n,     序列中元素个数/* 返回值   : -/* 备注     : -/* 作者     : <xxx>/* </FUNC>*******************************************************************************/void InsertSort(int x[], int n){    int sentinel = 0; /* sentinel: 哨兵 */    int i, j, k;    for(i = 1; i < n; i++) /* 序列中的第一个元素可以看成一个有序表 */    {        if(LQ(x[i], x[i - 1]))        {            sentinel=x[i]; /* 复制为哨兵 */            for(j = i - 1; j >= 0 && LQ(sentinel, x[j]); --j)                x[j + 1] = x[j]; /* 记录后移 */            x[j + 1] = sentinel; /* 插入到正确位置 */        }        printf("第 %d 趟排序后的结果: ", i); /*输出每一趟排序的结果*/        for(k = 0; k < n; k++)            printf("%d ", x[k]);        printf("\n");    }}/*******************************************************************************/* <FUNC>/* 函数名   : BubbleSort/* 功能     : 冒泡排序/* 参数     : int x[],   待排序列/*            int n,     序列中元素个数/* 返回值   : -/* 备注     : 一种交换排序/* 作者     : <xxx>/* </FUNC>*******************************************************************************/void BubbleSort(int x[], int n){    int temp, exchange;    int i, j, k;    for(i=n-1; i>0; i--)  //最多做n-1趟排序    {        exchange=0; //本趟排序开始前, 交换标志应为假        for(j=0; j<i; j++)        {            if(LQ(x[j+1], x[j]))            {                temp=x[j+1];                x[j+1]=x[j];                x[j]=temp;                exchange=1;            }        }        if(!exchange) //本趟排序未发生交换，提前终止算法            break;        printf("第 %d 趟排序后的结果: ", n-i); /*输出每一趟排序的结果*/        for(k=0; k<n; k++)            printf("%d ", x[k]);        printf("\n");    }}/*******************************************************************************/* <FUNC>/* 函数名   : QuickSort/* 功能     : 快速排序/* 参数     : -/* 返回值   : -/* 备注     : 一种交换排序/* 作者     : <xxx>/* </FUNC>*******************************************************************************/int Partition(int x[], int low, int high){    int sentinel = x[low];    int pivotkey = x[low];    while(low < high)    {        while(low<high && LQ(pivotkey, x[high])) --high;        x[low] = x[high];        while(low<high && LQ(x[low], pivotkey)) ++low;        x[high] = x[low];    }    x[low]=sentinel;    return low;}void QuickSort(int x[], int low, int high){    int pivotloc, k;    if(low < high)    {        pivotloc=Partition(x, low, high);        printf("排序过程: "); /*输出每一趟排序的结果*/        for(k=0; k<8; k++)            printf("%d ", x[k]);        printf("\n");        QuickSort(x, low, pivotloc-1);        QuickSort(x, pivotloc+1, high);    }}/*******************************************************************************/* <FUNC>/* 函数名   : SelectSort/* 功能     : 简单选择排序/* 参数     : -/* 返回值   : -/* 备注     : 一种选择排序/* 作者     : <xxx>/* </FUNC>*******************************************************************************/int SelectMinKey(int x[], int low, int high){    int temp = x[low], pos=low;    while(low <= high)    {        if(LQ(x[low], temp))        {            temp = x[low];            pos = low;        }        low++;    }    return pos;}void SelectSort(int x[], int n){    int i, j, k, temp;    for(i=0; i<n; i++)    {        j = SelectMinKey(x, i, n-1);        if(i!=j)        {            temp=x[i];            x[i]=x[j];            x[j]=temp;        }        printf("第 %d 趟排序后的结果: ", i+1); /*输出每一趟排序的结果*/        for(k=0; k<n; k++)            printf("%d ", x[k]);        printf("\n");    }}/*******************************************************************************/* <FUNC>/* 函数名   : main/* 功能     : 测试函数/* 参数     : -/* 返回值   : -/* 备注     : -/* 作者     : <xxx>/* </FUNC>*******************************************************************************/void main(){    int x[10] = {10, 35, 19, 23, 17, 18, -1, 3, 12, 5}, i;    printf("\n直接插入排序序列: ");    for(i=0; i<10; i++)            printf("%d ", x[i]);    printf("\n\n");    InsertSort(x, 10);    printf("\n\n");        int y[10] = {88, 29, 48, 37, 16, 5, 14, 32, -2, 11};    printf("冒泡排序序列: ");    for(i=0; i<10; i++)        printf("%d ", y[i]);    printf("\n\n");    BubbleSort(y, 10);    printf("\n\n");        int z[8] = {49, 38, 65, 97, 76, 13, 27, 49};    printf("快速排序序列: ");    for(i=0; i<8; i++)        printf("%d ", z[i]);    printf("\n\n");    QuickSort(z, 0, 7);    printf("\n\n");        int m[10] = {19, 45, 0, 17, 16, 8, 24, 14, 3, 11};    printf("简单选择排序序列: ");    for(i=0; i<10; i++)        printf("%d ", m[i]);    printf("\n\n");    SelectSort(m, 10);    printf("\n");}