本文共 564 字,大约阅读时间需要 1 分钟。
算法思路:每次选择一个元素pivot作为枢轴,将比pivot大的元素放到他的右边,比pivot小的元素放到他的左边,从而确定了pivot的位置。将pivot左右两个子表进行同样的操作,循环递归,直至结束。
性能分析:
时间复杂度与划分是否对称有关,最坏O(n^2),最好、平均O(nlogn)
空间复杂度与递归调用深度有关,最好、平均O(logn),最坏O(n)
稳定性: 不稳定
注:快速排序是所有内部排序中算法性能最好的排序
int Partition(int arr[],int low,int high){ int pivot; pivot=arr[low]; while(lowlow&&arr[high]>=pivot) high--; arr[low]=arr[high]; while(low <=pivot) low++; arr[high]=arr[low]; } arr[low]=pivot; return low;}void QuickSort(int arr[],int low,int high){ if(low
转载地址:http://mpczb.baihongyu.com/