快速排序算法的实验验证 [ 实验目的] 验证快速排序算法。(C++)

快速排序算法流程图~

看看这个，我找不到原链接了。如果有帮助，心里感谢下作者。谢谢！

1．将i 和j分别指向待排序区域的最左侧记录和最右侧记录的位置；
2．重复下述过程，直到i=j
2.1右侧扫描，直到记录j的关键码小于基准记录的关键码；
2.2 如果i<j，则将r[j]与r[i]交换，并将i++；
2.3左侧扫描，直到记录i的关键码大于基准记录的关键码；
2.4 如果i<j，则将r[i]与r[j]交换，并将j--；
3．退出循环，说明i和j指向了基准记录所在位置，返回该位置；
void QuickSort(int r[ ], int first, int end)
{
if (first<end) { //递归结束
pivot=Partition(r, first, end); //一次划分
QuickSort(r, first, pivot-1); //递归地对左侧子序列进行快速排序
QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序
}
}

int Partition(int r[ ], int first, int end)
{
i=first; j=end; //初始化
while (i<j)
{
while (i<j && r[i]<= r[j]) j--； //右侧扫描
if (i<j) {
r[i]←→r[j]; //将较小记录交换到前面
i++;
}
while (i<j && r[i]<= r[j]) i++； //左侧扫描
if (i<j) {
r[j]←→r[i]; //将较大记录交换到后面
j--;
}
}
retutn i; //i为轴值记录的最终位置
}

今天介绍快速排序，这也是在实际中最常用的一种排序算法，速度快，效率高。就像名字一样，快速排序是最优秀的一种排序算法。

思想

快速排序采用的思想是分治思想。

快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

举例说明一下吧，这个可能不是太好理解。假设要排序的序列为

2 2 4 9 3 6 7 1 5 首先用2当作基准，使用i j两个指针分别从两边进行扫描，把比2小的元素和比2大的元素分开。首先比较2和5，5比2大，j左移

2 2 4 9 3 6 7 1 5 比较2和1，1小于2，所以把1放在2的位置

2 1 4 9 3 6 7 1 5 比较2和4，4大于2，因此将4移动到后面

2 1 4 9 3 6 7 4 5 比较2和7，2和6，2和3，2和9，全部大于2，满足条件，因此不变

经过第一轮的快速排序，元素变为下面的样子

[1] 2 [4 9 3 6 7 5]

之后，在把2左边的元素进行快排，由于只有一个元素，因此快排结束。右边进行快排，递归进行，最终生成最后的结果。

代码

int quicksort(vector<int> &v, int left, int right){
if(left < right){
int key = v[left];
int low = left;
int high = right;
while(low < high){
while(low < high && v[high] > key){
high--;
}
v[low] = v[high];
while(low < high && v[low] < key){
low++;
}
v[high] = v[low];
}
v[low] = key;
quicksort(v,left,low-1);
quicksort(v,low+1,right);
}
}

分析

快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。

最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)

在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)

尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。

---

上思县18649564358： 算法与数据结构实验顺序表的应用实验报告 - ？
俎壮七味： 者visual c++都行. 看看这个也许你会明白的更多一些. 实验一 多项式相加一、实验目的 熟悉链表的使用. 掌握如何使用C语言实现链表的说明、创建以及结点的插入和删除等操作.二、实验要求熟悉C语言编程.三、实验内容对于两个...

上思县18649564358： C语言的一些东西 - ？
俎壮七味： 先暂时给你这么多批注吧,你去看看,有问题直接QQ联系, 麻烦采纳!实验九 排序 一、实验目的 1. 掌握常用的排序方法,并掌握用高级语言实现排序算法的方法;2. 深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用; 3. 了解各...

上思县18649564358： 课题31:给出一组实验来比较下列排序算法的时间性能: 快速排序、堆排序、希尔排序、冒泡排序、归并排 - ？
俎壮七味： 7个以下数据,插入排序有效率.以上数据,安排有序(顺序,逆序),随机数多组进行测试.一般来说,快排最快,但是原始数据有序情况下会退化为n平方,需要随机化.

上思县18649564358： 用快速排序对实验二的学生数据进行处理,让其按照平均分从小到大的顺序排列.？
俎壮七味： #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;time.h&gt; struct student { int num; char *name; int math; int computer; int english; int avg; }stu[5] = { {1001, ＂丁一＂, 90, 95, 85, 90}, {1002, ＂马二＂, 80, 85, 90, 85}, {1003, ＂张...

上思县18649564358： 用vc实现排序输出过程 - ？
俎壮七味： 我提供各种排序的算法和实现源代码 希望会对你有帮助 相关知识介绍(所有定义只为帮助读者理解相关概念,并非严格定义):1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序...

上思县18649564358： 如何证明快速排序法的平均复杂度为O - ？
俎壮七味： 时间复杂度为O(nlogn) n为元素个数1. 快速排序的三个步骤:1.1. 找到序列中用于划分序列的元素1.2. 用元素划分序列1.3. 对划分后的两个序列重复1,2两个步骤指导序列无法再划分 所以对于n个元素其排序时间为T(n) = 2*T(n/2) + n (表示将长...

上思县18649564358： 最快的排序方法和题目. - ？
俎壮七味： 快速排序是对冒泡排序的一种改进.它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归...

上思县18649564358： 算法分析程序设计,用C语言 - ？
俎壮七味： 第一题#include <stdlib.h>#include <stdio.h> int main(int argc, char **argv) { int num[1000]; int min=10000; int i;for(i=0;i<2000;i++) { num[i] = rand() % 10000; if(num[i]<min) min=num[i]; } printf(＂The min number is %d\n＂,min); return 0; } 第二题...

上思县18649564358： 用C语言编程实现快速排序算法 - ？
俎壮七味： 给个快速排序你参考参考 /********************** 快速排序 **************************** 基本思想:在待排序的n个记录中任取一个记录(通常取第一个记录), 以该记录为基准,将当前的无序区划分为左右两个较小的无 序子区,使左边的记录均小于基...