快速排序2

Myth丶恋晨 2021-09-26 14:12 150阅读 0赞

这个排序方法跟算法导论上不一样。  
取第一个元素为基准。定义两个指针，一个从前往后扫描，一个从后往前扫描。  
①. i = L; j = R; 将基准数挖出形成第一个坑a\[i\]。  
②．j–，由后向前找比它小的数，找到后挖出此数填前一个坑a\[i\]中。  
③．i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a\[j\]中。  
④．再重复执行②，③二步，直到i==j，将基准数填入a\[i\]中。

import java.util.Random;
    
    public class 快速排序2 { 
    
        private static int N = 10;
        static Random rand = new Random();
        /** * @param args */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            test_quicksort_1();
        }
        private static void test_quicksort_1() {
            // TODO Auto-generated method stub
            int[] A = new int[N];
            for (int i = 0; i < N; i++) {
                A[i] = rand.nextInt(1000);
            }
            System.out.println("排序前：");
            print(A);
            Quick_sort1(A, 0, A.length - 1);
            System.out.println("排序后（每次第一个作为哨兵）：");
            print(A);
        }
        private static void Quick_sort1(int[] a, int p, int r) {
            // TODO Auto-generated method stub
            if(p<r){
                int q = Patition(a,p,r);
                Quick_sort1(a,p,q-1);
                Quick_sort1(a,q+1,r);
            }
        }
        private static int Patition(int[] a, int p, int r) {
            // TODO Auto-generated method stub
            //第一个元素作为哨兵
            int x = a[p];
            int i = p;
            int j = r;
            while(i<j){
                //j从后往前走，找到比x小的元素 放到i处
                while(i<j&&a[j]>=x)
                    j--;
                a[i] = a[j];
                //i从前往后走，找到比x大的元素 放到j处
                while(i<j&&a[i]<=x)
                    i++;
                a[j] = a[i];
            }
            //把x放到i处
            a[i] = x;
            return i;
        }
        // 打印数组
        private static void print(int[] A) {
            // TODO Auto-generated method stub
            for (int i = 0; i < A.length; i++) {
                System.out.print(A[i] + "\t");
            }
            System.out.println();
        }
    }

实验结果：

排序前：
    392 781 186 74  690 84  248 805 319 455 
    排序后（每次第一个作为哨兵）：
    74  84  186 248 319 392 455 690 781 805