快速交换排序C/C++代码实现

小鱼儿 2023-02-23 12:07 10阅读 0赞

## 举例： ##

快速排序(QuickSort) 是由冒泡排序改进而得的，选取一个记录作为枢轴（通常取第一个记录）一次性把小于的全冒到左边，然后对左右两边递归。  
快速排序方法中的一次交换可能消除多个逆序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
low和high两个指针轮流进行移动交换  
。![在这里插入图片描述][20200707113933902.png]

## 算法属性： ##

时间复杂度为O(nlog2(n))。  
空间复杂度最坏情况为O(n)  
不稳定排序。  
适合用于顺序结构，很难用于链式结构。  
当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、n较大时的情况。

## 代码实现： ##

#include<stdio.h>
    
    #define MAXSIZE 20
    typedef int KeyType;
    typedef int InfoType;
    //记录类型
    typedef struct {
        
    	KeyType key;
    	InfoType otherinfo;
    }RedType;
    //顺序表类型
    typedef struct {
        
    	RedType r[MAXSIZE + 1];  //r[0]闲置或作哨兵
    	int length;	  			 //顺序表长度
    }SqList;
    
    
    //快速交换排序
    //进行一趟排序并返回枢轴位置
    int Partition(SqList &L, int low, int high)
    {
        
    	L.r[0] = L.r[low];				//选第一个记录作枢轴
    	KeyType pivotkey = L.r[low].key;	//把枢轴记录关键字存在pivotkey中
    	while (low < high)
    	{
        
    		while (low < high && pivotkey <= L.r[high].key)
    		{
        
    			high--;
    		}
    		L.r[low] = L.r[high];
    		while (low < high && pivotkey >= L.r[low].key)
    		{
        
    			low++;
    		}
    		L.r[high] = L.r[low];
    	}
    	L.r[low] = L.r[0];
    	return low;
    }
    
    //将表L一分为二，并递归分别对子序列做快速排序
    void QSort(SqList &L, int low, int high)
    {
        
    	if (low < high)
    	{
        
    		int pivotloc = Partition(L, low, high);		//pivotloc为排序结束时枢轴的位置索引值
    		QSort(L, low, pivotloc - 1);
    		QSort(L, pivotloc + 1, high);
    	}
    }
    
    
    
    //打印排序结果
    void println(SqList L)
    {
        
    	for (int i = 1; i <= L.length; i++)
    	{
        
    		printf("%d, ", L.r[i].key);
    	}
    	printf("\n");
    }
    
    int main()
    {
        
    	SqList L;
    	L.r[1].key = 5;
    	L.r[2].key = 8;
    	L.r[3].key = 1;
    	L.r[4].key = 4;
    	L.r[5].key = 3;
    	L.length = 5;
    
    	//初始值low=1 ,  high=L.length
    	QSort(L, 1, L.length);
    	println(L);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200707113757217.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[20200707113933902.png]: https://img-blog.csdnimg.cn/20200707113933902.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200707114239310.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70