数据结构与算法分析之快速排序(Quick Sort)学习

快速排序(英语:Quick Sort),又称划分交换排序(Partition-Exchange Sort),简称快排,一种排序算法,最早由东尼·霍尔提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序算法描述:
1、从数列中挑出一个元素,称为”基准”(pivot),
2、重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3、递归把小于基准值元素的子数列和大于基准值元素的子数列排序。

一、 快速排序源码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM 10

// 两个数交换函数
void swap(int *p, int *q)
{
	int temp = *p;
	*p = *q;
	*q = temp;
}

// 快速排序函数实现
void quick_sort(int a[], int left, int right)
{
	if(left >= right) return;
	
	int mid = left;
	for(int i=left+1; i<=right; i++)
	{
		if(a[i] < a[left]) swap(&a[i], &a[++mid]);
	}
	swap(&a[left], &a[mid]);
	
	quick_sort(a, left, mid-1);
	quick_sort(a, mid+1, right);
}

int main(void)
{
	int array[NUM];
	
	srand((unsigned int)time(NULL));
	
	// 给数组赋随机值
	for(int i=0; i<NUM; i++)
	{
		array[i] = rand()%100;
	}
	
	// 打印排序前数组
	for(int i=0; i<NUM; i++)
	{
		printf("%5d", array[i]);
	}
	
	printf("\n");
	
	// 快速排序
	quick_sort(array, 0, NUM-1);
	
	// 打印排序后数组
	for(int i=0; i<NUM; i++)
	{
		printf("%5d", array[i]);
	}
	
	printf("\n");
	
	return 0;
}

二、 运行结果

[ycxie@fedora Workspace]$ gcc quick_sort.c -o quick_sort -Wall
[ycxie@fedora Workspace]$ ./quick_sort
   22   72   92    0   37   75    5   95   40   41
    0    5   22   37   40   41   72   75   92   95
[ycxie@fedora Workspace]$ ./quick_sort
    7   31   39   47   28   81   41   85    6   67
    6    7   28   31   39   41   47   67   81   85
[ycxie@fedora Workspace]$ ./quick_sort
   16   84   12   74   53   16   33   12   99   68
   12   12   16   16   33   53   68   74   84   99
[ycxie@fedora Workspace]$ ./quick_sort
   92   48   73   84   42   41   40   11   68   62
   11   40   41   42   48   62   68   73   84   92
[ycxie@fedora Workspace]$ ./quick_sort
   92   48   73   84   42   41   40   11   68   62
   11   40   41   42   48   62   68   73   84   92

Leave a Reply

Your email address will not be published. Required fields are marked *