[数据结构与算法]快速排序！

? 快速排序是基于分治法的思想，是个人比较喜欢的排序算法之一了?！

1.首先最重要的是对数组进行一轮划分。

int partition1(int *A,int low,int high)
{
    int pivot=A[low];//将第一个元素设置为枢轴
    while(low<high){
        while(low<high&&A[high]>=pivot) --high;
        A[low]=A[high];
        while(low<high&&A[low]<=pivot) ++low;
        A[high]=A[low];
    }
    A[low]=pivot;
    return low;
}

2.递归调用进行排序

void QuickSort(int *A,int low,int high)
{
   if(low<high){
        int pivotpos=partition1(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);

     }
}

3.主函数调用下

int main()
{
    int arry[maxsize]={0};
	int num=0;
	int i=1;
	printf("please input sum:");//排序的数目
	scanf("%d",&num);
	printf("please input sequence:");//待排序列
	for(;i<=num;i++){
        scanf("%d",&arry[i]);
	}
	QuickSort(arry,1,num);
	printf("QuickSort Result:");
	i=1;
	while(i<=num)
		printf("%d ",arry[i++]);
	printf("\n");
	return 0;
}

?4.测试一下

测试序列数目：6

测试序列数字序列：10 5 9 44 32 19

结果如下：

?5.分析一下性能

? ? ? 快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。

? ? 理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。

? ? 最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。

? ? ?从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log2(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(log2n)。