快速排序 C语言实现-蒲公英云

快速排序 C语言实现

快速排序

快速排序(Quick Sort )是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的一次交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。

课本上的例子：

在这里插入图片描述
时间复杂度

最好情况：O(n l o g 2 log_2 log2n)
最坏情况：O( n 2 n^2 n2)
平均情况：O(n l o g 2 log_2 log2n)

空间复杂度

O( l o g 2 log_2 log2n)

算法特点：

1）记录非顺次的移动导致排序方法是不稳定的。
2）排序过程中需要定位表的下界和上界，所有适合用于顺序结构，很难用于链式。
3）当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、n较大时的情况。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100 //顺序表最大容量，可以自行加大 
typedef struct 
{ 
    int key;//关键字项 
    char *otherinfo;//其他数据项 
}ElemType;//记录类型 
typedef struct
{ 
    ElemType Data[MAXSIZE+1];//静态顺序表的数据域，这里Data[0]为空闲或者为哨兵单元 
    int length;//顺序表的长度 
}SqList;//顺序表 
void InitList(SqList &L)//顺序表的初始化 
{ 
    L.length = 0;//使顺序表长度归0，便是顺序表的初始化 
}
void CreateList(SqList &L)//顺序表的创建 
{ 
    printf("请输入："); 
    while(1)//建立一个死循环，循环终止条件是按了enter键 
    { 
        L.length++;//顺序表长度加一 
        if(L.length>MAXSIZE)//判断是否超出最大容纳量 
        { 
            printf("顺序表已满！\n");
            return ;
        }
        scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
        if(getchar() == '\n')//循环终止条件 
            break;
    }
}
void InputList(SqList L)//顺序表的输出 
{ 
    int i;//记录次数 
    if(L.length == 0)//判断顺序表是否为空 ，若为空结束该函数 
    { 
        printf("顺序表是空的！\n");
        return ;
    }
    printf("打印为：");
    for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
        printf("%d ",L.Data[i].key);    
}
int Partition(SqList &L,int low,int high)//对顺序表L中的子表Data[low…high]进行一趟排序，返回驱轴位置 
{ 
    L.Data[0] = L.Data[low];//用子表的第一个记录做驱轴记录 
    while(low < high)//当low==high时终止循环 ，从表的两端交替地向中间扫描 
    { 
        while(low<high&&L.Data[0].key<=L.Data[high].key)
            high--;
        L.Data[low] = L.Data[high];//将比驱轴记录小的记录移到低端 
        while(low<high&&L.Data[0].key>=L.Data[low].key)
            low++;
        L.Data[high] = L.Data[low];//将比驱轴记录大的记录移到高端 
    }
    L.Data[low] = L.Data[0];//驱轴记录到位 
    return low;//返回驱轴位置 
}
int pivotloc;//递归函数中不宜定义变量，故定义一个全局变量 
void QSort(SqList &L,int low,int high)//调用前置初值：low=1;high=L.length; 
{ //对顺序表L中的字序列L.Data[low…high]做快速排序，递归算法 
    if(low < high)//长度大于1，递归终止条件 
    { 
        pivotloc = Partition(L,low,high);//将L.Data[low…high]一分为二，pivotloc是驱轴位置 
        QSort(L,low,pivotloc-1);//对左子表递归排序 
        QSort(L,pivotloc+1,high);//对右子表递归排序 
    }
}
void QuickSort(SqList &L)//对顺序表L做快速排序 
{ 
    QSort(L,1,L.length);
}
int main()
{ 
    SqList L;
    InitList(L);//初始化顺序表 
    CreateList(L);//创建顺序表 
    QuickSort(L);//快速排序 
    InputList(L);//打印排序后结果 
    return 0;
}