加载中……
C/C++实现快速排序

提出

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序,它有一种比较重要的思想——分治思想。大致可以描述为,确保一组序列中存在一个特别的数据,其左边的数据都比他大(小),右边的数据都比它小(大),那么可以将这个数作为基准数,在其左边和右边分别再次确保一个数满足同等关系,直到区间大小为1,则排序完成。

时间复杂度

O(N*logN)

步骤

  1. 选取基准数
  2. 以基准数为中心点进行分区,左边分区比基准数小(大),右边分区比基准数大(小)。
  3. 每个分区递归完成上述规则,直到分区大小为1。

代码实现

快速排序实现方式多样,这里对本实现方式做简要介绍。

在这里为实现代码简洁,选取第一个数作为基准数,如需设置其他位置的数作为基准数,则只需要将该位置的数与第一个数交换位置即可。

初始情况:

15, 3, 432, 23, 32, 13, 6, 3256, 5567, 12, 8, 987

首先保存基准数的值( tmp = arr[s] ),然后从最右边查找第一个小于等于基准数的值,并将该值保存到基准值的位置(基准值已保存,所以可以直接将该值覆盖,红色覆盖蓝色),并将基准值位置向右偏移一位(s++),由于基准值以第一个数开始,则可以理解为将小值往右边扔。执行完成结果应当是这样:

8, 3, 432, 23, 32, 13, 6, 3256, 5567, 12, 8, 987

此时可以看到有两个数值8,我们可以理解为,可以在右边的8头上随便动土~

因此,我们开始从基准值位置开始向右移动,直到找到第一个比基准值大的数。然后去欺负右边的8,直接覆盖掉他,然后右边界限减1(e–)。数组此时变为:

8, 3, 432, 23, 32, 13, 6, 3256, 5567, 12, 423, 987

可以很直观的发现,此时有两个423,话不多说,从右边开始找小于基准值的数,盘他。

8, 3, 12, 23, 32, 13, 6, 3256, 5567, 12, 423, 987

这样,我们始终保持一个可改变的数值去容纳查找到的符合规定的值,直到基准值到达右界限( s >= e )并将基准值赋予该位置( arr[s] = tmp )。则满足基准值左右分治条件(左边小与基准值,右边大于基准值)。结果为:

8, 3, 12, 6, 13, 15, 32, 3256, 5567, 23, 432, 987

最后,划分左右分区,实行递归即可。

 

/*快速排序
 *C/C++
*/

#include <iostream>

using namespace std;


int quick_sort( int *arr, int start, int end )
{
    int s = start, e = end;//记录分区信息
    //swap(arr[s],arr[(s+e)]/2);
    int tmp = arr[s];//保存基准值
    
    if ( s >= e )
    {
        return 0;
    }

    while ( s < e )
    {
        while ( s < e && arr[e] )//从右向左查找第一个小于等于基准值的数
        {
            if ( arr[e--] <= tmp )
            {
                arr[s++] = arr[++e];//将该值往区间最右边移动
                break;
            }
        }

        while ( s < e && arr[s] ) //从左向右查找第一个大于基准值的数
        { 
            if ( arr[s++] > tmp )
            {
                arr[e--] = arr[--s];//将该值往区间最左边移动
                break;
            }
        }
    }

    arr[s] = tmp;//将基准值填入对应位置
    quick_sort( arr, start, s - 1 );//递归左分区
    quick_sort( arr, s + 1, end );//递归右分区
    return 0;
}

int main()
{
    int arr[] = {15, 3, 432, 23, 32, 13, 6, 3256, 5567, 12, 8, 987};
    int end = sizeof( arr ) / sizeof( arr[0] ) - 1;
    int start = 0;//此处以第一个数作为基准数,若以其他数(如中间数)作为基准数,则应实现并打开修改swap注释。
    quick_sort( arr, start, end );

    while ( start <= end )
    {
        cout << arr[start++] << endl;
    }

    return 0;
}

执行结果

C/C++实现快速排序

版权声明: 若无特殊说明,文章均为原创,版权归本文作者所有,转载请保留出处和此说明!
本文链接: C/C++实现快速排序
本文作者: Jan.
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