java 实现数组-快排序

╰+攻爆jí腚メ 2022-11-30 12:49 115阅读 0赞

快排在我理解就是双指针法。一个数组，左右两个指针，然后左指针向右移动，右指针向左移动。

1      4      6     8      9      2     3     44     55      11

左指针  ↑   ----------》                                                     《---------↑右指针

这里一定要注意，一定是右指针先移动，并且是两个指针每次都移动一次。

算法原理：

1、先确定一个基准点。我选择第一个元素。

2、每次都和这个点比较，比如，右指针遇到比基准点小的就停下来。左指针遇到比基准点大的就停下来。然后这俩元素互换位置。

3、直到这俩指针相遇也就是相等的时候。将基准点和相遇的角标元素互换位置。

4、递归执行基准点的左右子数组。比如 sort(arr,0,基准点-1)，sort(arr,基准点+1,arr.length)

上代码：

public class Demo {
    
        public static void sort(int[] arr){
    
            quickSort(arr,0,arr.length-1);
        }
    
        public static void quickSort(int[] arr,int left,int right){
    
            if(left >= right){
                return ;
            }
    
            int temp ;
            int i = left,j = right;
            int point = arr[left];
    
            while(i < j){
    
                while (point <= arr[j] && i < j){
    
                    j --;
                }
                while (point >= arr[i] && i < j){
                    i ++;
                }
    
                if(i < j){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            arr[left] = arr[j];
            arr[j] = point;
            quickSort(arr,left,j - 1);
            quickSort(arr,j + 1,right);
    
        }
    
        public static void main(String[] args) {
    
            int[] arr = {1,4,6,8,9,2,3,44,55,11};
    
            sort(arr);
    
            for(int a : arr){
                System.out.println(a);
            }
    
        }
    }