快速排序 C语言实现

﹏ヽ暗。殇╰゛Y 2022-12-22 11:12 157阅读 0赞

### 快速排序 ###

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

课本上的例子：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
**时间复杂度**

最好情况：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;
    }

![在这里插入图片描述][20201119220530155.png_pic_center]  
（完）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/c71e5f181ce74ab6afbe2a351c0b2fca.png
[20201119220530155.png_pic_center]: /images/20221120/6d309c701333421cbd5d436acc62aab1.png