黑马程序员技术交流社区

标题: 快速排序 [打印本页]
作者: Mayer    时间: 2016-1-29 09:43
标题: 快速排序
基本思路：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
  1. static void quicksort(int n[], int left, int right) {
  2.         int dp;
  3.         if (left < right) {
  4.             dp = partition(n, left, right);
  5.             quicksort(n, left, dp - 1);
  6.             quicksort(n, dp + 1, right);
  7.         }
  8.     }

  10.     static int partition(int n[], int left, int right) {
  11.         int pivot = n[left];
  12.         while (left < right) {
  13.             while (left < right && n[right] >= pivot)
  14.                 right--;
  15.             if (left < right)
  16.                 n[left++] = n[right];
  17.             while (left < right && n[left] <= pivot)
  18.                 left++;
  19.             if (left < right)
  20.                 n[right--] = n[left];
  21.         }
  22.         n[left] = pivot;
  23.         return left;
  24.     }
复制代码
作者: 西贝    时间: 2016-1-29 12:36
没有冒泡和插入排序好理解，看的脑袋都大了



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2