排序

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

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

五种最常见的排序

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

快速排序

以下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🤣