快速排序(java)

快速排序(java)

这里写目录标题

• 快速排序
• • 快速排序
  • • 1）把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部 分：左侧<划分值、中间==划分值、右侧>划分值
    • 2）对左侧范围和右侧范围，递归执行
  • 代码
  • • 代码做出的改动
  • 分析
  • • 1）划分值越靠近两侧，复杂度越高；划分值越靠近中间，复杂度越低
    • 2）可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为O(N^2)

快速排序 快速排序 1）把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部 分：左侧<划分值、中间==划分值、右侧>划分值 2）对左侧范围和右侧范围，递归执行 代码

public class quicklysort {
	public static void quickSort(int []arr) {
		if(arr == null||arr.length < 2) {
			return ;
		}
		quickSort(arr,0,arr.length - 1);
	}
	public static void quickSort(int []arr, int l,int r) {
		if(l arr[r]) {
				swap(arr, --more, l);
			} else {
				l++;
			}
		}
		swap(arr, more, r);
		return new int[] { less + 1, more };
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

代码做出的改动

• 递归行为，注意先partition：
• 然后返回的是边界的前面一个值，注意转化成边界：quickSort(arr,l,p[0]-1);
  quickSort(arr,p[1]+1,r);
• 在partition的过程中，要加上一个swap，将more与r进行转化。因为r还没有转化

分析 1）划分值越靠近两侧，复杂度越高；划分值越靠近中间，复杂度越低 2）可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为O(N^2)

例如123456789，每一次的结果都在端点，导致每一次都遍历N遍。成为了O（N^2）。