您当前的位置: 首页 >  数据结构
  • 2浏览

    0关注

    880博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【大话数据结构C语言】70 快速排序

CodeAllen嵌入式编程 发布时间:2021-05-23 22:00:17 ,浏览量:2

目录

背景

快速排序

复杂度

快速排序的优化

背景
快速排序是图灵奖获得者 Tony Hoare设计提出的
快速排序被誉为20世纪十大算法之一
 
希尔排序是直接插入排序的升级,属于插入排序
堆排序是简单选择排序的升级,属于选择排序类
快速排序是冒泡排序的升级,属于交换排序类
 
快速排序是增加了记录的比较和移动的距离,将关键字较大的记录从前面直接移到后面,关键字较小的记录从后边直接移到前面,从而减少了比较次数和移动交换的次数
 
 
快速排序
快排的基本思想是,通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则可以对这两部分记录继续进行排序,以达到整个序列有序的目的
 
复杂度
快排的时间复杂度:
在最优的情况下为nlogn
最坏的情况下为n方
平均情况:nlogn
 
空间复杂度:logn
 
由于关键字的比较和交换是交换式的,因此,快排是一种不稳定的排序方法
 
 
#include 

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]             
关注
打赏
1665938897
查看更多评论
0.0577s