java排序算法一次跟你说明白 ~ 快速排序

中心思想

是由冒泡排序改进而来。在待排序的 n 个记录中任取一个记录（通常取之一个记录），把该记录放入适当位置后，数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录在这两部分的中间(称为该记录归为)。

代码实现

private int[] quickSort(int[] arr, int left, int right) { // System.out.println("left:"+ left +",right:"+ right) if (left < right) { int partitionIndex = partition(arr, left, right); // 递归调用,对分隔后的左边数组快速排序 quickSort(arr, left, partitionIndex - 1); // 递归调用,对分隔后的右边数组快速排序 quickSort(arr, partitionIndex + 1, right); } return arr; } private int partition(int[] arr, int left, int right) { // 设定基准值（pivot) int pivot = left; int index = pivot + 1; for (int i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index - 1; } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

时间复杂度

稳定性

由于每次都需要和中轴元素交换，因此原来的顺序可能被打乱。（多个相同的元素），所以说，快速排序是不稳定的！