数据结构之---C语言实现快速排序（多个版本）

快速排序基本上有如下版本

一、国内教材双向扫描版
二、单向扫描版本
三、随机化版本
四、三数取中分割法
五、非递归版

这里给我前两个版本（较为常用）

版本一：

双向扫描版本：

如图：

数据结构之---C语言实现快速排序（多个版本）

代码如下：

[cpp]view plain copy
//快速排序(版本一)  
//带枢轴  
//杨鑫  
#include <stdio.h>  
#include <stdlib.h>  
#define MAXN 100  
int a[MAXN + 1], n;  
void QuickSort(int left, int right)  
{  
    int i, j, t, temp;  
    if(left > right)  
            return;  
    temp = a[left];  
    i = left;  
    j = right;  
    while(i != j)  
    {  
        while(a[j] >= temp && i < j)  
        {  
            j--;  
        }  
        while(a[i] <= temp && i < j)  
        {  
            i++;  
        }  
        if(i < j)  
        {  
            t = a[i];  
            a[i] = a[j];  
            a[j] = t;  
        }  
    }  
    a[left] = a[i];  
    a[i] = temp;  
    QuickSort(left, i - 1);  
    QuickSort(i + 1, right);  
}  
int main()  
{  
    printf("=========快速排序版本一==========\n");  
    int i = 0, j, t, count = 0;  
    int T;  
    printf("请输入要对数据排序的个数:\n");  
    scanf("%d", &T);  
    while(T--)  
    {  
        scanf("%d", &a[i]);  
        i++;      
    }  
    QuickSort(0, i - 1);  
    printf("排序后的数据是:\n");  
    for(j = 0; j < i; j++)  
    {  
        printf("%d ", a[j]);  
    }  
    return 0;  
}  

版本二：

单项扫描：

[cpp]view plain copy
void quickSort2(int x[], int l, int r)  
{  
    if(l >= r)  
        return;  
    int m = l;  
    for(int i = l + l; i <= r; i++ )  
        {  
        if(x[i] < x[l])  
                {  
            swap2(x[++m], x[i]);  
        }  
    }  
    swap2(x[l], x[m]);  
    quickSort2(x, l, m - 1);  
    quickSort2(x, m + 1, r);  
  
}  
void swap2(int &a,int &b)  
{  
    if(a==b) return;//对同一地址的数据交换，会使其结果为0  
    a=a^b;  
    b=a^b;  
    a=a^b;  
}  

数据结构之---C语言实现快速排序（多个版本）

相关推荐