算法原理
快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码实现
#include <stdio.h>
void print_arr(int arr[], int len);
void quick_sort(int arr[], int left, int right);
int main(int argc, const char * argv[]) {
int arr[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
print_arr(arr, 10);
quick_sort(arr, 0, 9);
print_arr(arr, 10);
return 0;
}
void quick_sort(int arr[], int left, int right) {
if (left < right) {
int i = left, j = right, current = arr[left];
while (i < j) {
while (i < j && arr[j] > current)
j--;
if (i < j)
arr[i++] = arr[j];
while (i < j && arr[i] < current)
i++;
if (i < j)
arr[j--] = arr[i];
}
arr[i] = current;
quick_sort(arr, left, i-1);
quick_sort(arr, i+1, right);
}
}
void print_arr(int arr[], int len) {
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
