基本思想：用选取的初始值（一般是第一个）将待排序序列分为小于初始值和大于初始值的两部分，然后重复此操作，最终到排序完成。该算法是一个不稳定的算法（如果待排序序列中存在相同的元素，经过排序后他们的相对位置不发生改变那么这个算法就是稳定的排序算法）
空间复杂度最坏为O(n),平均
时间复杂度最坏为O(n2),最好为
Java实现：
public static int[] quickSort(int[] n, int low, int high) { int lowMark = low, highMark = high; int record; if (low < high) { //记录值 record = n[low]; while (lowMark != highMark) { //高位指针偏移 while (lowMark < highMark && n[highMark] >= record) { highMark--; } //交换元素 n[lowMark] = n[highMark]; //低位指针偏移 while (lowMark < highMark && n[lowMark] <= record) { lowMark++; } //交换元素 n[highMark] = n[lowMark]; } //将记录值写到最后低位指针的位置 n[lowMark] = record; //两边分别进行排序操作 quickSort(n, low, lowMark - 1); quickSort(n, lowMark + 1, high); } return n; }
|
