快速排序算法的分析与研究_王春红

快速排序实验报告
一、目的和要求
1、掌握快速排序的实现方法
2、掌握快速排序的基本思想
3、掌握快速排序的时间性能
4、要求：用快速排序法实现对无序序列的排序
二、程序设计的基本思想，原理和算法描述
快速排序是对起泡排序的一种改进，它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对两部分记录继续进行排序，以达到整个序列有序。

快速排序的三个步骤：
1、选择基准：在待排序列中，按照某种方式挑出一个元素，作为基准
2、分割操作：以该基准在序列中实际位置，把序列分成两个子序列。

此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大
3、递归地对两个序列快速排序，直到序列为空或者只有一个元素。

三、心得与体会
这个实验关键在于理解快速排序的那个过程，如何根据轴值将数
组分成两部分，然后将轴值放到合适的位置，继续对分成两部分的数组，执行类似的操作。

通过这次实验，理解和体会了快速排序的基本思想，了解到在所有同数量级的排序方法中，快速排序的平均性能最好。

快速排序算法描述摘要：一、快速排序算法的基本思想二、快速排序算法的具体步骤三、快速排序算法的优缺点四、快速排序算法的实际应用正文：快速排序算法是一种常用的排序算法，它采用分治的思想，通过选取一个基准元素，将待排序序列划分为两个子序列，其中一个子序列的所有元素都小于基准元素，另一个子序列的所有元素都大于基准元素，然后对这两个子序列分别进行递归排序，最终得到一个有序的序列。

一、快速排序算法的基本思想快速排序算法的基本思想是分治法，它将待排序的序列划分为两个子序列，其中一个子序列的所有元素都小于基准元素，另一个子序列的所有元素都大于基准元素，然后对这两个子序列分别进行递归排序，最终得到一个有序的序列。

二、快速排序算法的具体步骤快速排序算法的具体步骤如下：1.选取一个基准元素pivot；2.把小于基准元素pivot 的元素放到pivot 的左边，大于基准元素pivot 的元素放到pivot 的右边；3.对pivot 左边的子序列和右边的子序列分别递归地执行步骤1 和2，直到子序列的大小为1 或0，即它们已经有序；4.把排序好的子序列合并成一个有序序列。

三、快速排序算法的优缺点快速排序算法的优点是平均时间复杂度为O(nlogn)，且在实际应用中表现较好。

缺点是当序列已经有序或基本有序时，快速排序算法的性能较差，因为在这种情况下，划分出的子序列大小差异不大，导致递归树退化为一棵线性树，时间复杂度变为O(n^2)。

四、快速排序算法的实际应用快速排序算法在实际应用中非常广泛，例如在搜索引擎中，快速排序算法可以用于对搜索结果进行排序；在数据库中，快速排序算法可以用于对数据表进行排序；在文件系统中，快速排序算法可以用于对文件进行排序。

快速排序算法实验报告快速排序算法实验报告引言：快速排序算法是一种常用且高效的排序算法，它的核心思想是通过分治的思想将一个大问题分解成多个小问题，并通过递归的方式解决这些小问题。

本实验旨在通过实际实现和测试快速排序算法，探究其性能和效果。

实验目的：1. 理解快速排序算法的原理和思想；2. 掌握快速排序算法的实现方法；3. 通过实验比较快速排序算法与其他排序算法的性能差异。

实验步骤：1. 算法实现首先，我们需要实现快速排序算法。

快速排序算法的基本步骤如下：- 选择一个基准元素（通常选择数组的第一个元素）；- 将数组分成两个子数组，小于基准元素的放在左边，大于基准元素的放在右边；- 对左右子数组分别递归地应用快速排序算法；- 合并左右子数组和基准元素。

代码实现如下：```pythondef quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[0]left = [x for x in arr[1:] if x < pivot]right = [x for x in arr[1:] if x >= pivot]return quick_sort(left) + [pivot] + quick_sort(right)```2. 性能测试接下来，我们将使用不同规模的随机数组进行性能测试，比较快速排序算法与其他排序算法的效率。

