快速排序及Java实现

一 快速排序算法 快速排序由于排序效率在同为 O(N*logN)的几种排序方法中效率较高，因此经常被采用。 步骤 定基准——首先随机选择一个元素最为基准划分区——所有比基准小的元素置于基准左侧，比基准大的元素置于右侧递归调用——递归地调用此切分过程 二 代码实现 public void quickSort(int[] a, int left, int right) { if (left < right) { int i = arraySort(a, left, right); // 找基准 quickSort(a, left, i - 1); // 对左边递归排序 quickSort(a, i + 1, right); // 对右边递归排序 } } public int arraySort(int[] a, int left, int right) { int i = left; int j = right; int num = a[left]; while (i < j) { while (i < j && a[j] > num){ j--; } if (i < j) { a[i++] = a[j]; } while (i < j && a[i] < num) { i++; } if (i < j) { a[j--] = a[i]; } } a[i] = num; return i; }

代码优化

public void quickSort(int[] a, int low, int heigh) { if(low >= heigh) { return; } int left = low; int right = heigh; int num = a[low]; while(left < right) { while(left < right && a[right] >= num) { right--; } if (left < right) a[left++] = a[right]; while(left < right && a[left] <= num) { left++; } if (left < right) a[right--] = a[left]; } a[left] = num; quickSort(a, low, left - 1); quickSort(a, left + 1, heigh); }