• 周四. 4月 25th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

C++快速排序

admin

11月 28, 2021

  快速排序作为排序家族里面最为快捷的方式,值得思考。我们将一个数组中的某一个数定为基点,然后通过快速排序按照需求(假设升序),将比基点小的数丢在基点左边,把比基点大的数丢在基点右边这样来将基点数的正确位置找到。接着,我们再对基点两边的数组分别进行快排以达到有序的目的。

  举例实际分析如下:

  int data[6] = {6,2,7,3,8,9};

  int i = left,j = right,key = data[left];

  初始数组为6 2 3 7 8 9,我们将基点数定位6进行第一次比较。

  此时right = 5,left = 0。先从右往左找寻比key小的数,right = 3时找到。将data[ left]赋值为data[right] -> 3 2 7 3 8 9。

  然后从左往右找比key大的数,i = 2时找到。我们将data[right]赋值为data[left] -> 3 2 7 7 8 9。

  左右找寻数的任务已经完成,此时应该将key值放在正确位置去了,但是这个位置是哪里?现在还不知道,因为左右标志位还不等,但是下一次循环开始后,发现left 和 right 在2的地方相等了。所以这个位置应该是2 -> 3 2 6 7 8 9。这样,一次排序完成了。

  现在i 和 j 已经都变成了2而且6的正确位置已经找到了。但是按照算法的思路将这个数组分为左右两部分该怎么办,我们的left和right派上了大用场。从left 到 i – 1为左边部分,从j + 1 到 right则为右半部分,对这两部分进行递归快排最终可得到结果。

//
//  main.cpp
//  test
//
//  Created by MadMarical on 15/11/20.
//  Copyright (c) 2015年 com. All rights reserved.
//

#include <iostream>

using namespace std;

int pData[] = {6,2,7,3,8,9};

void quickSort(int *p,int s,int t)
{
    int left,right;
    int key;
    left = s,right = t;
    key = p[left];
    if (s >= t)
    {
        return;
    }
    while (left != right) //左右标志不等,在数组内寻找
    {
        while (left != right && p[right] >= key) //因为是升序,在数组里从右往左找寻一个比key小的数。
        {
            right--;
        }
        p[left] = p[right];
        while (left != right && p[left] <= key)
        {
            left++;
        }
        p[right] = p[left];
    }
    p[left] = key;
    quickSort(p, s, left - 1);
    quickSort(p, right + 1, t);
}

int main(int argc, const char * argv[])
{
    quickSort(pData, 0, 5);
    
    cout<<pData[0]<<" "<<pData[1]<<" "<<pData[2]<<" "<<pData[3]<<" "<<pData[4]<<" "<<pData[5]<<endl;
    
    return 0;
}

反思:

1.如果使用swap进行交换,在代码理解上会减轻不少。

2.快速排序中的判断方法和递归调用值得深思,网上的许多答案也是模棱两可,还是要自己理解比较靠谱。

  

  

《C++快速排序》有2个想法
  1. Wow, superb weblog format! How long have you ever been running a
    blog for? you made blogging glance easy.
    The whole glance of your website is excellent, let alone the
    content material! You can see similar here sklep internetowy

  2. Hey there! Do you know if they make any plugins to assist
    with SEO? I’m trying to get my site to rank for some targeted keywords but I’m not seeing very good
    results. If you know of any please share. Kudos!

    I saw similar text here: Link Building

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注