快速排序的平均时间复杂度是O(nlogn),最坏情况下为O(n^2)。
法一：
原始数据如上，并且设置两个指针，以及一个基准pivot = 4（这里采用首元素为基准，基准可以是随机一个元素）。
在第一次循环中，从right指针开始，让指针指向的元素与基准元素比较，指针指向元素大于等于基准元素时，指针向左移动一位；否则，指针right停止移动，切换到left指针。left指针指向的元素如果小于等于基准元素，指针向右移动，否则指针停止移动，让left指针指向的元素与right指针指向的元素进行交换。当left与right指向同一个位置时，将该与元素与基准元素交换位置。
在上面数列中1<4，所以right指针停止移动，切换到left指针，然后进行下一步比较，4=4，所以left指针向右移动，7>4,所以将left指针停止移动，并且将left和right指针指向的元素交换。接下来继续进行下一轮的循环。流程大致如下：
代码实现如下：
public static void quickSort(int[] arr,int left,int right){ int i,j,pivot; //递归结束条件 if(left>=right){ return; } i=left; //左指针 j=right; //右指针 //pivot就是基准位 pivot = arr[left]; while (i<j) { //先看右边，依次往左递减 while (pivot<=arr[j]&&i<j) { j--; } //再看左边，依次往右递增 while (pivot>=arr[i]&&i<j) { i++; } //如果满足条件则交换 if (i<j) { int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } //最后将基准为与i和j相等位置的数字交换 arr[left] = arr[i]; arr[i] = pivot; //递归调用左半数组 quickSort(arr, left, j-1); //递归调用右半数组 quickSort(arr, j+1, right); }
法二：
选择第一个为基准（需要将其先赋值给临时变量，方便覆盖赋值于最终赋值），同样的从right下标开始，如果其下标的值大于基准时，right下标向左移动，反之将right下标对应的值覆盖left下标的值；然后left下标对应的值小于等于基准时，left下标向右移动，反之将left下标对应值覆盖right的值。直到left下标与right下标相等，将将基准赋值到left或者right下标（此时基准元素便不会发生改变），直到最终规模为1，也就是全部有序了。
由于数据特殊，一次居然就有序了，具体就是重复上面的操作。
/** * 划分函数）（每进行一次就会确定一个位置） * @param arr * @param left * @param right * @return */ public static int parition(int[] arr,int left,int right){ int temp = arr[left];//基准 while (left<right){ // 从右想左寻找 while (arr[right] > temp && left<right){ right--; } // 退出上面的循环说明该数比基准小，交换位置 arr[left] = arr[right]; // 从左向右寻找 while (arr[left] <= temp && left<right){ left++; } // 退出上面的循环说明该数比基准大，交换位置 arr[right] = arr[left]; } // 说明i==j;本轮交换结束 arr[left] = temp; return left; } /** * 递归调用，进行排序 * @param arr * @param left * @param right */ public static void qucikSort(int[] arr,int left,int right){ if(left < right){ int pos = parition(arr,left,right); //左边排序 qucikSort(arr,left,pos-1); qucikSort(arr,pos+1,right); } }
将上述递归操作变成非递归：
/** * 非递归 * @param arr * @param left * @param right */ public static void niceQucikSort(int[] arr,int left,int right){ Queue<Integer> queue = new LinkedList<>(); queue.offer(left); queue.offer(right); while (!queue.isEmpty()) { left = queue.poll(); right = queue.poll(); int pos = parition(arr, left, right); if (left < pos - 1) { queue.offer(left); queue.offer(pos - 1); } if (pos + 1 < right) { queue.offer(pos + 1); queue.offer(right); } } }
每次都是存入下标值，通过调用划分函数，来寻找每个基准的位置。
优化：
当数据越有序，并且选取的基准不恰当，时间复杂度就会变成O(n^2)。
采用随机坐标值作为基准：
/** * 随机下标划分 * @param arr * @param left * @param right * @return */ public static int RandomPartition(int[] arr,int left,int right){ Random random = new Random(); int index = random.nextInt(right - left+1) + left; // 将随机坐标换到最左边 int temp = arr[left]; arr[left] = arr[index]; arr[index] = temp; return parition(arr,left,right); }
另一种是三者取中。