数据结构之排序了如指掌(三)

private void quick(int[] arr,int start,int end)
{
//start如果大于等于end说明已经相遇,也说明当前这边已经排完序了
if (start>=end)
{
return;
}
//调用Hoare法先让第一次的基准值到数组中间位置
int pivot=partitionHoare(arr,start,end);
//然后递归基准值左边并排序
quick(arr,start,pivot-1);
//递归基准值右边并排序
quick(arr,pivot+1,end);
}

private int partitionHoare(int[] arr, int left, int right) {
//先将基准值元素给到tmp
int tmp=arr[left];
//并将基准值下标给到i,以免找不到基准值下标,无法交换
int i=left;
//当left小于right时
while (left<right)
{
//我们在此处while循环也需要加上left<right条件,否则left可能大于right
//并且right下标元素大于等于基准值的时候right--
while (left<right&&arr[right]>=tmp)
{
right--;
}
//走到这里说明right找到比基准值小的元素
//left开始找比基准值大的元素,如果left下标元素小于基准值,left++
while (left<right&&arr[left]<= tmp)
{
left++;
}
//走到这里说明left找到了比基准值大的元素,right找到了比基准值小的元素,此时将left元素和right元素交换
//并继续进行while循环
swap(arr,left,right);
}
//走到这里说明left和right相遇,则交换基准值元素和相遇点元素
swap(arr,i,left);
//交换之后,此时left就是基准值下标,返回即可
return left;
}
//挖坑法
private int partitionHole(int[] arr,int left,int right)
{
int tmp=arr[left];
while (left<right)
{
while (left<right&&arr[right]>=tmp)
{
right--;
}
arr[left]=arr[right];

while (left<right&&arr[left]<= tmp)
{
left++;
}
arr[right]=arr[left];
}
arr[left]=tmp;
return left;
}
//交换代码
public void swap(int[] arr,int a,int b)
{
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}

挖坑法

挖坑法思路

1.将基准值保存在临时变量(相当于挖掉挖坑),并且从右边找比基准值小的,左边找比基准值大的

2.从右边找到比基准值小的,放入坑中,此时又出现一个新的坑

3.从左边找比基准值大的,放入坑中,此时又新出现一个坑

4.循环上述过程,当left和right相遇的时候,无论是谁相遇谁,left和right相遇位置一定会有个坑,然后把临时变量也就是基准值放入坑中

5.从左边建立新的基准值递归这个过程

6.从右边建立新的基准值递归这个过程

以上觉得我写的无法理解清楚,请看下图

所有的思路就是这样,就是先把基准值挖坑,然后从右边找,从左边找去填坑,然后相遇位置一定是坑,把基准值放入坑,递归左边和右边即可

挖坑法代码

public void quickSort(int[] arr)
{
    //调用quick方法并传参数
    quick(arr,0, arr.length-1);
}

private void quick(int[] arr,int start,int end)
{
    //start如果大于等于end说明已经相遇,也说明当前这边已经排完序了
    if (start>=end)
    {
        return;
    }
    //调用挖坑法,先让第一次的基准值到数组中间位置
    int pivot=partitionHole(arr,start,end);
    //然后递归基准值左边并排序
    quick(arr,start,pivot-1);
    //递归基准值右边并排序
    quick(arr,pivot+1,end);
}

private int partitionHole(int[] arr,int left,int right)
{
    //默认为最左边为基准值,将基准值挖坑放入临时变量
    int tmp=arr[left];
    //当left没有和right相遇
    while (left<right)
    {
        //当left没有和right相遇并且right还没有找到比基准值小的元素
        while (left<right&&arr[right]>=tmp)
        {
            //向左继续寻找
            right--;
        }
        //走到这说明找到了,然后把坑填上
        arr[left]=arr[right];
        //当left和right没有相遇,并且left没有找到比tmp大的元素
        while (left<right&&arr[left]<= tmp)
    {
        //继续向右寻找
        left++;
    }
        //找到了,此时将right位置的坑填上
        arr[right]=arr[left];
    }
    //走到这里说明left和right相遇了,把基准值填入相遇点
    arr[left]=tmp;
    //返回基准值
    return left;
}

前后指针法

这个方法和上述两个方法略有不同

前后指针法思路

1.让0下标作为基准值

2.left指向0下标,right指向数组最后一个元素

3.创建prev指向left,创建cur指向prev+1

4.当cur没有走完数组最后一个元素,也就是cur<=right

5.让cur一直从左往右去找到比cur小的元素并且满足++prev!=cur,说明prev再往前走一个,此时prev等于cur

6.prev只有在cur找到比基准值小的元素才会往前走,而cur无论有没有找到prev都会往前走

7.prev没有往前走,也就说明了,cur往前走的时候,找到的元素大于基准值

8.如果满足上面条件,就交换cur和prev元素,cur继续往前走,直到走到right位置

9.当走完right,让基准值和prev元素交换,最后返回prev,继续递归遍历prev左边和prev右边

这就有一种cur推着prev走的感觉,只有cur满足条件,prev才有可能往后走

画个图大家就懂了

大家只要清楚的明白cur和prev的满足条件即可

前后指针法代码

public void quickSort(int[] arr)
{
    //调用quick方法并传参数
    quick(arr,0, arr.length-1);
}

private void quick(int[] arr,int start,int end)
{
    //start如果大于等于end说明已经相遇,也说明当前这边已经排完序了
    if (start>=end)
    {
        return;
    }
    //先让第一次的基准值到数组中间位置
    int pivot=partition(arr,start,end);
    //然后递归基准值左边并排序
    quick(arr,start,pivot-1);
    //递归基准值右边并排序
    quick(arr,pivot+1,end);
}

private int partition(int[] arr,int left,int right)
{
    //让prev指向left
    int prev=left;
    //cur指向prev+1
    int cur=prev+1;
    //当cur没有走完right
    while (cur<=right)
    {
        //重点!!  如果cur中的元素比基准值小并且++prev后所在的位置不是cur的位置
        if (arr[cur]<arr[left]&&arr[++prev]!=arr[cur])
        {
            //才会交换prev和cur元素值
            swap(arr,prev,cur);
        }
        //cur不管满不满足以上条件都会往后走,而prev只有满足arr[cur]<arr[left]这个条件,才会往后走,因为是短路与
        //前面条件不满足,不会进行后面条件判断
        cur++;
    }
    //当cur走完right位置,就把基准值和prev交换位置,返回基准值下标
    swap(arr,left,prev);
    return prev;
}

小结

我们可以看这三个方法代码,他们被调用的时候都是通过quick去调用,而且调用三个方法的时候只需要把调用方法名字修改一下就可以了,很方便

我们已经讲完了

直接插入排序(摆扑克牌)

希尔排序(分组摆扑克牌)

冒泡排序(相邻两个元素只要左边比右边大就交换位置,每趟会将数组现存最大元素放到最后面)

堆排序(建立大根堆,然后堆顶元素必然是堆中最大的元素,然后将堆顶元素和最后一个元素交换位置,除去交换的元素,将交换后的堆重新建立大根堆并循环以上过程)

选择排序(找基准值然后排序,再从基准值左边找基准值排序,再从基准值右边找基准值排序)

昨晚熬了个小夜,今天更要加油努力!!!!

喜欢的话记得给个三连!!!(点赞关注收藏)

有问题请在评论区留言或者私信!!

原文地址:https://blog.csdn.net/weixin_67836079/article/details/137716900 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1779471178772123648.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部