121.【C语言】数据结构之快速排序(未优化的Hoare排序存在的问题)以及时间复杂度的分析
目录
1.未优化的Hoare排序存在的问题
测试代码
"量身定制"的测试代码1
运行结果
"量身定制"的测试代码2
运行结果
"量身定制"的测试代码3
运行结果
分析代码1、2和3栈溢出的原因
排有序数组的分析
分析测试代码1:给一个升序数组,要求排升序
分析测试代码2:给一个降序数组,要求排升序
分析测试代码3:给一个元素全相同的数组,要求排升序
分析排有序和数组元素全相同的时间复杂度
分析一般情况下快排的时间复杂度
1.未优化的Hoare排序存在的问题
将120.【C语言】数据结构之快速排序(详解Hoare排序算法)文章的Hoare排序代码的性能(116.【C语言】测试排序性能的模板代码 点我跳转)
测试代码
在VS2022+Debug+x86环境下,试试下面这个为没有优化的Hoare排序"量身定制"的修改过的测试性能的两个代码
"量身定制"的测试代码1
void ShellSort(int* arr, int n)//排升序
{
int gap = n;
while (gap > 1)
{
gap /= 2;
for (int i = gap; i < n; i++)//交替排序,每次i+1
{
int end = i - gap;
int tmp = arr[end + gap];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
void TestTime()
{
srand((unsigned int)time(0));
const int N = 10000;
int* a1 = (int*)malloc(sizeof(int) * N);
if (a1 == NULL)
{
perror("malloc");
return;
}
for (int i = 0; i < N; i++)
{
a1[i] = rand();
}
ShellSort(a1, N);
clock_t begin2 = clock();
QuickSort(a1, 0, N-1);
clock_t end2 = clock();
printf("QuickSort's time=%ldms\n", end2 - begin2);
free(a1);
}
int main()
{
TestTime();
return 0;
}运行结果
虽然N==10000不是很大,但是栈溢出(Stack overflow)了
"量身定制"的测试代码2
void ShellSort(int* arr, int n)//排降序
{
int gap = n;
while (gap > 1)
{
gap /= 2;
for (int i = gap; i < n; i++)//交替排序,每次i+1
{
int end = i - gap;
int tmp = arr[end + gap];
while (end >= 0)
{
if (tmp > arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
void TestTime()
{
const int N = 10000;
int* a1 = (int*)malloc(sizeof(int) * N);
if (a1 == NULL)
{
perror("malloc");
return;
}
for (int i = 0; i < N; i++)
{
a1[i] = rand();
}
ShellSort(a1,N);
clock_t begin2 = clock();
QuickSort(a1, 0, N-1);
clock_t end2 = clock();
printf("QuickSort's time=%ldms\n", end2 - begin2);
free(a1);
}
int main()
{
TestTime();
return 0;
}运行结果
"量身定制"的测试代码3
void TestTime()
{
const int N = 10000;
int* a1 = (int*)malloc(sizeof(int) * N);
if (a1 == NULL)
{
perror("malloc");
return;
}
for (int i = 0; i < N; i++)
{
a1[i] = 2;
}
clock_t begin2 = clock();
QuickSort(a1, 0, N-1);
clock_t end2 = clock();
printf("QuickSort's time=%ldms\n", end2 - begin2);
free(a1);
}
int main()
{
TestTime();
return 0;
}运行结果
三个测试代码的运行结果都Stack overflow(栈溢出)
分析代码1、2和3栈溢出的原因
仔细看看测试代码1是怎么"量身定制"的:(下面展示关键代码)
ShellSort(a1, N);//调用希尔排序先对数组a1排升序一次
//......
//调用120.【C语言】数据结构之快速排序(详解Hoare排序算法)文章的Hoare排序代码
QuickSort(a1, 0, N-1);
//......发现
① 希尔排序和快速排序排的都是同一个数组
② 先用希尔排序将数组a1排升序后再用快速排序排升序
仔细看看测试代码2是怎么"量身定制"的:(下面展示关键代码)
ShellSort(a1, N);//调用希尔排序先对数组a1排降序一次
//......
//调用120.【C语言】数据结构之快速排序(详解Hoare排序算法)文章的Hoare排序代码
QuickSort(a1, 0, N-1);
//......发现
① 希尔排序和快速排序排的都是同一个数组
② 先用希尔排序将数组a1排升序后再用快速排序排降序
仔细看看测试代码3是怎么"量身定制"的:(下面展示关键代码)
for (int i = 0; i < N; i++)
{
a1[i] = 2;
}发现 a1[0]==a1[1]==a1[2]==...==a1[N-1]
由发现可得知:未优化的快速排序会对有序或接近优先有序或每个元素都相同的数组产生栈溢出的问题,由于是递归调用,则栈溢出的原因显然是递归调用次数过多导致开辟的栈帧空间过多而溢出导致的
排有序数组的分析
分析测试代码1:给一个升序数组,要求排升序
分析测试代码2:给一个降序数组,要求排升序
分析测试代码3:给一个元素全相同的数组,要求排升序
从三个测试代码可以看出:关键值key并没有起到分割数组的作用,反而每次都需要对数组的整体进行排序,这样导致函数的栈帧开辟的空间越来越大,函数没有没有及时返回(销毁),从而导致栈溢出
分析排有序和数组元素全相同的时间复杂度
上述三种是快排最坏情况循环的次数为N+N-1+N-2+...+1,为等差数列求和,时间复杂度为
总结:影响快速排序的性能为key(arr[key_i]==key),key_i越接近中间-->越能二分-->越接近满二叉树-->深度越均匀-->效率越高
分析一般情况下快排的时间复杂度
从上方的总结上分析一般情况下快排的时间复杂度:类似于二叉树
lgn的算法:设总行数为x
因此
(简写为
)
第一行排n次,第二行排(n/2)*2次,第三行排(n/3)*3次,...,第lgn行排n次
因此总次数为,时间复杂度为