我们选择插入排序算法和归并排序算法作为对比算法。

首先，我们生成1000个随机整数，并分别使用快速排序算法、插入排序算法和归并排序算法进行排序。

记录下每个算法的运行时间。

然后，我们逐渐增加数组的规模，分别测试10000、100000、1000000个随机整数的排序时间。

最后，我们绘制出三种算法在不同规模下的运行时间曲线，并进行分析和比较。

实验结果：经过多次实验和测试，我们得到了以下结果：在1000个随机整数的排序中，快速排序算法的平均运行时间为X秒，插入排序算法的平均运行时间为Y秒，归并排序算法的平均运行时间为Z秒。

快速排序算法的教学要点与方法探讨
1快速排序算法在教学中存在的问题
算法思想内容过于抽象，理解困难，不易掌握。

学生大凡在看到快速排序的算法思想时，一时很难弄明白，也很难理解。

单一从文字叙述方面来弄懂快速排序算法思想很困难，如果我们换个思路，先看详尽案例，再来理解算法，就会发现该算法思想其实并不难理解。

下面通过例子来说明快速排序的算法思想：
图1一趟快速排序
一趟排序之后的状态：{20 38 10 49 75 90 66}。

2快速排序算法的不足之处
3方法探讨
由于数据结构课程内容浩繁、理论抽象、逻辑性强、难以理解等特点，造成教师教学费力，学生学习吃力，教学效果不理想，教师在教学内容的选择方面，存在“重理论，轻实践”的普遍现象。

目前部分教师仍采用传统教学方法――“满堂灌”（讲授法），忽略了学生的主体地位，在讲授理论的同时，不观察学生的听课反映，未给学生留出思考时间，缺少与学生的互动环节，这样可能学生跟不上老师的思路，降低了听课效率。

针对教学中存在的问题，提出如下建议：
（1）采取案例教学，激发学习兴趣
案例教学法具有较强沟通性、针对性、实践性等特点。

课堂教学中运用案例教学法，将理论知识融入案例之中，运用案例引导学生主动学习，激发学习兴趣。

案例教学法的核心――案例必须是优选的。

好的案例对于学生掌握基本概念、基本知识，培养基本技能起到积极的推动作用。

（2）理论联系实际，做好上机实验
学习算法，不仅要理解教材上的理论知识，更严重的是能够联系实际，能针对实际问题编写出正确易读、结构清撤、执行效率高的程序，上机实验也是学习数据结构必不可少的教学环节，对于训练学生编程能力，加深抽象理论的理解至关严重。

一、实验目的1. 理解快速排序算法的基本原理和实现方法。

2. 掌握快速排序算法的递归分治策略。

3. 分析快速排序算法的时间复杂度和空间复杂度。

4. 通过实验验证快速排序算法的性能。

二、实验内容本实验主要涉及快速排序算法的原理、实现和性能分析。

实验内容包括：1. 快速排序算法的基本原理。

2. 快速排序算法的递归分治策略。

3. 快速排序算法的时间复杂度和空间复杂度分析。

4. 快速排序算法的C语言实现。

5. 快速排序算法的性能测试。

三、实验原理快速排序算法是一种高效的排序算法，其基本思想是选取一个基准元素（pivot），将待排序的序列划分为两部分，使得左边的部分都小于等于基准元素，右边的部分都大于等于基准元素。

然后递归地对左右两部分分别进行快速排序，直到整个序列有序。

快速排序算法的递归分治策略如下：1. 选择基准元素：在待排序序列中选取一个元素作为基准元素。

2. 分区操作：将待排序序列划分为两部分，使得左边的部分都小于等于基准元素，右边的部分都大于等于基准元素。

3. 递归排序：分别对左右两部分递归进行快速排序。

