1. 快速排序
时间复杂度:平均复杂度为O(n·log n),最差情况下的复杂度为O(n2)
空间复杂度:平均复杂度为O(log n),最差情况下的复杂度为O(n)
1 package org.example.sort; 2 3 import java.util.List; 4 5 /** 6 * @description: 快速排序 7 **/ 8 9 public class QuickSort { 10 11 public static void sort(List<Integer> list) { 12 sort(list, 0, list.size() - 1); 13 } 14 15 private static void sort(List<Integer> list, int begin, int end) { 16 17 if (begin >= end) return; 18 19 int left = begin; 20 int right = end; 21 int midVal = list.get(left); 22 while (left < right) { 23 // 基准值是最左侧的值,所以可以认为左边已经遇到的不满足条件的值 24 // 因此循环从右侧开始 25 while (list.get(right) > midVal && left < right) { 26 right--; 27 } 28 // 找到第一个小于等于midVal的值,交换到左边 29 if (left < right) { 30 list.set(left, list.get(right)); 31 left++; 32 } 33 34 while (list.get(left) < midVal && left < right) { 35 left++; 36 } 37 // 找到第一个大于等于midVal的值,交换到右边 38 if (left < right) { 39 list.set(right, list.get(left)); 40 right--; 41 } 42 } 43 // 把midVal放到中间位置 44 list.set(left, midVal); 45 sort(list, begin, left - 1); 46 sort(list, left + 1, end); 47 } 48 }标签:sort,right,复杂度,list,midVal,排序,left From: https://www.cnblogs.com/simple-design/p/17234532.html