- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(n2)
- 稳定性：不稳定
python
# coding:utf-8
def quick_sort(alist, first, last):
"""快速排序"""
if first > last:
return
mid_value = alist[first]
low = first
high = last
while high > low:
while high > low and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
while high > low and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
alist[low] = mid_value
quick_sort(alist, first, low - 1)
quick_sort(alist, low + 1, last)
if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
quick_sort(li, 0, len(li)-1)
print(li)
objective-c
/**
快速排序
*/
- (void)quick_sort:(NSMutableArray *)arr first:(NSInteger)first last:(NSInteger)last
{
if (first > last) {
return;
}
NSInteger low = first;
NSInteger high = last;
NSNumber *mid_value = arr[first];
while (high > low) {
while (high > low && arr[high] >= mid_value) {
high--;
}
arr[low] = arr[high];
while (high > low && arr[low] < mid_value) {
low++;
}
arr[high] = arr[low];
}
arr[high] = mid_value;
[self quick_sort:arr first:first last:high - 1];
[self quick_sort:arr first:high + 1 last:last];
}
示例图
