快速排序法

算法步骤：

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)