算法步骤：
1：从数列中挑选一个元素，称为“基准”，
2：重新排序数列，所有元素比基准小的值摆放在基准前，所有元素比基准大的值摆放在基准后，（相同的数可以任意一边）在这个分区退出之后，该基准处于分区的中间位置。这个称为分区操作
3:递归的把小于基准元素的子数列和大于基准元素的自数列进行排序
intpartition(int*arr,intlow,inthigh){
intprivot = arr[high];
inti = low - 1;
intj,tmp;
for(j = low; j
if(arr[j]
tmp = arr[++i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
tmp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = tmp;
returni + 1;
}
voidquick_sort(int*arr,intlow,inthigh){
if(low
intmid =partition(arr, low, high);
quick_sort(arr,low,mid-1);
quick_sort(arr,mid + 1,high);
}
}
intmain(intargc,constchar* argv[]) {
intarr[10] = {1,2,5,3,6,8,7,23,15};
quick_sort(arr, 0, 9);
inti;
for(i = 0; i < 10; ++i) {
printf("%d ",arr[i]);
}
return0;
}
算法复杂度：
最坏情况下的开拍时间复杂度
最坏的情况发生在划分过程中产生的两个区域分别包含一个n-1和一个0元素的时候，即假设算法每一次递归调用过程中都出现了，这种划分不对称，那么划分的代价为o(n)，因为对一个大小为0的数组递归调用后，返回T（0）=O(1)，估算法的运行时间可以递归表示为：
T（n）= T(n-1) + T(0) +O(n) = T(n-1)+O(n).
可以证明为T(n) = O(n^2).
因此，若在算法的每一层递归上，划分都是最大不对称的话，算法的时间复杂度为O(n^2)
最快情况下开拍时间复杂度：
最快情况下，及Partition可能做的最平衡的划分中，得到的每一个子问题都不能大于n/2。因为其中一个子问题的大小为|n/2|。另一个的子问题的大小为|-n/2|-1
在这种情况下，快速排序的速度要快的多
T(n)<2T(n/2)+O(n),可以证得，T(n) = O(nlgn)
