原理

快速排序法原理

C语言实现-数据结构课自己所写

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 40

typedef struct{
    char name[8];
    int score;
}Student;


int Partition(Student stu[],int low,int high)
{
    int pivotkey,piv_score;
    char piv_name[8];
    piv_score = stu[low].score;
    strcpy(piv_name,stu[low].name);
    pivotkey = stu[low].score;
    while (low<high)
    {
        while (low<high && stu[high].score >= pivotkey)
        {
            --high;
        }
        stu[low].score = stu[high].score;
        strcpy(stu[low].name,stu[high].name);
        while (low<high && stu[low].score<=pivotkey)
        {
            ++low;
        }
        stu[high].score = stu[low].score;
        strcpy(stu[high].name,stu[low].name);
    }
    stu[low].score = piv_score;
    strcpy(stu[low].name,piv_name);
    return low;
}

void QSort(Student stu[],int low,int high)
{
    int pivotloc;
    if (low < high)
    {
        pivotloc = Partition(stu,low,high);
        QSort(stu,low,pivotloc-1);
        QSort(stu,pivotloc+1,high);
    }
}

int main()
{
    Student stu[N];
    int i,n;
    printf("please input the number of students:");
    scanf("%d",&n);
    printf("please input name and score:\n");
    for (i=0;i<n;i++)
    {
        scanf("%s",stu[i].name);
        scanf("%d",&stu[i].score);
    }
    QSort(stu,0,n-1);
    printf("After sorted by score:\n");
    for (i=0;i<n;i++)
    {
        printf("%d  %s\n",stu[i].score,stu[i].name);
    }
    return 0;
}

一个更加简介的快速排序-C语言实现

#include <stdio.h>

// 需排序的数据类型
typedef	float	TYPE;

/**
 * 快速排序
 * @Author   CofCai
 * @DateTime 2020-08-14T18:19:48+0800
 * @param    q                        排序对象
 * @param    l                        起点
 * @param    r                        终点
 */
void quickSort(TYPE q[], int l, int r)
{
	if (l >= r)
	{
		return;
	}

	int i = l - 1;
	int j = r + 1;
	TYPE x = q[l], tmp;
	while(i < j)
	{
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		if (i < j)
		{
			// 对于整型数，可以采用下面异或的方式交换两个值
			// q[i] = q[i]^q[j];
			// q[j] = q[i]^q[j];
			// q[i] = q[i]^q[j];
			// 
			// 上面交换两个变量的值的方式不是很通用
			tmp = q[i];
			q[i] = q[j];
			q[j] = tmp;

		}
		else
		{
			break;
		}
	}
	quickSort(q, l, j);
	quickSort(q, j + 1, r);
}

/**
 * 主函数
 * @Author   CofCai
 * @DateTime 2020-08-14T18:37:59+0800
 * @param    argc                     [description]
 * @param    argv                     [description]
 * @return                            [description]
 */
int main(int argc, char const *argv[])
{
	TYPE x[] = {9, 4, 10, 5, 34, 10, 2, 0, 38};
	int i, len = sizeof(x)/sizeof(int);

	printf("before sort\r\n");
	for (i = 0; i < len; ++i)
	{
		printf("%.2f\t", x[i]);
	}

	quickSort(x, 0, len-1);

	printf("\r\nafter sort\r\n");
	for (i = 0; i < len; ++i)
	{
		printf("%.2f\t", x[i]);
	}
	return 0;
}