【数据结构与算法】—— 快速排序数据结构和算法快速排序

1.快速排序的定义
【【数据结构与算法】—— 快速排序】快速排序是一种效率很高的排序算法，基本思想是选定一个基准值，然后遍历数组，将小于基准值的元素放在数组左边，大于基准值的元素放在数组右边。然后对数组左边和数组右边的元素重复该步骤。如下是个简单的示例：
原数组：[3,2,5,4,1] 选择pivot为3，pivotIndex = 0
第一次将大于和小于3的元素放在左右后数组变成[2,1,3,4,5].即左边为小于3的元素，右边为大于3的元素。
然后对左边数组和右边数组分别执行如上步骤，即数组[2,1]和数组[4,5]。
同样选择数组第一个元素2和4作为pivot。
经过上述步骤后数组变成[1,2]和[4,5]。最后整个数组变成[1,2,3,4,5]
2. 时间复杂度
平均时间复杂度：\( O(nlogn) \)
最坏时间复杂度：\( O(n^2) \)
如数组[1,2,3,4,5]。我们每次选择第一个元素作为pivot，那么整个排序步骤大概是如下过程
[1,2,3,4,5]
[],[2,3,4,5]
[],[3,4,5]
[],[4,5]
[],[5]
即每次左边的元素都是空的。这样5个元素每次就要递归对子数组排序5次。而每次要遍历整个数组。所以时间复杂度为 \( O(n^2) \)
3. Java实现

public void quickSort(int[] arr) { quickSortInternal(arr, 0, arr.length - 1); }private void quickSortInternal(int[] arr, int low, int high) { int left = low, right = high; while (left < right) { while (arr[left] < arr[low]) { left++; } while (arr[right] > arr[low]) { right--; } swap(arr, left, right); } // then the low element is lower than the element in pivotIdx // the high element is higher than the element in pivotIdx // repeat the above steps in left arr and right arr if low < high if (low < high) { quickSortInternal(arr, low, low - 1); quickSortInternal(arr, low + 1, high); } }private void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }

4. 数据结构系列代码地址
Github：https://github.com/bennetty74...