快速排序（C语言版）

关于快速排序，其实它跟冒泡排序一样，也是一种交换排序算法，但是他比冒泡排序快速的多，减少了比较次数和移动交换次数，是冒泡排序的升级。

 

下面先讲一些必要的定义吧：

 

快速排序的基本思想是： 通过一趟排序将带排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列的目的。

 

枢轴：通过Partition函数，先选取当中的一个关键字，然后想尽办法把它放到一个i额位置，使得他左边的值都比它小，右边的值都比它大，我们将这样的关键字称为枢轴。

 

直接上代码：

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

#define TRUE 1
#define FALSE 0
#define MAXSIZE 9
#define  random(x) (rand()%x)
 
typedef int ElemType, Status;	

typedef struct {	//定义一个线性表的顺序存储结构 
	ElemType data[MAXSIZE];
	int length;
}SqList;

/*将列表中的数据进行展示*/
void display(SqList	L) {
	int i;
	for(i = 0; i <L.length; i++) {
		printf("%d ", L.data[i]);
	}
	printf("\n");
}

/*将顺序表L中的i和j两个位置进行交换*/
void swap(SqList *L, int i, int j){
	ElemType temp = L->data[i];
	L->data[i] = L->data[j];
	L->data[j] = temp;
} 

/*
	交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置
	此时在它之前（后）的记录均不大于（小） 它 
*/
int partition(SqList *L, int low, int high) {
	int pivotKey = L->data[low];	//用字表的第一个记录作枢轴记录 
	
	while(low < high) {	//从表的两端交替向中间扫描 
		
		while((low < high) && L->data[high] >= pivotKey) {	//一定要记得=号，否则在一些情况下会造成死循环
			high--;
		}
//		printf("high : %d ", high);
		swap(L, low, high);	//将比枢轴记录小的记录交换到低端 
		
		while((low < high) && L->data[low] <= pivotKey) {	//一定要记得=号，否则在一些情况下会造成死循环 
			low++;
		}
//		printf("low : %d \n", low);
		swap(L, low, high);//将比枢轴记录大的记录交换到高端 
	}	
	return low;	//返回枢轴所在的位置 

} 

/*
	对顺序表L中的子序列L->data[low..high]作快速排序
	因为该方法需要递归调用，所以必须外封装成一个函数 
*/
void qSort(SqList *L, int low, int high) {
	int pivot;	//枢轴值 
	
	if(low < high) {
		pivot = partition(L, low, high);	//将L->data[low,,high]一分为二 
		//printf("pivot : %d \n", pivot);
		qSort(L, low, pivot - 1);	//将低子表进行递归排序 
		qSort(L, pivot + 1, high);	//将高子表进行递归排序
	} 
}

/*
	快速排序 
*/
void quickSort(SqList *L) {
	qSort(L, 0, L->length - 1);	
}

int main() {
    srand((int)time(NULL));	//用当前的时间作为随机数种子，这样就能保证每次运行时都能取到不同的随机数序列
    
	SqList s;
	int i = 0;
	s.length = 0;
	for(i; i < MAXSIZE; i++) {	//创建一个原始栈并为其赋值 
		s.data[i] = random(MAXSIZE);
		s.length++;	
	}
	printf("数组的长度 ： %d\n原始数组为 : ", s.length);
	display(s); 
	quickSort(&s);
	printf("经过排序后 ：");
	display(s); 
}

 

由于我的测试数据是随机生成的，下面只列出运行结果之一：

数组的长度 ： 9
原始数组为 : 0 5 0 1 3 5 7 1 7
经过排序后 ：0 0 1 1 3 5 5 7 7
请按任意键继续. . .