剑痴乎

  • 首页
  • 文章分类
    • 音视频
    • WebRTC
    • 编程之美
    • Linux
    • Windows
    • 生活点滴
    • 校园生活
  • 参考
    • API参考
    • 实用工具
    • 测试音视频
    • 文档
  • 留言板
  • 关于
剑痴乎
代码为剑,如痴如醉
  1. 首页
  2. 编程之美
  3. 正文

快速排序

2013年9月12日 142点热度 0人点赞 0条评论

快速排序是基于分治策略的一个排序算法,实现快速排序的分治过程如下:
分解:数组A[p..r]被划分为两个(可能空)子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于等于A(q),而且,小于等于A[q+1..r]中的元素。下标q也在这个划分过程中进行计算。
解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]排序
合并:因为两个子数组是就地排序的,将它们的合并不需要操作,整个数组
A[p..r]已排序。
实验代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
using namespace std;
int num;
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}//交换元素位置
void PrintArray(int *arr)
{
    for(int i=1; i<=num; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
int Partition1(int *arr, int p, int r)
{
    int x=arr[r];
    int i=p-1;
    int j;
    for(j=p;j<=r-1;j++)
    {
       if(arr[j]<=x)
       {i=i+1;
       swap(arr[i],arr[j]);
       }
    }
    swap(arr[i+1],arr[r]);
    return i+1;
}//对子数组A[p..r]进行就地重排
void QuickSort(int *arr, int p, int r)
{
    if(p < r)
    {
        int q = Partition1(arr, p, r);
        QuickSort(arr, p, q-1);
        QuickSort(arr, q+1, r);
    }
}//该过程实现快速排序
int main()
{
    int arr[100];
    cout << "请输入元素个数:\n";
    cin >> num;
    cout << "请输入元素大小:\n";
    for(int i=1; i<=num; ++i)
        cin >> arr[i];
    QuickSort(arr, 1, num);
    cout << "最后结果:";
    PrintArray(arr);
    return 0;
}

该算法在最坏情况下的时间复杂性为T(n)=O(n^2),平均情况下的时间复杂性是O(nlogn)

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2017年10月19日

Jeff Young

代码为剑,如痴如醉

打赏 点赞
< 上一篇
下一篇 >

文章评论

取消回复

我的其它小窝

公众号:码上Play(基本不更新,回答问题用)

近期评论
  • Fett on Windows平台WebRTC编译(持续更新)能不能提供一个.lib,一份include,这样我…
  • Jeff on WebRTC研究:BBR拥塞控制被移除了研究过了,等后面有时间简单说明下
  • xhcx on WebRTC研究:BBR拥塞控制被移除了楼主,BBR移除的原因最近有研究吗,分享一下
  • Jeff on Windows平台WebRTC编译(持续更新)M79是2019年发布的版本,不适用这篇文章。编译…
  • haige on Windows平台WebRTC编译(持续更新)我编译的m79版本,用VS2019打开会报错, F…
版权声明

为支持原创,创作更好的文章,未经许可,禁止任何形式的转载与抄袭,如需转载请邮件私信!本人保留所有法定权利。违者必究!

COPYRIGHT © 2021 剑痴乎. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS