intx =A[r];
inti =p- 1;
for(intj =p; j <=r- 1; j++)
{
if(A[j] <= x) {
i j);
}
}
Exchange(A, i + 1,r);
returni + 1;
}
//在左右两个区间进行递归调用本身
voidquick_sort(intA[],intp,intr)
for(int i = 0;i < length;i++){
cout<<array[i]<<endl;
}
end = clock();
cout<<"优化排序时间为："<< end - start<<endl;;
}
void QUICK_INSERT_SORT (int A[],int n,int k)
{
{
quick_sort(A,0,n,k);
int i=0;
int x=0;
for(int j=1;j<=n;j++)
{
x = A[j];
i = j;
while(i > 0 && A[i - 1] > x)
{
A[i] = A[i - 1];
i--;
}
A[i] = x;
}
}
三、结果与分析：
题目一:
下面是运行快速排序算法，首先生成1000个随机数组成的数组，然后对这1000个随机数进行排序，最后利用c++的时间函数对整个数组输出进行统计时间，得到的时间为743.
}
end = clock();
cout<<"时间是"<<end - start<<endl;
}
intPARTITION(intA[],intp,intr) {
intx =A[r];
inti =p- 1;
for(intj =p; j <=r- 1; j++)
{
if(A[j] <= x) {
i = i + 1;
voidquick_sort(intA[],intp,intr);
intmain()
{
//定义一个随机产生1000个数的数组
intlength = 1000;
int*array =newint[length];
for(inti = 0; i < length; i++)
{
array[i] = rand();
Exchange(A, i, j);
}
}
Exchange(A, i + 1,r);
returni + 1;
}
//交换两个数
voidExchange(intA[],intleft,intend) {
inttemp;
temp =A[left];
A[left] =A[end];
A[end] = temp;
int *array = new int[length];
for(int i = 0;i < length;i++)
{
array[i]=rand();
cout<<array[i]<<endl;
}
//调用时间函数
clock_t start,end;
start = clock();
QUICK_INSERT_SORT(array,length-1,k);
附录（源代码）
算法源代码（C/C++/JAVA描述）
//题目一：快速排序算法
#include<iostream>
usingnamespacestd;
#include<cstdlib>
#include<ctime>
intPARTITION(intA[],intp,intr);
voidExchange(intA[],intleft,intend);
《算法设计与分析》上机报告
姓名：
学号：
SA1722
日期：
2017.11
上机题目：
快速排序算法及优化
实验环境：
CPU：i5;内存:;操作系统：win10;软件平台：VS2015;
一、算法设计与分析：
题目一:
实现快速排序算法
题目二：
快速排序优化算法
二、核心代码：
题目一:
//把A数组分为两部分
intPARTITION(intA[],intp,intr) {
}
//递归调用快速排序算法
voidquick_sort(intA[],intp,intr)
{
intq=0;
if(p<r)
{
q = PARTITION(A,p,r);
quick_sort(A,p, q - 1);
quick_sort(A, q + 1,r);
}
}
//题目二：快速排序优化算法
#include <iostream>
{
int q=0;
if(r-p>k)
{
q = PARTITION(A,p,r);
quick_sort(A ,p, q-1,k);
quick_sort(A, q+1,r, k);
}
}
int MEDIAN(int A[],int p,int r)
{
int middle = (p + r)/2;
if(A[middle] < A[p]){
{
int x = MEDIAN(A,p,r);
int i = p - 1;
for(int j = p;j <= r - 1;j++)
{
if(A[j] <= x)
{
i = i + 1;
Exchange(A,i,j);
}
}
Exchange(A,i+1,r);
return i + 1;
}
void Exchange(int A[] , int left, int end) {
cout<<array[i]<<endl;
}
//调用时间函数，计算排序后程序运行的时间
clock_tstart, end;
start = clock();
quick_sort(array, 0, length-1);
for(inti = 0; i < length; i++)
{
cout<<array[i]<<endl;
int MEDIAN(int A[],int p,int r);
int PARTITION(int A[],int p,int r);
void Exchange(int A[] , int left, int end);
int main()
{
int length = 1000;
int k = 20;
Exchange(A,p,middle);
}
if(A[r] < A[p]){
Exchange(A,p,r);
}
if(A[r] < A[middle]){
Exchange(A,middle,r);
}
Exchange(A,middle,r - 1);
return A[r - 1];
}
int PARTITION(int A[],int p,int r)
int temp;
temp = A[left];
A[left] = A[end];
A[end] = temp;
}
{
intq=0;
if(p<r)
{
q = PARTITION(A,p,r);
quick_sort(A,p, q - 1);
quick_sort(A, q + 1,r);
}
}
题目二：
//对k=20规模时，对数组进行插入排序的算法
void QUICK_INSERT_SORT (int A[],int n,int k)
题目二：
下面是运行快速排序优化算法，首先生成1000个随机数组成的数组，然后对这1000个随机数进行排序，最后利用c++的时间函数对整个数组输出进行统计时间，得到的时间为495.相对于普通快速排序算法快了248.
四、备注（*可选）：
有可能影响结论的因素：
总结：
经过优化后的快速排序算法先是进行快速排序不断进行分治，等分治后的分数个数达到20后进行插入排序，从而能减少了算法的时间。
using namespace std;
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
void QUICK_INSERT_SORT(int A[],int n,int k);
void quick_sort(int A[], int p, int r,int k);
quick_sort(A,0,n,k);
int i=0;
int x=0;
for(int j=1;j<=n;j++)
{
x = A[j];
i = j;
while(i > 0 && A[i - 1] > x)
