原地快速排序

快速排序的原理

    快速排序的原理为根据数组中的某一个数据（代码中取数组中最后一位）将数组切分成比该数据大和比该数据小的两组， 再将两组数据同理进行切分， 直到切分至无法切分为止， 至此排序完成。

快速排序的时间复杂度为O(nlogn), 而原始的快速排序对空间占用较多， 我们这边采用游标的方式不再开拓新的分区， 而是在原始的数组中进行切分排序， 空间复杂度为O(1)， 因为没开拓新的分区空间， 也成为原地排序， 以下为相应代码

public static void main(String[] args) {Integer[] arr = new Integer[]{1,5,8,2,4,10,24,6,8,9};change(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}private static void change(Integer[] arr, Integer startIndex, Integer endIndex) {Integer patternKey = arr[endIndex];int cursor = startIndex;for (int i = startIndex; i <= endIndex; i++) {if (arr[i] < patternKey) {if (i == cursor) {cursor++;} else {swap(arr, i, cursor);cursor++;}}}swap(arr, endIndex, cursor);if (cursor - startIndex + 1 >= 2) {change(arr, startIndex, cursor - 1);}if (endIndex - cursor - 1 >= 1) {change(arr, cursor + 1, endIndex);}}private static void swap(Integer[] arr, Integer i, Integer j){Integer temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！