手撕快速排序

1.思想1分治策略 原地排序。2选择一个基准元素pivot将数组分成两部分左边部分 基准右边部分 基准。3递归地对左右两部分进行同样的操作。2.算法步骤1选择基准如第一个、最后一个、或随机。2分区partition通过交换将元素放到基准两侧。3递归处理左右子数组。3.复杂度与特点1时间复杂度a平均时间复杂度O(nlogn)。b最坏情况下的时间复杂度数组已经正序或逆序排序并且基准元素选择的是队首或队尾O(n^2)。c最好情况下的时间复杂度O(nlogn)。2空间复杂度O(logn)递归栈。3快速排序是否稳定不稳定交换可能改变相等元素的相对顺序。4特点原地排序常数因子小实际应用中通常比归并排序快。附代码class QuickSort { public void quickSort(int[] nums, int left, int right) { if (left right) { return; } int pivotIndex partition(nums, left, right); quickSort(nums, left, pivotIndex); quickSort(nums, pivotIndex 1, right); } private int partition(int[] nums, int left, int right) { // 选择中间元素作为基准 int pivot nums[left (right - left) / 2]; int i left; int j right; while (true) { // 从左向右找第一个 pivot 的元素 while (nums[i] pivot) { i; } // 从右向左找第一个 pivot 的元素 while (nums[j] pivot) { j--; } // 如果指针相遇或交叉分区结束 // 此时j指向左半部分的结尾i指向右半部分的开头 // 所以是return j if (i j) { return j; } // 交换 swap(nums, i, j); i; j--; } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } }ACM模式import java.util.Scanner; class QuickSort { public void quickSort(int[] nums, int left, int right) { if (left right) { return; } int pivotIndex partition(nums, left, right); quickSort(nums, left, pivotIndex); quickSort(nums, pivotIndex 1, right); } private int partition(int[] nums, int left, int right) { // 选择中间元素作为基准 int pivot nums[left (right - left) / 2]; int i left; int j right; while (true) { // 从左向右找第一个 pivot 的元素 while (nums[i] pivot) { i; } // 从右向左找第一个 pivot 的元素 while (nums[j] pivot) { j--; } // 如果指针相遇或交叉分区结束 // 此时j指向左半部分的结尾i指向右半部分的开头 // 所以是return j if (i j) { return j; } // 交换 swap(nums, i, j); i; j--; } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n scanner.nextInt(); int[] nums new int[n]; for (int i 0; i n; i) { nums[i] scanner.nextInt(); } QuickSort quickSort new QuickSort(); quickSort.quickSort(nums, 0, n - 1); for (int i 0; i n; i) { System.out.print(nums[i]); if (i n - 1) { System.out.print( ); } } System.out.println(); scanner.close(); } }