基本思路:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
- static void quicksort(int n[], int left, int right) {
- int dp;
- if (left < right) {
- dp = partition(n, left, right);
- quicksort(n, left, dp - 1);
- quicksort(n, dp + 1, right);
- }
- }
-
- static int partition(int n[], int left, int right) {
- int pivot = n[left];
- while (left < right) {
- while (left < right && n[right] >= pivot)
- right--;
- if (left < right)
- n[left++] = n[right];
- while (left < right && n[left] <= pivot)
- left++;
- if (left < right)
- n[right--] = n[left];
- }
- n[left] = pivot;
- return left;
- }
复制代码 |
|