快速排序思路总结以及算法性能分析

（一）思路：

懒比一个，电脑画图实在是费事，还说不清楚，直接在纸上写了思路：

思路

我这里再描述下吧，最开始已第一个数作为“枢轴”，我们之后的操作最终是为了使该“枢轴”到达一个确定的位置，前面的数都比它小，后面的数都比它大。
一个枢轴确定后，以它为分界点，递归继续它的前后序列。

（二）代码：

#include <stdio.h>
void QuickSort(int* a,int low,int high)
{
    int temp;
    int i=low;int j=high;
    if(low<high)
    {
        temp=a[low];
        while(i<j)
        {
            while(i<j&&a[j]>=temp) --j;//z从右往左找到一个比temp小的值的下标
            if(i<j)
            {
                a[i]=a[j];
                ++i;
            }
            while(i<j&&a[i]<temp) ++i;
            if(i<j)
            {
                a[j]=a[i];
                --j;
            }
        }
        //循环结束,i=j
        a[i]=temp;
        //至此，temp右边都是小于它的数，左边都是大于它的数，递归此过程
        QuickSort(a,low,i-1);
        QuickSort(a,i+1,high);
    }
}
int main(){
    int arr[9]={1,3,4,1,9,23,4,4,6};
    QuickSort(arr,0,9);
    for(int i=0;i<9;i++)
    {
        printf("%d ",arr[i]);
    }
}

运行结果

（三）算法及性能分析：

快排的效率与它序列最初的状态相关，初始状态越接近无序，该算法的效率最高：O(nlog2n)。
最坏情况O(n2)；平均情况时间复杂度为O(nlog2n),本算法事递归实现的，需要栈的辅助，空间复杂度为O(log2n)。

结语：就这样，水平有限，有错误或者描述不正确的，欢迎大家指正。