【大话数据结构C语言】70 快速排序
【摘要】
目录
背景
快速排序
复杂度
快速排序的优化
背景
快速排序是图灵奖获得者 Tony Hoare设计提出的
快速排序被誉为20世纪十大算法之一
希尔排序是直接插入排序的升级，属于插入排序
堆排序是简单选择排序的升级，属于选择排序类
快速排序是冒泡排序的升级，属于交换...
目录
背景
快速排序是图灵奖获得者 Tony Hoare设计提出的
快速排序被誉为20世纪十大算法之一
希尔排序是直接插入排序的升级，属于插入排序
堆排序是简单选择排序的升级，属于选择排序类
快速排序是冒泡排序的升级，属于交换排序类
快速排序是增加了记录的比较和移动的距离，将关键字较大的记录从前面直接移到后面，关键字较小的记录从后边直接移到前面，从而减少了比较次数和移动交换的次数
快速排序
快排的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则可以对这两部分记录继续进行排序，以达到整个序列有序的目的
复杂度
快排的时间复杂度：
在最优的情况下为nlogn
最坏的情况下为n方
平均情况：nlogn
空间复杂度：logn
由于关键字的比较和交换是交换式的，因此，快排是一种不稳定的排序方法
-
#include <stdio.h>
-
-
void swap(int k[], int low, int high)
-
{
-
int temp;
-
-
temp = k[low];
-
k[low] = k[high];
-
k[high] = temp;
-
}
-
-
int Partition(int k[], int low, int high)
-
{
-
int point;
-
-
point = k[low];
-
-
while( low < high )
-
{
-
while( low < high && k[high] >= point )
-
{
-
high--;
-
}
-
swap(k, low, high);
-
-
while( low < high && k[low] <= point )
-
{
-
low++;
-
}
-
swap(k, low, high);
-
}
-
-
return low;
-
}
-
-
void QSort(int k[], int low, int high)
-
{
-
int point;
-
-
if( low < high )
-
{
-
point = Partition(k, low, high);
-
-
QSort(k, low, point-1);
-
-
QSort(k, point+1, high);
-
}
-
}
-
-
void QuickSort(int k[], int n)
-
{
-
QSort(k, 0, n-1);
-
}
-
-
int main()
-
{
-
int i, a[10] = {4, 2, 5, 0, 3, 9, 1, 7, 6, 8};
-
-
QuickSort(a, 10);
-
-
printf("排序后的结果是：");
-
for( i=0; i < 10; i++ )
-
{
-
printf("%d", a[i]);
-
}
-
printf("\n\n");
-
-
return 0;
-
}
快速排序的优化
1.优化选取基准点
2.优化不必要的交换
3.优化小数组时的排序方案
4.优化递归操作
文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。
原文链接：allen5g.blog.csdn.net/article/details/117201550
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）