三大改进策略优化快速排序算法
最编程
2024-02-22 13:09:28
...
前言
本文主要是介绍关于快速排序的三种优化思路,所以是基于读者已经掌握快速排序算法思想以及最基本的实现的前提,遂有关于快速排序原理方面,这里就不多赘述了。
下面是快速排序最简单的实现版本,即每次选取待排序序列中最左侧的元素作为枢纽元。
package SortPractice;
import java.util.Random;
public class QuickSortTest {
// 辅助函数,用来交换数组中两个位置上的元素
private static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 快速排序外部入口
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr,int l,int r) {
if (l >= r) {
return;
}
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
private static int partition(int[] arr,int l,int r) {
int val = arr[l];
int j = l;
for(int i = l + 1;i <= r; i++) {
if (arr[i] < val) {
swap(arr, i, ++j);
}
}
swap(arr, l, j);
return j;
}
}
优化一:结合插入排序
插入排序有两个优点,如下:
- 在数组几乎有序的情况下,插入排序效率极高!考虑一种极端情况,在数组完全有序的情况下,插入排序的时间复杂度将是 O(n)!
- 在数据量较小的时候,插入排序的效率很高!
对于这两个优点,本文简单的解释一下,首先给出插入排序的实现,如下
// 对于数组arr,从下标 l 开始到 r 部分执行插入排序
public static void insertSort(int[] arr,int l,int r) {
for(int i = l + 1; i <= r; i++) {
int val = arr[i];
int j;
for(j = i; j > l && arr[j - 1] > val; j--) {
arr[j] = arr[j - 1];
}
arr[j] = val;
}
上一篇: 快速排序(QuickSort):基础版本实操与简易优化指南
下一篇: 几种改进快速排序的方法
推荐阅读
-
三大改进策略优化快速排序算法
-
如何快速编写与优化快速排序算法的代码实例
-
MAX_LEN) {
int pivot = partition(arr, left, right);
quicksort_optimized(arr, left, pivot - 1);
quicksort_optimized(arr, pivot + 1, right);
} else {
// 使用插入排序处理小数组
}
}
```
- 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如:
原序列: 1 4 6 7 6 6 7 6 8 6
- 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6
- 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6
- 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7
- 下次划分得到的子序列:1 4 和 7 8 7
通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。">
改进版快速排序:针对部分有序列的策略与优化技巧" - 随机选枢轴:当数据部分有序时,传统快速排序通过固定枢轴可能导致效率低下。为此,我们采用随机选取枢轴的方法,代码如下: ```c int SelectPivotRandom(int arr[], int low, int high) { srand(time(0)); int pivotPos = (rand() % (high - low)) + low; swap(arr[pivotPos], arr[low]); return arr[low]; } ``` - 优化小数组交换:针对小且部分有序的数组,快速排序不如插入排序高效。因此,当待排序序列长度小于等于10时,我们会切换至插入排序: ```c #define MAX_LEN 10 void quicksort_optimized(int *arr, int left, int right) { int length = right - left; if (length > MAX_LEN) { int pivot = partition(arr, left, right); quicksort_optimized(arr, left, pivot - 1); quicksort_optimized(arr, pivot + 1, right); } else { // 使用插入排序处理小数组 } } ``` - 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如: 原序列: 1 4 6 7 6 6 7 6 8 6 - 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6 - 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6 - 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7 - 下次划分得到的子序列:1 4 和 7 8 7 通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。
-
改进版快速排序:随机化快速排序算法
-
快速排序方法及其改进策略
-
玩转数据结构:快速排序的高效改进策略
-
深入探索Python编程:优化版快速排序算法详解
-
改进版快速排序(quicksort)算法技巧
-
快速排序方法及其改进策略
-
准备攻克数学建模难题10:利用粒子群算法改进BP神经网络的优化策略