四、实验步骤1. 快速排序算法的C语言实现```c#include <stdio.h>void swap(int a, int b) {int temp = a;a = b;b = temp;}int partition(int arr[], int low, int high) { int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high - 1; j++) {if (arr[j] < pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);}void quickSort(int arr[], int low, int high) { if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("Sorted array: \n");printArray(arr, n);return 0;}```2. 快速排序算法的性能测试为了测试快速排序算法的性能，我们可以对不同的输入数据量进行排序，并记录排序所需的时间。

《数据结构课程设计》报告题目：快速排序问题专业计算机科学与技术学生姓名高海松班级B计116学号**********指导教师巩永旺完成日期2013年1月11日目录1简介 (3)2算法说明 (5)3测试结果 (6)4分析与探讨 (8)5小结 (11)附录：源程序清单 (11)一、简介1、排序及排序算法类型排序是数据处理领域和软件设计领域中一种常见而重要的运算。

排序就是将一组记录（元素）的任意序列按照某个域的值的递增（从小到大）或递减（由大到小）的次序重新排列的过程。

排序的目的之一就是为了方便查找。

排序分为内部排序和外部排序。

在内存中进行的排序叫内部排序，利用外部存储的排序叫外部排序。

内部排序的方法有很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的缺点，适合在不同的环境下使用。

按照其策略不同，可归纳为五类：插入排序、交换排序、选择排序、归并排序和基数排序。

2、快速排序算法介绍快速算法就像是它的名称所暗示的，是一种快速的分而治之的算法，平均时间复杂度为O(nlog2n)。

它的速度主要归于一个非常紧凑并且高度优化的内部循环。

其基本算法Quicksort(S)由以下4个步骤组成：（1）如果S中的元素的个数为0或1 ，则返回。

（2）选择S中的任意一个元素v,v叫做支点（Pivot）.（3）将S—{v}(剩下的元素在S中)分成两个分开的部分。

L={x∈S—{v}|x ≦v}和R={x∈S-{v}|x≧v}。

（4）依次返回Quicksort（L）、v和Quicksort(R)的结果。

基本的快速排序算法可以应用递归实现，关键的细节包括支点的选择和如何分组。

该算法允许把任何元素作为支点。

支点把数组分为两组：小于支点的元素和大于支点的元素集。

图1展示了一组数据进行快速排序的基本过程。

3、快速排序的分析（1）最好情况：快速排序的最好情况是支点把集合分成两个同等大小的子集，并且在递归的每个阶段都这样划分。

一、实验目的1. 理解快速排序算法的基本原理和实现方法。

2. 掌握快速排序算法的代码实现。

3. 通过实验验证快速排序算法的效率。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验原理快速排序是一种常用的排序算法，它采用分而治之的策略，将待排序的数组分为两部分，使得左边的元素都比右边的元素小，然后递归地对左右两边的子数组进行排序。

快速排序的平均时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)。

快速排序算法的核心是选择一个基准值，然后将数组分为两个子数组，一个子数组的元素都比基准值小，另一个子数组的元素都比基准值大。

然后递归地对这两个子数组进行快速排序。

四、实验步骤1. 设计快速排序算法的函数，包括选择基准值、划分数组、递归排序等步骤。

2. 编写主函数，用于测试快速排序算法。

3. 使用不同大小的数组进行测试，观察算法的执行时间。

