快速排序-java实现

快速排序是目前现有的最优时间复杂度的排序算法，核心思想是选择一个数作为序列的基准数，将比它大的数放到右边，比它小的数放到它的左边。那么在一次循环之后，这个数的左边都比它小，右边都比它大。所以这个数对于最终结果来说，它已经放在它应该在的位置。因而我们只需要通过递归的思想对基准数左右进行相同的操作即可。所以我们得到如下代码：

/** * 快速排序启动器 * @param a * @param left * @param right */ public static void quickSort(int[] a, int left, int right){ if(left < right){ int middle = getMiddle(a, left, right); quickSort(a, left, middle-1); quickSort(a, middle+1, right); } } /** * 调整并且获得中间值的方法 * @param a * @param left * @param right * @return */ private static int getMiddle(int[] a, int left, int right) { int temp = a[left]; //此处还可以进行优化 while(left < right){ while(left < right && a[right] >= temp){ right--; } a[left] = a[right]; while(left < right && a[left] <= temp){ left++; } a[right] = temp; } return left; }

其中如下方法，是以一个数为基准，将比它大的数放到它的右边，比它小的数放到它的左边，并且返回基准数位置的算法。

int getMiddle(int[] a, int left, int right)

最终执行结果：

public static void main(String[] args) { int[] a = new int[]{3,1,5,6,4,2,5}; quickSort(a,0,6); for(int i = 0;i<a.length;i++){ System.out.print(" " + a[i]); } }

代码测试无误，需要的同学可以拷贝。