快速排序法详解

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。大概算法是先找到某一元素的确切位置，再把该元素前后分成两半，没找到就移动，找到就赋值！具体做法是先移H，左边找到比val大的就赋值，右边找到比它小的就赋值！L和H赋值(L指向第一个元素，H指向最后一个元素，val存放第一个元素的值)。一旦赋值完就不移动！L和H重合了就不需要找了。只要记住一点就行了：左边找比关键字(val)大的就赋值(没找到就向右移)，右边找比关键字(val)小的就赋值(没找到就向左移)。 然后利用递归的思想（排序依次后，对关键字两边执行的操作是一样的）。

举例说明

49 38 65 97 76 13 27 49] //初始关键字
[27 38 13] 49 [76 97 65 49] //第1次划分完成之后，对应递归树第2层
[13] 27 [38] 49 [49 65] 76 [97] //对上一层各无序区划分完成后，对应递归树第3层
13 27 38 49 49 [65] 76 97 //对上一层各无序区划分完成后，对应递归树第4层
13 27 38 49 49 65 76 97 //最后的排序结果

实例代码

#include<stdio.h>
#include<conio.h>
void QuickSort(int *,int,int,int);
int FindPos(int *,int,int);
int num=0;//num用来保存排序进行的趟数
int main()
{
	int arr[]={49,38,65,97,76,13,27,49};
	int i;
	int n=sizeof(arr)/sizeof(int);//用n存放数组长度
	printf("***************** 快速排序算法 ******************\n\n");
	QuickSort(arr,0,n-1,n);//第二个参数表示第一个元素的下标，第三个参数表示最后一个元素的下标
	printf("\n------------- 总共进行了 %d 趟排序！-----------\n",num);
	printf("快速排序后的元素为：");
    for(i=0;i<n;++i)
		printf("%d  ",arr[i]);
	getch();//暂停程序，等待用户输入任意键退出程序
	return 0;
}
/*进行快速排序，确定第一个元素的确切位置，并将元素分成两半，左边一半和右边一半算法相同，*/
void QuickSort(int *a,int low,int high,int n)
{
	int pos=0;
	int i;
	if(low<high)
	{
		pos=FindPos(a,low,high);//确定元素的确切位置
		printf("第%d趟排序后的元素：",++num);
		for(i=0;i<n;++i)
			printf("%d  ",a[i]);
		printf("\n");
		QuickSort(a,low,pos-1,n);//前一半进行排序 
		QuickSort(a,pos+1,high,n);//后一半进行排序
	}
}
int FindPos(int *a,int low,int high)
{
	int val=a[low];//val作为关键字
	while(low<high)//每趟排序都从右边开始
	{
		while(low<high&&a[high]>=val)
			--high;
		a[low]=a[high];
		while(low<high&&a[low]<=val)
			++low;
		a[high]=a[low];
	}//终止while循环之后low和high的值一定是相等的
	a[low]=val;
	return low;
}

运行结果：

注意：

排序算法有3个衡量标准：时间复杂度，空间复杂度，稳定性。稳定性就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。比如甲(60)、乙、丙(60)排完序后甲还是在前面就说明这种排序算法稳定，但从运行结果可以看到第3趟和第四趟结果是一样的，这说明快速排序是一种不稳定的排序算法。

结束语

数据结构的学习暂时告一段落，有关数据结构还有很多东西要去学，毕竟数据结构是我们如何存储数据及它们之间的关系(重点) 的一个有力武器，数据结构为我们研究线性和非线性(因为我们的内存是线性一维的，所以通常把非线性结构转化为线性结构来进行存储)问题提供了方便。 明天开始学习算法!