五、实验代码```pythondef quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)def test_quick_sort():import timetest_arrays = [[3, 6, 8, 10, 1, 2, 1],[5, 3, 8, 6, 2],[9, 1, 5, 3, 4, 7],[3, 3, 3, 3, 3, 3, 3, 3],[1],[]]for arr in test_arrays:start_time = time.time()sorted_arr = quick_sort(arr)end_time = time.time()print(f"Original array: {arr}")print(f"Sorted array: {sorted_arr}")print(f"Execution time: {end_time - start_time:.6f} seconds\n") test_quick_sort()```六、实验结果与分析1. 测试数组：[3, 6, 8, 10, 1, 2, 1]- 原始数组：[3, 6, 8, 10, 1, 2, 1]- 排序后数组：[1, 1, 2, 3, 6, 8, 10] - 执行时间：0.000097 seconds2. 测试数组：[5, 3, 8, 6, 2]- 原始数组：[5, 3, 8, 6, 2]- 排序后数组：[2, 3, 5, 6, 8]- 执行时间：0.000073 seconds3. 测试数组：[9, 1, 5, 3, 4, 7]- 原始数组：[9, 1, 5, 3, 4, 7]- 排序后数组：[1, 3, 4, 5, 7, 9]- 执行时间：0.000061 seconds4. 测试数组：[3, 3, 3, 3, 3, 3, 3, 3]- 原始数组：[3, 3, 3, 3, 3, 3, 3, 3] - 排序后数组：[3, 3, 3, 3, 3, 3, 3, 3] - 执行时间：0.000000 seconds5. 测试数组：[1]- 原始数组：[1]- 排序后数组：[1]- 执行时间：0.000000 seconds6. 测试数组：[]- 原始数组：[]- 排序后数组：[]- 执行时间：0.000000 seconds从实验结果可以看出，快速排序算法对于不同大小的数组都能在较短的时间内完成排序，且对于大部分情况，执行时间都在微秒级别。

数据结构之快速排序快速排序算法原理和实现方法快速排序是一种常用的排序算法，其原理是通过将待排序序列划分成较小和较大两个子序列，然后对两个子序列进行递归排序，最终得到有序序列。

本文将介绍快速排序算法的原理和实现方法。

一、快速排序算法原理快速排序算法的原理可以分为以下几个步骤：1. 选择一个基准元素：从待排序序列中选择一个元素作为基准元素，通常选择第一个元素或最后一个元素。

2. 分割操作：将待排序序列划分成两个子序列，使得左边子序列中的元素都小于基准元素，右边子序列中的元素都大于基准元素。

同时基准元素位于两个子序列中间的正确位置。

3. 递归排序：对左边子序列和右边子序列分别进行递归排序。

4. 合并操作：将左边子序列、基准元素和右边子序列合并起来，得到最终的有序序列。

二、快速排序算法实现方法下面给出一种常见的实现快速排序算法的方法：1. 选择基准元素：从待排序序列中选择第一个元素作为基准元素。

2. 定义两个指针：设置两个指针low和high，分别指向待排序序列的起始位置和结束位置。

3. 划分操作：循环执行以下操作，直到low和high相遇为止：- 从high指针开始，向前遍历，找到一个小于等于基准元素的元素，将其与low指针指向的元素进行交换。

- 从low指针开始，向后遍历，找到一个大于基准元素的元素，将其与high指针指向的元素进行交换。

4. 递归排序：对基准元素左边的子序列和右边的子序列进行递归排序。

5. 合并操作：将左边子序列、基准元素和右边子序列合并起来。

三、示例代码下面给出示例代码，演示如何实现快速排序算法：```pythondef quick_sort(arr, low, high):if low < high:pivot_index = partition(arr, low, high) # 划分操作，得到基准元素的正确位置quick_sort(arr, low, pivot_index - 1) # 对基准元素左边的子序列进行递归排序quick_sort(arr, pivot_index + 1, high) # 对基准元素右边的子序列进行递归排序def partition(arr, low, high):pivot = arr[low] # 选择第一个元素作为基准元素while low < high:while low < high and arr[high] >= pivot:high -= 1arr[low] = arr[high]while low < high and arr[low] <= pivot:low += 1arr[high] = arr[low]arr[low] = pivotreturn low# 测试arr = [6, 5, 3, 1, 8, 7, 2, 4]quick_sort(arr, 0, len(arr)-1)print(arr) # 输出：[1, 2, 3, 4, 5, 6, 7, 8]```以上是快速排序算法的原理和实现方法。

