欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序(一天一个算法)

程序员文章站 2024-02-23 15:13:58
...

作为一个菜鸡新手,看了网上好多快速排序的文章资质浅的我只能初步理解以下部分。。。

快排的基本思想



快速排序是我们之前学习的冒泡排序的升级,他们都属于交换类排序,
都是采用不断的比较和移动来实现排序的。快速排序是一种非常高效的排序算法,
它的实现,增大了记录的比较和移动的距离,将关键字较大的记录从前面直接移动到后面,
关键字较小的记录从后面直接移动到前面,从而减少了总的比较次数和移动次数。
同时采用“分而治之”的思想,把大的拆分为小的,小的拆分为更小的,
其原理如下:对于给定的一组记录,选择一个基准元素,通常选择第一个元素或者最后一个元素,
通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,
一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,
然后再用同样的方法递归地排序划分的两部分,直到序列中的所有记录均有序为止。

步骤:

1.现在所要排序的数组中设置一个基准值【base】 :不过看了好多文章这种只适合于混乱无序的数组,不适合有序数组

2.在排序分区过程中,将比基准值大的数全放到它的右边,小于或等于它的数全放到它的左边

3.然后在对左右分区重复第二步骤重新设定基准值,继续分区,直到每个分区只有一个元素

图解

两个指针,分别从数组的首尾开始向中间运动,左指针先运动,左指针指到的数若大于或等于枢纽元则停下来,当左指针停下来的时候,右指针运动,右指针指到的数若小于枢纽元则停下来,此时,交换左右指针指向的数,然后重复上述运动。直到左右指针相遇,运动结束。

【枢纽元即文初所指的基准数】

快速排序(一天一个算法)
左指针指到的数等于7,停下来;右指针指向的数大于7,继续走。。。
快速排序(一天一个算法)
右指针指向的数为5,小于7,停下来;然后交换两个指针指向的数。。。
快速排序(一天一个算法)
然后左指针继续走,走到10,大于7,停下来;然后右指针走,指向8,大于7,继续走,然后走到1,小于7,停下来。。。
快速排序(一天一个算法)
然后交换左右两个指针的指向的值。。。
快速排序(一天一个算法)
然后左指针继续走,走到2,小于7,继续走,走到4,继续走,走到7,等于7,停;然后右指针走,走到7,和左指针相遇。。。
快速排序(一天一个算法)
然后以7位界限,左边的都是小于7的数,右边的都是大于7的数。然后将左边的【5,1,2,4】和右边的【10,8,7,19】看成是两个数组,重复上述的步骤,就可以排成【1,2,4,5,7,7,8,10,19】这样的从小到大的有序数组。

package com.Jevin.priorityQueue;
/**
 * @author mahui
 * @date 2020/8/12 -10:27
 *
 * 《那就一天一个小算法吧--》
 * 快速排序Day02--
 */
public class QuickSort {

    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];

        while (i<j) {
            //先看右边,依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边,依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }


    public static void main(String[] args){
        int[] arr = {7,10,2,4,7,1,8,5,19};
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

运行结果:

com.Jevin.priorityQueue.QuickSort
1 2 4 5 7 7 8 10 19 
Process finished with exit code 0