网站运营费用,门户网站平台建设的经费,wordpress 扫码支付,用C语言做网站登录界面快速排序是一种非常高效的排序算法#xff0c;由英国计算机科学家托尼霍尔#xff08;Tony Hoare#xff09;在1960年代发明。它使用分治法#xff08;Divide and Conquer#xff09;策略来把一个序列分为较小的部分#xff0c;然后递归地排序这些部分。
快速排序的基本…快速排序是一种非常高效的排序算法由英国计算机科学家托尼·霍尔Tony Hoare在1960年代发明。它使用分治法Divide and Conquer策略来把一个序列分为较小的部分然后递归地排序这些部分。
快速排序的基本步骤
选择基准值Pivot Selection从序列中选择一个元素作为基准值。通常选择序列的第一个、最后一个或中间的元素也可以随机选择。分区操作Partitioning重新排列序列使得所有小于基准值的元素都位于基准值的左边所有大于基准值的元素都位于基准值的右边。完成这个操作后基准值就位于最终排序后的位置。递归排序子序列递归地对基准值左边和右边的子序列应用快速排序算法。
分区操作细节
设置两个指针 left 和 rightleft 指针从序列的起始位置开始right 指针从序列的结束位置开始。移动 right 指针直到找到一个小于或等于基准值的元素。移动 left 指针直到找到一个大于或等于基准值的元素。如果 left 指针在 right 指针的左边交换两个指针所指向的元素。重复上述步骤直到 left 和 right 指针相遇或交叉。当指针交叉时将基准值与 right 指针所指向的元素交换完成分区操作。
Java代码实现
下面是一个简单的快速排序算法的Java实现
public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low high) {// pi is partitioning index, arr[pi] is now at right placeint pi partition(arr, low, high);// Recursively sort elements before and after partitionquickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot arr[high]; // pivotint i (low - 1); // Index of smaller elementfor (int j low; j high; j) {// If current element is smaller than the pivotif (arr[j] pivot) {i;// swap arr[i] and arr[j]int temp arr[i];arr[i] arr[j];arr[j] temp;}}// swap arr[i1] and arr[high] (or pivot)int temp arr[i 1];arr[i 1] arr[high];arr[high] temp;return i 1;}// Function to print an arraypublic static void printArray(int[] arr) {for (int value : arr) {System.out.print(value );}System.out.println();}public static void main(String[] args) {int[] arr {10, 7, 8, 9, 1, 5};int n arr.length;quickSort(arr, 0, n - 1);System.out.println(Sorted array:);printArray(arr);}
}时间复杂度
最佳和平均情况O(n log n)最差情况O(n^2)当输入数组已经是排序好的或逆序的基准值每次都是最小或最大值。
空间复杂度
O(log n)由于递归调用栈的空间。
快速排序在实际应用中非常广泛尤其是在大规模数据集上因为它能够提供非常好的性能。然而在某些情况下例如数据已经接近排序的情况下快速排序的性能可能会退化这时可以考虑使用其他排序算法如堆排序或归并排序。
要优化快速排序算法我们可以采取几种不同的策略来提高其效率和稳定性。以下是一些常见的改进方法 三数取中法Median-of-three选择基准值 在选择基准值时使用数组的第一个元素、中间元素和最后一个元素中的中位数作为基准值这有助于避免最坏情况的发生特别是在数组已经部分排序的情况下。 插入排序小数组 对于小规模的子数组使用插入排序替换快速排序。插入排序在小数组上的性能通常优于快速排序因为它的常数因子较小。 尾递归优化 可以优化递归调用减少栈空间的使用。具体来说你可以先递归处理较大的子数组然后迭代处理较小的子数组或者使用循环结构替代递归。 非递归版本 使用显式栈来模拟递归调用这样可以避免系统调用栈的开销。
下面是使用三数取中法和插入排序小数组的优化版快速排序示例代码
public class OptimizedQuickSort {public static void quickSort(int[] arr, int low, int high) {while (low high) {// Partition and get the partition index.int pi partition(arr, low, high);// Recursively sort the left part, but only if its larger than the right.if (pi - low high - pi) {quickSort(arr, low, pi - 1);low pi 1;} else {quickSort(arr, pi 1, high);high pi - 1;}}}private static int partition(int[] arr, int low, int high) {// Median-of-three pivot selectionint mid (low high) / 2;if (arr[mid] arr[high]) {swap(arr, mid, high);}if (arr[low] arr[high]) {swap(arr, low, high);}if (arr[mid] arr[low]) {swap(arr, mid, low);}int pivot arr[low];int i low 1;int j high;while (true) {while (i j arr[i] pivot) {i;}while (i j arr[j] pivot) {j--;}if (i j) {swap(arr, i, j);} else {break;}}swap(arr, low, j);return j;}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void insertionSort(int[] arr, int low, int high) {for (int i low 1; i high; i) {int key arr[i];int j i - 1;while (j low arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}}public static void main(String[] args) {int[] arr {10, 7, 8, 9, 1, 5};int n arr.length;// Optimize: Use insertion sort for small subarraysfor (int i 0; i n; i 16) {insertionSort(arr, i, Math.min((i 15), (n - 1)));}quickSort(arr, 0, n - 1);System.out.println(Sorted array:);for (int value : arr) {System.out.print(value );}System.out.println();}
}在这个优化版本中我们使用了三数取中法来选择更合理的基准值并且对于小于16个元素的小数组使用插入排序进行排序。此外我们还通过循环结构代替递归来减少栈的使用。这些修改可以帮助提高快速排序在各种情况下的性能和稳定性。
尾递归优化
尾递归优化是指在递归函数中如果递归调用是函数执行的最后一个操作那么可以通过一些技巧将其转换为迭代从而避免栈溢出的风险和减少递归调用的开销。对于快速排序而言可以优先递归处理较小的子数组然后返回处理较大的子数组这样可以保证递归深度不会过大。
下面是一个利用尾递归优化的快速排序Java实现示例
public class TailRecursiveQuickSort {public static void quickSort(int[] arr, int low, int high) {while (low high) {// Partitioning indexint pi partition(arr, low, high);// Recursively sort elements before partition and after partitionif (pi - low high - pi) {// Sort the smaller part firstquickSort(arr, low, pi - 1);// Update the range for the larger partlow pi 1;} else {// Sort the larger part firstquickSort(arr, pi 1, high);// Update the range for the smaller parthigh pi - 1;}}}private static int partition(int[] arr, int low, int high) {int pivot arr[high];int i (low - 1); // index of smaller elementfor (int j low; j high; j) {// If current element is smaller than or equal to pivotif (arr[j] pivot) {i;// swap arr[i] and arr[j]int temp arr[i];arr[i] arr[j];arr[j] temp;}}// swap arr[i1] and arr[high] (or pivot)int temp arr[i 1];arr[i 1] arr[high];arr[high] temp;return i 1;}public static void main(String[] args) {int[] arr {10, 7, 8, 9, 1, 5};int n arr.length;quickSort(arr, 0, n - 1);System.out.println(Sorted array:);for (int value : arr) {System.out.print(value );}System.out.println();}
}在这个版本中quickSort 函数使用了一个循环来处理子数组的排序。在每次循环中它首先对当前的子数组进行分区操作然后根据左右两部分的大小决定先递归处理哪一部分。这样做可以确保每次递归调用之后剩余需要处理的子数组的大小总是比前一次小从而减少了递归的深度。
然而值得注意的是尽管这种优化减少了递归调用的次数但在最坏情况下如果每次分区都偏向一侧递归深度仍然可能较大。因此结合其他优化策略如三数取中法选择基准值可以进一步提高算法的稳定性和性能。
为了进一步提高快速排序的稳定性和性能可以结合多种优化策略。以下是几种常见的改进方法 三数取中法选择基准值选取第一个、中间的和最后一个元素中的中值作为基准值以减少最坏情况的发生。 插入排序小数组对于小规模的子数组使用插入排序。插入排序在小数组上的效率高于快速排序。 随机化基准值选择随机选择数组中的一个元素作为基准值可以避免最坏情况的发生尤其是当数组已部分排序时。 双路快速排序Dual-Pivot QuickSort同时使用两个基准值可以减少比较和交换的次数从而提高性能。 尾递归优化减少递归调用的深度使用循环结构替代递归。 并行化利用多核处理器的优势使用并行计算技术对子数组进行排序。
下面是一个结合了三数取中法、插入排序小数组和尾递归优化的快速排序Java实现
public class OptimizedQuickSort {private static final int INSERTION_SORT_THRESHOLD 16; // 阈值用于插入排序public static void quickSort(int[] arr, int low, int high) {while (low high) {// 使用三数取中法选择基准值int pivotIndex medianOfThree(arr, low, high);int pivot arr[pivotIndex];// 将基准值放到最后swap(arr, pivotIndex, high);// Partitioning indexint pi partition(arr, low, high);// Recursively sort elements before partition and after partitionif (pi - low high - pi) {// Sort the smaller part firstquickSort(arr, low, pi - 1);// Update the range for the larger partlow pi 1;} else {// Sort the larger part firstquickSort(arr, pi 1, high);// Update the range for the smaller parthigh pi - 1;}}}private static int medianOfThree(int[] arr, int low, int high) {int mid (low high) 1; // 使用无符号右移获得中间索引if (arr[mid] arr[high]) {swap(arr, mid, high);}if (arr[low] arr[high]) {swap(arr, low, high);}if (arr[mid] arr[low]) {swap(arr, mid, low);}return low; // 返回中位数的索引}private static int partition(int[] arr, int low, int high) {int pivot arr[high];int i low - 1;for (int j low; j high; j) {if (arr[j] pivot) {i;swap(arr, i, j);}}swap(arr, i 1, high);return i 1;}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void insertionSort(int[] arr, int low, int high) {for (int i low 1; i high; i) {int key arr[i];int j i - 1;while (j low arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}}public static void main(String[] args) {int[] arr {10, 7, 8, 9, 1, 5};int n arr.length;// 使用插入排序处理小数组for (int i 0; i n; i INSERTION_SORT_THRESHOLD) {insertionSort(arr, i, Math.min(i INSERTION_SORT_THRESHOLD - 1, n - 1));}// 使用快速排序处理大数组quickSort(arr, 0, n - 1);System.out.println(Sorted array:);for (int value : arr) {System.out.print(value );}System.out.println();}
}这个版本的快速排序算法结合了多种优化策略提高了排序的性能和稳定性。在实际应用中根据数据的特点和环境的限制还可以尝试其他的优化策略以达到最佳效果。例如对于大规模数据集可以考虑使用并行快速排序来充分利用多核处理器的能力。
在Java中利用并行流parallel streams或java.util.concurrent包中的工具可以实现并行快速排序。这里我将展示如何使用Fork/Join框架来实现并行快速排序。
Fork/Join框架是Java 7引入的一种并行编程模型它允许任务被分割成更小的任务然后并行执行。在快速排序中我们可以将大的数组分割成小的子数组并在不同的线程上并行地对它们进行排序。
下面是一个使用Fork/Join框架的并行快速排序实现
import java.util.Arrays;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;public class ParallelQuickSort {public static void main(String[] args) {int[] arr new int[1_000_000];// 初始化数组...for (int i 0; i arr.length; i) {arr[i] (int)(Math.random() * 1000);}long startTime System.currentTimeMillis();ForkJoinPool pool new ForkJoinPool();pool.invoke(new SortTask(arr, 0, arr.length - 1));long endTime System.currentTimeMillis();System.out.println(Sorting took (endTime - startTime) ms);// 检查排序是否正确boolean isSorted true;for (int i 1; i arr.length; i) {if (arr[i] arr[i - 1]) {isSorted false;break;}}System.out.println(Is sorted: isSorted);}static class SortTask extends RecursiveAction {private final int[] arr;private final int low;private final int high;public SortTask(int[] arr, int low, int high) {this.arr arr;this.low low;this.high high;}Overrideprotected void compute() {if (low high) {int pi partition(arr, low, high);invokeAll(new SortTask(arr, low, pi - 1), new SortTask(arr, pi 1, high));}}private int partition(int[] arr, int low, int high) {int pivot arr[high];int i (low - 1); // index of smaller elementfor (int j low; j high; j) {// If current element is smaller than or equal to pivotif (arr[j] pivot) {i;// swap arr[i] and arr[j]int temp arr[i];arr[i] arr[j];arr[j] temp;}}// swap arr[i1] and arr[high] (or pivot)int temp arr[i 1];arr[i 1] arr[high];arr[high] temp;return i 1;}}
}在上述代码中SortTask继承自RecursiveAction类这是Fork/Join框架中的一个抽象类用于表示一个可并行执行的任务。compute方法定义了任务的执行逻辑。当一个SortTask实例被创建并提交给ForkJoinPool时它会根据子任务的大小决定是继续分割任务还是直接执行。如果任务足够小它将直接进行排序如果任务足够大它将被分割成更小的子任务并在多个线程上并行执行。
这种方法特别适用于多核处理器因为它能有效利用所有可用的CPU核心。但是对于较小的数据集由于启动额外线程的开销传统的单线程排序可能会更快。因此在实际应用中你可能还需要调整任务分割的阈值以找到最适合特定硬件配置的平衡点。
优化后的非递归版本的快速排序算法通常使用显式栈来模拟递归调用的行为从而避免了递归调用带来的栈溢出风险以及函数调用的开销。下面是一个使用显式栈的非递归快速排序算法的Java实现
import java.util.ArrayDeque;
import java.util.Deque;public class NonRecursiveQuickSort {public static void quickSort(int[] arr) {DequeInteger stack new ArrayDeque();stack.push(0);stack.push(arr.length - 1);while (!stack.isEmpty()) {int high stack.pop();int low stack.pop();int pivotIndex partition(arr, low, high);if (pivotIndex - 1 low) {stack.push(low);stack.push(pivotIndex - 1);}if (pivotIndex 1 high) {stack.push(pivotIndex 1);stack.push(high);}}}private static int partition(int[] arr, int low, int high) {int pivot arr[high];int i low - 1;for (int j low; j high; j) {if (arr[j] pivot) {i;swap(arr, i, j);}}swap(arr, i 1, high);return i 1;}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int[] arr {10, 7, 8, 9, 1, 5};quickSort(arr);System.out.println(Sorted array:);for (int value : arr) {System.out.print(value );}System.out.println();}
}在这个实现中我们使用了一个双向队列ArrayDeque作为栈用于存储待处理的子数组的边界。quickSort函数初始化栈然后在一个循环中不断弹出栈顶的高边界和低边界进行分区操作并根据分区结果更新栈的内容直到栈为空为止。
这种非递归的方法可以有效地减少内存栈的使用避免了在递归深度过深时可能出现的栈溢出问题同时也能保持快速排序的高效性能。在实际应用中你可以根据具体需求调整分区策略、基准值的选择方法等以进一步优化排序过程。