快速排序算法
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：初始状态{49 38 65 97 76 13 27} 进行一次快速排序之后划分为{27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序{27 38 13} 经第三步和第四步交换后变成{13 27 38} 完成排序。

{76 97 65} 经第三步和第四步交换后变成{65 76 97} 完成排序。

运行结果：
27 38 13 49 76 97 65
13 27 38 49 76 97 65
13 27 38 49 65 76 97
第一轮函数调用的详细过程：
{49 38 65 97 76 13 27}
i =0 j=6 Key=49
第一轮循环：i=0 j=6 {27 38 65 97 76 13 27} j=6 {27 38 65 97 76 13 65} i=2
第二轮循环：i=2 j=6 {27 38 13 97 76 13 65} j=5 {27 38 13 97 76 97 65} i=3
第三轮循环：i=3 j=5 {27 38 13 97 76 97 65} j=3
循环结束：i=3 j=3 a[i] = key {27 38 13 49 76 97 65}
C语言版本
C++语言
Java
C#。

第1篇一、实验背景随着计算机科学的发展，算法在各个领域都扮演着至关重要的角色。

排序算法作为算法领域中的一项基本技能，其重要性不言而喻。

快速排序作为一种高效的排序算法，因其简洁的原理和良好的性能，被广泛应用于各种场景。

本次实验旨在通过实践，深入了解快速排序算法的原理、实现及其性能特点。

二、实验目的1. 掌握快速排序算法的基本原理和实现方法；2. 分析快速排序算法的时间复杂度和空间复杂度；3. 比较快速排序与其他排序算法的性能差异；4. 熟练运用快速排序算法解决实际问题。

三、实验内容1. 快速排序算法原理及实现快速排序是一种分而治之的排序算法，其基本思想是：选取一个基准元素，将待排序序列划分为两个子序列，一个子序列中的所有元素均小于等于基准元素，另一个子序列中的所有元素均大于等于基准元素。

然后递归地对这两个子序列进行快速排序。

具体实现步骤如下：（1）选择基准元素：从待排序序列中选取一个元素作为基准元素，通常选择序列的第一个或最后一个元素。

（2）划分：将待排序序列划分为两个子序列，左子序列包含小于等于基准元素的元素，右子序列包含大于等于基准元素的元素。

（3）递归排序：递归地对左子序列和右子序列进行快速排序。

2. 快速排序算法性能分析快速排序算法的平均时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)。

空间复杂度为O(logn)，因为快速排序采用递归实现，需要一定的栈空间。

3. 快速排序与其他排序算法的比较与冒泡排序、插入排序等简单排序算法相比，快速排序具有以下优点：（1）时间复杂度较低，适用于大规模数据的排序；（2）空间复杂度较低，节省内存资源；（3）对数据结构无特殊要求，适用于各种数据类型。

然而，快速排序也存在以下缺点：（1）最坏情况下的时间复杂度较高，当数据量较大且分布不均匀时，性能可能不如其他排序算法；（2）递归实现可能导致栈溢出，对数据量较大的排序任务不适用。

四、实验总结通过本次实验，我对快速排序算法有了更深入的了解。

快速排序的实验报告快速排序的实验报告引言：排序算法是计算机科学中的基础知识之一，它在数据处理和算法设计中扮演着重要的角色。

其中，快速排序是一种高效的排序算法，它的时间复杂度为O(nlogn)，在大多数情况下表现出色。

本实验旨在通过对快速排序算法的实验研究，验证其效率和可靠性。

实验设计：本次实验采用C++语言编写，通过随机生成不同规模的数组，并对其进行快速排序。

实验中，我们将比较不同规模数据的排序时间，并分析其结果。

实验步骤：1. 随机生成不同规模的数组，包括100个、1000个和10000个元素，元素范围在1到100之间。

2. 使用快速排序算法对生成的数组进行排序，并记录排序所需时间。

3. 多次运行实验，取平均时间，以提高实验结果的可靠性。

实验结果：经过多次实验，我们得到了如下结果：1. 对于100个元素的数组，快速排序的平均时间为0.001秒。

