排序

稳定排序:当两个元素相同时,排序后这两个元素相对位置不变则称为稳定排序,我们一般需要的都是稳定排序

排序和查找的关系:排序是搜索的前提,排序是重点

五种最常见的排序

冒泡排序
选择排序
插入排序
快速排序
归并排序

快速排序

以下gif来自该视频,虽然是java,但是讲的很棒bilibili
我们假设有一个队人,要让他们按照从小到大排队站好,我们可以这样做,先让最左边的人当作基准点,把队伍分成比他高的和比他矮的两部分这样56号的位置已经确定了,我们先看他的左边,是比他矮的小队,我们依然是让最左边的当作基准点,也就是8号,针对于它的小队,不再是全体小队,让比八号矮的站到他的左边,高的站到他的右边。

完成之后我们再对56号右边的小队进行同样的操作,其实就是递归

我们来看看每个元素的归位顺序

我们来看一下快排的伪算法

//
quickSort(int* arr,int left, int right)
//这里的left和right参数表示对一个闭区间内的元素进行排序
{
   如果left >= right 排序结束

   基准点为arr[left]
   
   把小的放到左边,大的放到右边//重点实现部分

   对左边队伍再次进行快排
  
   对右边队伍再次进行快排
}

接下来我们就看一下如何实现,我们先定义两个变量i和j分别指向头部和尾部,我们先让j向左移动,直到遇到一个比p也就是基准点小的值,停止移动,我们再让i向右移动,直到遇到一个比p大的值停止移动,然后交换i和j的值

交换之后我们继续让j移动,直到遇到比p小的值,再让i移动,直到遇到比p大的值,交换 当最后i和j相等时,i的左边就是比p小的,i的右边就是比p大的,我们就可以把i和p交换位置上代码

//快排
void quickSort(int* arr,int left,int right)
{
    if(left >= right)
        return;
    //把最左边的定为基准点
    int p = arr[left];

    //把大的放到基准点右边,小的放到基准点左边
    int i = left,j = right;
    while(j > i)
    {
        //j向左移找到一个比p小的元素
        while(arr[j]>=p && j>i)
            j--;
        //i向右移找到一个比p大的元素
        while(arr[i]<=p&&j>i)
            i++;
        int temp = arr[i];
        arr[i] =arr[j];
        arr[j] = temp;
    }
    
    //把基准点与i交换
    if(i<j)
    {
       arr[left] = arr[i];
       arr[i] = p;
    }
    
    //对左右两队再进行快排
    quickSort(arr,left,i-1);
    quickSort(arr,i+1,right);

}
int a[5] {2,4,1,5,7};

quickSort(a,0,4);

for(int i = 0; i<5 ; ++i)
{
    cout << a[i];
}
/*输出
12457
*/
  • 还有一种写法,只有一点微小的差别

在寻找基准点位置的时候我们先让j向左移,再让i向右移,最后交换i,j元素,我们也可以在j找到一个比p小的元素后就将他赋值个i,当i找到一个大于p的值的时候就赋值给j,最开始i就是基准点,赋值给了p,所以i的位置实际上已经空出来了,当把j赋值给i时,这个空被填上了,但是j又空了出来,这就是一个不断填坑的过程

//
 while(j > i)
    {
        //j向左移找到一个比p小的元素
        while(arr[j]>=p && j>i)
            j--;
        aar[i] = arr[j];
        //i向右移找到一个比p大的元素
        while(arr[i]<=p&&j>i)
            i++;
        arr[j] = arr[i];
   }
  •  同样当你想用其它位置的数来做基准点也很简单,只要你把它和第一位交换就可以了

    有问题欢迎大家提问哦0。0 可以直接评论😂 也可以QQ🤣

排序》有30个想法

  1. KelErex说:

    Zithromax And Prolonged Qt Interval Viagra Liquida Pfizer Viagra Prezzo [url=http://cialibuy.com]Cialis[/url] order accutane from canada Buy Olanzapine Uk Propecia For Sale Cheapest

  2. smore traiolit说:

    An impressive share, I just given this onto a colleague who was doing a little analysis on this. And he in fact bought me breakfast because I found it for him.. smile. So let me reword that: Thnx for the treat! But yeah Thnkx for spending the time to discuss this, I feel strongly about it and love reading more on this topic. If possible, as you become expertise, would you mind updating your blog with more details? It is highly helpful for me. Big thumb up for this blog post!

  3. smoretraiolit说:

    Nice read, I just passed this onto a friend who was doing a little research on that. And he actually bought me lunch as I found it for him smile Thus let me rephrase that: Thank you for lunch!

  4. dominoqq说:

    Good day very cool blog!! Man .. Beautiful ..
    Wonderful .. I’ll bookmark your web site and take the feeds additionally?
    I’m happy to search out numerous helpful information here in the post, we’d like
    work out extra strategies in this regard, thanks
    for sharing. . . . . .

发表评论

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