2. 对于1000个元素的数组，快速排序的平均时间为0.02秒。

3. 对于10000个元素的数组，快速排序的平均时间为0.3秒。

实验分析：通过对实验结果的分析，我们可以得出以下结论：1. 随着数组规模的增加，快速排序的时间也呈指数级增长。

这符合快速排序算法的时间复杂度为O(nlogn)的特性。

2. 快速排序在处理小规模数据时表现出色，排序时间非常短。

3. 随着数据规模的增加，排序时间也显著增加，但相对于其他排序算法，快速排序仍然是一种高效的排序算法。

实验总结：通过本次实验，我们验证了快速排序算法的高效性和可靠性。

快速排序算法在处理大规模数据时仍然表现出色，且具有较低的时间复杂度。

然而，我们也要注意到，快速排序在处理小规模数据时效果更好，对于大规模数据可能存在一定的性能瓶颈。

结论：快速排序是一种高效的排序算法，通过本次实验，我们验证了其在不同规模数据上的表现。

然而，在实际应用中，我们需要根据具体情况选择合适的排序算法，综合考虑时间复杂度、空间复杂度以及实际应用场景。

快速排序算法分析解析快速排序算法的时间复杂度和各次标准数据元素的值关系很⼤。

如果每次选取的标准元素都能均分两个⼦数组的长度,这样的快速排序过程是⼀个完全⼆叉树结构。

(即每个结点都把当前数组分成两个⼤⼩相等的数组结点,n个元素数组的根结点的分解次数就构成⼀棵完全⼆叉树)。

这时分解次数等于完全⼆叉树的深度log2n;每次快速排序过程⽆论把数组怎样划分、全部的⽐较次数都接近于n-1次，所以最好情况下快速排序算法的时间复杂度为O(nlog2n):快速排序算法的最坏情况是数据元素已全部有序，此时数据元素数组的根结点的分需次数构成⼀棵⼆叉退化树(即单分⽀⼆叉树),⼀棵⼆叉退化树的深度是n,所以最坏情况下快速排序算法的时间复杂度为O(n2)。

般情况下 ,标准元素值的分布是随机的，数组的分邮⼤数构成模⼆⼜树，这样的⼆叉树的深度接近于log2n, 所以快速排序算法的平均(或称期望）时间复杂度为O(nlog2n)function findKey(&$arr, $low, $hight){$target = $arr[$low];while ($low < $hight) {while ($low < $hight && $target < $arr[$hight]) {$hight--;}$arr[$low] = $arr[$hight];while ($low < $hight && $target > $arr[$low]) {$low++;}$arr[$hight] = $arr[$low];}$arr[$hight]=$target;return$hight;}function quickSort(&$arr,$low,$hight){$posKey=findKey($arr,$low,$hight);if($low<$posKey){quickSort($arr,$low,$posKey-1);}if($posKey<$hight){quickSort($arr,$posKey+1,$hight);}}$arr = [12, 56, 98, 32, 16, 34, 2, 9, 1];$len = count($arr);quickSort($arr, 0, $len - 1);var_dump($arr);die;。

快速排序算法的分析与研究王春红;王文霞【摘要】Quick sort is one of sorting algorithms with better performance,but it has choke point when sorted data is in ba-sic sort order. In order to ensure high efficiency of quick sort in any case,based on a full analysis of the time efficiency of quick sorting algorithm,it is pointed out that the main factor which affects the efficiency of quick sorting algorithms is the selec-tion of pointing element. Therefore,a quick sorting method of selecting the pointing element randomly is proposed,which makes the occurrence of the worst case well avoided. The correctness and efficiency of the improved algorithm were verified by experi-ments.%快速排序是排序算法中性能较好的一种，但存在对数据基本有序的情形下的性能瓶颈问题。

为了保证快速排序在任何情况下的高效性，在对快速排序算法的时间效率进行充分的分析的基础上，指出支点元素的选取是影响快速排序算法效率的主要因素。

提出了一种随机选择支点元素的快速快排方法，很好地避免了最坏情况的发生。

通过实验验证了改进算法的正确性和高效性。

排序算法杂谈（五）——关于快速排序的优化策略分析1. 前提2. 优化策略1：主元（Pivot）的选取归并排序（Merge Sort）有⼀个很⼤的优势，就是每⼀次的递归都能够将数组平均⼆分，从⽽⼤⼤减少了总递归的次数。

⽽快速排序（Quick Sort）在这⼀点上就做的很不好。

快速排序是通过选择⼀个主元，将整个数组划分（Partition）成两个部分，⼩于等于主元 and ⼤于等于主元。

这个过程对于数组的划分完全就是随机的，俗称看脸吃饭。

这个划分是越接近平均⼆分，那么这个划分就越是优秀；⽽若果不巧取到了数组的最⼤值或是最⼩值，那这次划分其实和没做没有什么区别。

因此，主元的选取，直接决定了⼀个快速排序的效率。

通过之前快速排序的学习，我们知道了基本上有两种主流的划分⽅式，我将其称之为：挖坑取数快慢指针前者将最左侧的数作为主元，后者将最右侧的数作为主元，这种⾏为完全就是随机取数。

最简单的的⽅法，就是在范围内取⼀个随机数，但是这种⽅法从概率的⾓度上来说，和之前的没有区别。

进⼀步的思考，可以从范围内随机取出三个数字，找到三个数字的中位数，然后和原主元的位置进⾏交换。

将中位数作为主元，相⽐于随机取出的另外两个数字，对于划分的影响还是很明显的。

1package pare.quick.partition.pivot;23import com.gerrard.util.RandomHelper;45public final class MediumPivot implements Pivot {67 @Override8public int getPivotIndex(int[] array, int left, int right) {9int index1 = RandomHelper.randomBetween(left, right);10int index2 = RandomHelper.randomBetween(left, right);11int index3 = RandomHelper.randomBetween(left, right);12if (array[index1] > array[index2]) {13if (array[index2] > array[index3]) {14return index2;15 } else {16return array[index1] > array[index3] ? index3 : index1;17 }18 } else {19if (array[index1] > array[index3]) {20return index3;21 } else {22return array[index2] > array[index3] ? index3 : index2;23 }24 }25 }26 }3. 优化策略2：阈值的选取同样是参考归并排序的优化策略，归并排序可以通过判断数组的长度，设定⼀个阈值。

快速排序实验排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

假设含n个记录的序列为{ R1, R2, …， R n }其相应的关键字序列为 { K1, K2, …，K n }这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：K p1≤K p2≤…≤K pn按此固有关系将上式记录序列重新排列为{ R p1, R p2, …，R pn }的操作称作排序。

排序算法是计算机科学中最重要的研究问题之一。

对于排序的研究既有理论上的重要意义，又有实际应用价值。

它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。

常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。

例1：有时候应用程序本身就需要对信息进行排序。

为了准备客户账目，银行需要根据支票的号码对支票排序；例2：在一个绘制互相重叠的图形对象的程序中，可能需要根据一个“在上方”关系将各对象排序，以便自下而上地绘出对象。

例3：在一个由n个数构成的集合上，求集合中第i小/大的数。

例4：对一个含有n个元数的集合，求解中位数、k分位数。

问题描述在操作系统中，我们总是希望以最短的时间处理完所有的任务。

但事情总是要一件件地做，任务也要操作系统一件件地处理。

当操作系统处理一件任务时，其他待处理的任务就需要等待。

虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。

只需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。

当有 n 件任务同时来临时，每件任务需要用时n i，求让所有任务等待的时间和最小的任务处理顺序。

基本要求（1）数据的输入输出格式：输入：第一行是一个整数n，代表任务的件数。

接下来一行，有n个正整数，代表每件任务所用的时间。

输出：输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。